A Discussion on Data Structures — Queues

Implementing a straightforward data structure that works in a FIFO fashion.

Photo by Annie Spratt on Unsplash

This is the latest in a series of posts on Data Structures, documenting my progress as I implement an STL like library called Telemetry. More here:

Telemetry — Implementing a library for Data Structures and Algorithms in C++.

Today, let’s talk about Queues. Since my last post, I changed things in the Telemetry repository a bit — for one, I wrote a decent README and added a TODO in there. Implementing Queues was to be done on priority (😃), so here we are!

What are Queues?

As always, let me begin with what a Queue is. According to trusty old Cplusplus.com —

Queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

Diagrammatically, a queue can be represented like this:

Fig. 1. A standard FIFO Queue.

As in Fig. 1, the Queue allows entry from the Back and exit from the Front, keeping everybody in line and awaiting their turn. Fairly simple.

Reading the Cplusplus.com entry further, we can see that a Queue is also a container adaptor, and it can be implemented using either a Vector or a List because the underlying container should support functions like push_back() and pop_front(), apart from allowing us access to the front and back elements. Luckily for us, we can rely on our Lists implementation to run the show here!

So now that we know how a Queue is supposed to behave, let’s take a gander at the UML Class Diagram for a Queue.

Fig. 2. The UML Class Diagram for our Queue.

There isn’t any need for special data members in the class. The static queue_count and the ID variables are meant for a more diagnostic purpose than anything else. In case multiple objects are being used concurrently, they identify the offending object when an Exception is thrown. Speaking of which, I did a little something since the last article…

For the sake of simplicity, I discarded the StackUnderflowException, EmptyListException and every other ThisAndThatException in favor of a nice and clean EmptyContainerException. It still behaves as before though — if we try to rummage around an empty container, it spits out the ID of the container and tells us there’s nothing to look at there!

Operations on Queues

The following operations must be available in Queues:

1. push(): Push an element from the back of the Queue.
2. pop(): Pop an element from the front of the Queue. If the Queue is empty, throw an EmptyContainerException.
3. front(): Access the front of the Queue but don’t remove the element. If the Queue is empty, throw an EmptyContainerException.
4. back(): Access the back of the Queue but don’t remove the element. If the Queue is empty, throw an EmptyContainerException.
5. size(): Return the current size of the Queue.
6. empty(): Return if the Queue is empty or not.

Class Definition

The Queue class boils down to a very simple and familiar definition, as follows: (As always, I’m leaving out fluff like include guards, #include statements and the like. See the GitHub repository for the proper code. Link at the end!)

template <class T>
class Queue {
private:
    static int queue_count;
    int ID;
    List<T> queue;
public:
    // utility functions;
    void push(T arg);
    T pop();
    T front();
    T back();
    int size();
    bool empty();
    static int get_queue_count();
    std::string get_ID();
//constructors;
    Queue() {
        ID = ++queue_count;
    }
};

Some of the member functions are implemented as follows:

push()

// push arg into the queue from the rear;
template <class T>
void Queue<T>::push(T arg) {
    queue.push_back(arg);
}

Notice that we have used the queue.push_back() function here from the underlying List, to add elements to the Queue from the back.

pop()

// pop arg from the queue from the front;
template <class T>
T Queue<T>::pop() {
    if (queue.empty()) {
        //throw Exception
        throw EmptyContainerException(std::to_string(ID));
    } else {
        return queue.pop();
    }
}

Notice the new EmptyContainerException class in action!

front()

// accesses the first element in the queue but does not remove it;
template <class T>
T Queue<T>::front() {
    if (queue.empty()) {
        throw EmptyContainerException(std::to_string(ID));
    } else {
        return (queue.get_head())->data;
    }
}

Notice how (queue.get_head()) is used wherever a reference to the front element is required. Keep in mind that that returns a pointer to the Node and not the data — the pointer must be “dereferenced” to access the data!

back()

// access the last element in the queue but does not remove it;
template <class T>
T Queue<T>::back() {
    if (queue.empty()) {
        throw EmptyContainerException(std::to_string(ID));
    } else {
        return (queue.get_tail())->data;
    }
}

The other member functions are pretty much the same as before. However, to see the full header file, please head over to:

utkarshpant/telemetry

That’s it for Queues! I should mention that a little further into our journey with Telemetry, we’ll implement another type of Queue — a Priority Queue (see what I did up top?) These queues accept elements in any order but always pop the element with the highest priority. Since the implementation under the hood is completely different from what we saw today, I’ll discuss this a little further down the road. But we’ll still add the implementation of the class to Queue.h just like our STL cousins.

fin.

References

1. Reema Thareja, 2017, Data Structures Using C, 2nd Ed., Oxford University Press.
2. std::queue (http://www.cplusplus.com/reference/queue/queue/)