Queue Data Structure

Queue is an abstract data structure (ADT) which replicates the queue we observe in public places like check-in counters, ticket counters etc. Queue data structure allows us to add or remove elements into a virtual queue. The new elements are added to the rear end of the queue and elements are removed from the front end of queue. Because of this behaviour, queue data structure is referred as a First in First out (FIFO) type of data structure. It means that the first element pushed into the queue will always be the first element to come out.

Basic Operations Supported by a Queue

Before we go through all the operations formally supported by a queue abstract data type, let’s go through a practical example and relate each operation to a corresponding one in real life.

Assume that there is a checkout queue at a grocery counter. Let us now think through all the operations that are necessary for proper funtioning of the queue:

• We need a way for people to join the queue. Also the persons reaching first in the queue should be at the front of queue.
  • This action corresponds to enqueue(person)/push(person) operation to the queue
• We need a way to get details from person at the front of queue without removing him from queue and process the items he wishes to check out
  • This action corresponds to front() / first() operation to the queue which returns the element present at the end
• We need a way for the persons whose items are processed to leave the queue and after this the next person who came the earliest among all remaining persons, should be at the front of queue
  • This action corresponds to dequeue() / pop() operation to the queue
• We also need a way to check if the queue is empty or not and take decisions like halt the counter etc.
  • This action corresponds to is_empty() operation to the queue which tells us if the queue is empty

All the operations discussed are summarized in the table below:

Let us now go through each operation in detail.

Push an element into the rear end of Queue

This operation allows us to push or “enqueue” element into the queue. The enqueued element will be placed at end or tail of the queue. The animation below depicts enqueuing of 4 elements into a queue.

This operation is denoted by enqueue(element) which takes in an element to adds to the rear end of queue.

Pop an element from the front end of Queue

This operation allows us to remove or “dequeue” the front element in the queue. It is similar to allowing person at the beginning of a queue to leave the queue. The animation below depicts dequeuing of 4 elements from a queue.

This operation is denoted by dequeue(element) which removes and returns the element present at the front of queue.

Access the element present at the front of Queue

This operation allows us to access the “front” element in the queue. It is similar to taking the credentials of a person standing at the front of a queue and doing some processing while the person is still in queue.

This operation is denoted by front() or first() which returns the information about the element present at the front of queue.

Check if the Queue is Empty

This operation is useful for finding out if a queue is empty. This is helpful especially to prevent popping / dequeuing an element from an empty queue. Or to prevent accessing the front element in an empty queue etc.

This operation is denoted by is_empty() which returns true if the queue is empty and false otherwise.

Implementing Queue Abstract Data Structure

Array implementation of Queue

/******************************************************************************
C++ Implementation of Queue ADT using Vector/List
*******************************************************************************/

#include <iostream>
#include <vector>

// Using template with generic type T
// So that we can decide the type of elements
// We wish to use the queue for
template <typename T> class Queue {
private:
  std::vector<T> array;
  size_t head = 0;
  size_t queue_size = 0;

public:
  Queue(size_t size) : array(size) {}

  void enqueue(T element) {
    // Uses the concept of circular arrays
    // to find the correct insert position
    array[(head + queue_size) % array.size()] = element;
    queue_size++;
  }
  T dequeue() {
    T result = array[head];
    head++;
    if (head == array.size())
      head = 0;
    queue_size--;
    return result;
  }
  bool is_empty() const { return queue_size == 0; }
  T &front() const { return array[head]; }
};

// Let us now test the Queue ADT!
int main() {
  Queue<int> q(5);
  q.enqueue(1);
  q.enqueue(2);
  q.enqueue(3);

  while (q.is_empty() != true) {
    std::cout << q.dequeue() << " ";
  }
  return 0;
}

Linked list implementation of Queue

/******************************************************************************
C++ Implementation of Queue Data Structure using Linked List
*******************************************************************************/

#include <iostream>
#include <memory>

// Define the Linked list data structure
template <typename T> struct LinkedListNode {
  LinkedListNode(T element) : value(element) {}
  T value;
  std::shared_ptr<LinkedListNode<T>> next;
};

// Define the Queue data structure
template <typename T> class Queue {
private:
  std::shared_ptr<LinkedListNode<T>> head, tail;
  size_t queue_size = 0;

public:
  Queue() {}

  void enqueue(T element) {
    if (!head) {
      head = tail = std::make_shared<LinkedListNode<T>>(element);
    } else {
      tail->next = std::make_shared<LinkedListNode<T>>(element);
      tail = tail->next;
    }
    queue_size++;
  }
  T dequeue() {
    T result = head->value;
    head = head->next;
    queue_size--;
    return result;
  }
  bool is_empty() const { return queue_size == 0; }
  T &front() const { return head->value; }
};


// Let us now test the implementation
int main() {
  Queue<int> q;
  q.enqueue(1);
  q.enqueue(2);
  q.enqueue(3);

  while (q.is_empty() != true) {
    std::cout << q.dequeue() << " ";
  }
  return 0;
}

Applications of Queue Data Structure

• Queues are used for maintaining active playlists in media players (The song added to the queue first needs to be played before the next)
• In printer job queues where each print job has to be queued until the earliest print job in the queue is complete
• In task handlers where we need to process tasks on a first come first serve basis
• In messaging queue’s where there is a need to decouple senders and listeners
• In data buffers where processed data needs to be removed from the start of buffer and new data needs to be added to the end of buffer

References

• Operations Visualization
• Oxford edu
• Wikipedia