Whereas a stack provides a last in, first out (LIFO) collection, a queue provides a first in, first out (FIFO) collection. In a queue, the first item added to the collection is the first one that will be removed. The second item added will be the second one removed, and so on. Think of a line of people waiting for something. The first person to get in line is the first person to be served and leave the line.
The first in, first out property of a queue lends itself to more straight forward uses than stacks. We pretty much only need a queue if we want to add things to a collection and then remove them in the same order that they were added.
Like a stack, a queue does not imply any particular implementation. The only real requirement is that we can efficiently add items to one end of the collection (the back of the queue) and remove items from the other end (the front of the queue).
In a linked list based implementation of a queue, to efficiently add items to the back and remove them from the front, we have two choices:
Use a doubly linked list with a tail pointer, so we can efficiently add or remove at both the head and tail of the list. In this case we can call either end the “front” and the other the “back”.
Use a singly linked list with a tail pointer. In this case, the only thing that we can efficiently do at the tail of the list is to add values. Values can only be efficiently removed at the head. So in this implementation, we have to define the “front” of the queue to be at the head of the list, and the “back” of the queue to be at the tail of the list.
Activity29.3.1.Queue Implemented with a Linked List.
A queue of integers has been implemented using a singly linked list. Use the interactive below to experiment with enqueueing and dequeueing items from the queue.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
Because this behavior is identical to that of a linked list, just with different terminology, we can easily use an existing linked list implementation (as long as that implementation provides the necessary operations) to create a queue.
class IntQueue {
private:
list<int> list; // Underlying linked list to store queue elements
public:
void enqueue(const int& item) {
list.push_back(item); // Add item to the back of the list
}
int dequeue() {
if (list.empty()) {
throw std::out_of_range("Queue is empty");
}
int frontItem = list.front(); // Get the item at the front of the list
list.pop_front(); // Remove the item from the front of the list
return frontItem; // Return the dequeued item
}
bool isEmpty() const {
return list.empty(); // Check if the queue is empty
}
};
As when we examined implementing a stack using a list (or a vector), using an existing list implementation means the queue class is not responsible for managing the memory of the underlying data structure. It is just responsible for providing the queue interface.
