Queues

Queues are dreadful in real-life when you have to wait in line for an hour or two. But in data structures, they are very useful and simple to implement.

Queues follow a very simple design concept: First-In-First-Out or FIFO. In other words, items arrive first into a queue are processed first.

Queues are useful to use as a buffers to store system input data until the system catches up and asks for more data from the queue to process.

FIFO queue featuring enqueue() and dequeue() methods

FIFO queue featuring enqueue() and dequeue() methods


Implementation of queue data structure is fairly simple. Queues sport two major methods: enqueue() to add items to our queue structure; and dequeue().

When you think about it, queues are opposites to stacks. So, similarly we can utilize the same underlying data structure we designed before (Linked List) to implement a Queue class. The fact that our linked list features a tail pointer is just great. Because we can use it to insert items into a queue from the back and use the head pointer to dequeue items from the front. Let’s take a look a the following code.

#include "List.h"

template <typename T>
class Queue
{
public:
	Queue<T>(void) { _size = 0; }
	~Queue<T>(void) {}

	void enqueue(T item); // adds items to queue
	T dequeue(); // removes items from queue

	int size() { return _size; }

private:
	int _size;
	List<T> _queue;
};

Similar to our Stack implementation, we defined two methods to add and remove items: enqueue() and dequeue(). Additionally, we declared a size() method to keep track of queue size.

Here is the code for enqueu() and dequeue().

template <typename T>
void Queue<T>::enqueue(T item)
{
	_size++;
	_queue.addToTail(item);
}

template <typename T>
T Queue<T>::dequeue()
{
	_size--;
	return _queue.deleteFromHead();
}

As you can see above, enqueue() adds items to the list at the back, and dequeue() removes items from the front. Both, methods run in constant time O(1) because List::addToTail() and List::deleteFromHead() both run in constant time.

Note

For simplicity we didn’t add any error checking to our methods, but we could write some error check to validate the _size member to make sure it is valid.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>