Queue Data Structure

↞↞Previous ↞Stack Data Structure

What is Queue?

You must have seen people line up in a bank to be served by a teller or at a Train ticket counter to get the ticket. This is always a fair practice which we follow in our real life. Queues maintain first-in, first-out order (FIFO). The FIFO property of a queue makes it similar like a line of customers waiting to get the tickets. We use Queue when order of retrieval should be the same as the order of insertion. Queues are often described in terms of producers and consumers. A producer is anything that stores data in a queue, while a consumer is anything that retrieves data from a queue.
Operations on a queue:

  • Enqueue(x): Insert item x at the back of queue.
  • Dequeue(): Return (and remove) the front item from queue.
  • peek(): Return the front item of queue.
  • Full(): Test whether the more items can be enqueued to the Queue.
  • Empty(): Test whether the more items can be dequeued from the Queue.

Implementation of Queue Data Structure:

  1. Implement using simple array. (bounded)
  2. Implement using linked list. (unbounded)

Queues are little more difficult to implement than stacks, because action happens at both ends. Queue maintain indices to the first (front) and last (rear) elements in the array. We always enqueue an element at the rear of the queue, just as a newly arriving customer takes a place at the end of the line. The element dequeued is always the one at the front of the queue, like the customer at the head of the line who has waited the longest.

Queue data structure
When you insert a new item in the queue in the Queue, the Front arrow moves upward, toward higher numbers in the array. When you remove an item, Rear also moves upward. The problem with this arrangement is that pretty soon the rear of the queue is at the end of the array. Even if there are empty cells at the beginning of the array, because you have removed them with dequeue, you still can’t insert a new item because Rear can’t go any further.
Queue data structure-2
To avoid the problem of not being able to insert more items into the queue even when it’s not full, the Front and Rear arrows wrap around to the beginning of the array. The result is a circular queue.
Queue data structure-3

Queue implementation in Java using Array

Queue implementation in Java using Linked List

Create a Node class which will hold value and link to the next element.

Create the Queue with all the methods.


References:

  • Introduction To Algorithm – CLRS.
  • Algorithm Design Manual – Skiena
  • Data Structure & Algorithms In Java – Robert Lafore