Data Structures - Queue ADT

<< Previous

Next >>

Queue is a data structure in which insertion is done in one end (rear) whereas deletion of an element can be done in another end (front).

Queue Data Structure support two operations:

• ENQUEUE - insert an element at the end of list or Rear end
• DEQUEUE- delete an element from the front of the list or Front end

Queue Data Structure is a FIFO data structure(First in First out).

Sample Use cases for Queue Data Structure

• Theater ticket counter
• Train ticket counter
• Order queue for Online Shopping portal
• Task Queue for computer system such as CPU task scheduling,
• Document Queue for Printer
• Signal queue for Interrupts handling

Queue Data Structure - Example 1

Implementation of Queue Data Structure

Queue is implemented by either an array or the linked list.

Array and Linked List implementation of queue give O(1) running time for all operations.

For array implementation, we can keep an array, Queue[], positions(Front and Rear) and queue size which keeps track of number of elements in the queue.

To Enqueue an new element X, we need to increase the size and increment the Rear position,then set Queue[rear] = X.

To an element Y, we need to decrease the size and increment the Front position, then set the return value to Queue[front] = Y.

Queue - circular array implementation

Whenever the front or rear reaches to the end of the array, it is wrapped back to the beginning.

Queue Data Structure - Basic Operations

Queue is used for the following two basic operations:

enqueue(): To add new data into the queue
dequeue(): To remove data from queue

Queue Data Structure Enqueue() Operation

Enqueue is used to insert a new data into the queue.

To enqueue of new element X

• first check whether the queue is full or not.
• If the queue is full, generate the overflow error message
• if the queue is not full, increase the size of the queue and rear value and then set queue[rear]=X.

Queue Data Structure - Implementation of enqueue

void enqueue(int data)
{
 if(size==MAXVALUE))
  cout<<"The Queue is full";
 else
 {
  Queue[++rear]=data;
  size++;
  cout<<"data is inserted";
 }
}
 

Queue Data Structure - Dequeue() Operation

Dequeue() operation is used to remove a data element from the queue.

In a Dequeue Operation, data is not directly removed. Instead, start index is moved to the next position and hence the first element is not part of the queue anymore and 2nd element becomes the 1st element. Now, the size of the queue is reduced by 1

To dequeue of element X

1. first check whether the queue is empty or not.
2. If the queue is empty, generate the underflow error message.
3. If the queue is not empty, access the value of Queue[front] and then increase the front index and decrease the size of the queue.

Queue Data Structure - Implementation of dequeue() in C++

void dequeue()
{
int data;
 if(size==0)
   cout<<"The queue is empty";
 else
 {
   data = Queue[front];
   front = front + 1;
   size--;
   cout<<"The return value is"<< data;
 }
}

<< Previous

Next >>