In our previous post, we saw how to model a Queue data structure using Linked List as a container for elements. Now, we will see how to implement the methods enqueue() and dequeue().

This is very similar to inserting a new element to a linked list as we saw earlier. To insert a new item, we construct a node with that item and a next pointer, add it to the list and adjust the pointers.

void Queue::enqueue (int item) {
  // if the queue is empty
  // front and rear are the same, i.e the new item
  Node *new_item = new Node;
  new_item->data = item;
  new_item->next = NULL;
  if (rear == NULL) {
    front = rear = new_item;
    return;
  }
  // else add it to the rear end 
  // of the queue
  rear->next = new_item;
  rear = new_item;
}


Queue Operations

int Queue::dequeue () {
  int res;
  // check if the queue is empty
  if (front == NULL)
    throw out_of_range("Empty queue");
  
  // get the item to dequeue
  Node *dequeue_item = front;
  res = front->data;
  front = front->next;

  // now, if there was only one node
  // to pop front would point to NULL
  if (front == NULL)
    rear = NULL;

  delete (dequeue_item);
  return res;
}

bool Queue::is_empty () {
  return (front == NULL);
}

That’s all there is in Queues!