Queue.md

Queue

A queue stores a collection of data values in a FIFO (First In, First Out) order. The first element added to the queue will be the first to be processed (removed).
A queue can only be accessed through its ends, referred as head for its rear and tail for its back.
The implementation could be an array-like (static and contiguous) or a linked-list-like (dynamic and dis-contiguous).

Table of Contents

Queue

• Table of Contents
• Common operations on Queue
  • Enqueue
    • Enqueue Example
  • Dequeue
    • Dequeue Example
  • Peek
    • Peek Example
  • Circular Queue
    • Circular Queue Example
  • Double Ended Queue
    • Double Ended Queue Example

Common operations on Queue

Enqueue

Add item to the rear of the queue

Enqueue Example

let queue = [4, 1, 0, 2]; queue.enqueue(5); // queue is now [4, 1, 0, 2, 5]

Dequeue

Remove the item from the front of the queue

Dequeue Example

let queue = [4, 1, 0, 2]; let head = queue.dequeue(); // head is 4 // queue is now [1, 0, 2]

Peek

Some programming languages provides peek method to allow checking the value of the current head without removing the value from the queue.

Peek Example

let queue = [4, 1, 0, 2]; let currentHead = queue.peek(); // currentHead is 4 // queue remains [4, 1, 0, 2]

The above shows the implementation of a simple Queue.

There are more types of Queues:

• Circular Queue
• Double Ended Queue

Circular Queue

If the last position is full and the first position is empty, we can not insert an element in the first position in a Simple Queue. However this is possible if we use circular Queue, where the last element is connected to the first element forming a circle-like structure.

Circular Queue Example

Dequeue and then enqueue

`` let size = 4 let queue = [4, 1, 0, 2]; let head = queue.dequeue(); // head is 4 // queue is now [ 1, 0, 2]

enqueue(8); /* queue is now [8, 1, 0, 2]. This operation could not be done in a simple queue since the last position of the queue is still occupied. According to simple Queue the queue is full. */

``

Double Ended Queue

Double Ended Queue or Deque is a type of queue where insertion and deletions can be done from both ends (front and rear).it does not follow FIFO rule (First In First Out).

Double Ended Queue Example

Insert from front

let queue = [4, 1, 0, 2]; queue.InsertFront(9); //The queue is now [9, 4, 1, 0, 2]

Insert from end

let queue = [4, 1, 0, 2]; queue.InsertEnd(9); //The queue is now [4, 1, 0, 2, 9]

Delete from front

let queue = [4, 1, 0, 2]; queue.DeleteFront(); //The queue is now [1, 0, 2]. 4 has been deleted

Delete from end

let queue = [4, 1, 0, 2]; queue.DeleteEnd(); //The queue is now [4, 1, 0]. 2 has been deleted

There are 2 types of Deque:

• Input restricted:
  In this Input is restricted to one end only whereas deletion is possible from both ends.

• Output restricted:
  In this Input is deletion from one end only whereas insertion(input) is possible to both ends.