Queue

Basic Queue Operations:

A queue is a data structure that is best described as "first in, first out". A queue is another special kind of list, where items are inserted at one end called the rear and deleted at the other end called the front. A real world example of a queue is people waiting in line at the bank. As each person enters the bank, he or she is "enqueued" at the back of the line. When a teller becomes available, they are "dequeued" at the front of the line.

Representation of a Queue using Array:

Let us consider a queue, which can hold maximum of five elements. Initially the queue is empty.

0        1         2        3         4

Q u e u e E mp t y

F RO NT  = RE A R = 0

F R

Now, insert 11 to the queue. Then queue status will be:

0        1         2        3         4

RE A R = RE A R + 1 = 1 F RO NT  = 0

F         R

Next, insert 22 to the queue. Then the queue status is:

0        1         2        3         4

11 22

RE A R = RE A R + 1 = 2 F RO NT  = 0

             

F                   R

Again insert another element 33 to the queue. The status of the queue is:

0        1         2        3         4

11 22 33

RE A R = RE A R + 1 = 3 F RO NT  = 0

                     

F                             R

Now, delete an element. The element deleted is the element at the front of the queue. So the status of the queue is:

0        1         2        3         4

22 33

RE A R = 3

F RO NT  = F R O NT  + 1 = 1

             

F                   R

Again, delete an element. The element to be deleted is always pointed to by the FRONT pointer. So, 22 is deleted. The queue status is as follows:

0        1         2        3         4

RE A R = 3

F RO NT  = F R O NT  + 1 = 2

    

F        R

Now, insert new elements 44 and 55 into the queue. The queue status is:

0        1         2        3         4

33 44 55

RE A R = 5 F RO NT  = 2

                   

F                          R

Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the rear crossed the maximum size of the queue (i.e., 5). There will be queue full signal. The queue status is as follows:

0        1         2        3         4

33 44 55

RE A R = 5 F RO NT  = 2

                   

F                          R

Now it is not possible to insert an element 66 even though there are two vacant positions in the linear queue. To over come this problem the elements of the queue are to be shifted towards the beginning of the queue so that it creates vacant position at the rear end. Then the FRONT and REAR are to be adjusted properly. The element 66 can be inserted at the rear end. After this operation, the queue status is as follows:

0        1         2        3         4

33 44 55 66

RE A R = 4 F RO NT  = 0

                             

F                                       R

This difficulty can overcome if we treat queue position with index 0 as a position that comes after position with index 4 i.e., we treat the queue as a circular queue.

Procedure for Queue operations using array:

In order to create a queue we require a one dimensional array Q(1:n) and two variables front and rear. The conventions we shall adopt for these two variables are that front is always 1 less than the actual front of the queue and rear always points to the last element in the queue. Thus, front = rear if and only if there are no elements in the queue. The initial condition then is front = rear = 0.

The various queue operations to perform creation, deletion and display the elements in a queue are as follows:

1.                  insertQ(): inserts an element at the end of queue Q.

2.                  deleteQ(): deletes the first element of Q.

3.                  displayQ(): displays the elements in the queue.

Linked List Implementation of Queue: We can represent a queue as a linked list. In a queue data is deleted from the front end and inserted at the rear end. We can perform similar operations on the two ends of a list. We use two pointers front and rear for our linked queue implementation.

Enqueue Operation

Queues  maintain  two  data  pointers, front and rear.  Therefore,  its  operations  are comparatively difficult to implement than that of stacks.

The following steps should be taken to enqueue (insert) data into a queue −

·         Step 1 − Check if the queue is full.

·         Step 2 − If the queue is full, produce overflow error and exit.

·         Step 3 − If the queue is not full, increment rear pointer to point the next empty space.

·         Step 4 − Add data element to the queue location, where the rear is pointing.

·         Step 5 − Return success.

Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen situations.

Algorithm for enqueue Operation

Implementation of enqueue() in C programming language −

Dequeue Operation

Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access. The following steps are  taken  to perform dequeue operation −

·       Step 1 − Check if the queue is empty.

·       Step 2 − If the queue is empty, produce underflow error and exit.

·       Step 3 − If the queue is not empty, access the data where front is pointing.

·       Step 4 − Increment front pointer to point to the next available data element.

·       Step 5 − Return success.

Algorithm for dequeue Operation

Implementation of dequeue() in C programming language −

Implementation in C

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 6

int intArray[MAX]; int front = 0;

int rear = -1;

int itemCount = 0;

int peek(){

return intArray[front];

}

bool isEmpty(){

return itemCount == 0;

}

bool isFull(){

return itemCount == MAX;

}

int size(){

return itemCount;

}

void insert(int data){

if(!isFull()){

if(rear == MAX-1){ rear = -1;

}

intArray[++rear] = data; itemCount++;

}

}

int removeData(){

int data = intArray[front++];

if(front == MAX){ front = 0;

}

itemCount--; return data;

}

int main() {

/* insert 5 items */ insert(3); insert(5); insert(9); insert(1); insert(12);

// front : 0

// rear  : 4

// ------------------

// index : 0 1 2 3 4

// ------------------

// queue : 3 5 9 1 12 insert(15);

// front : 0

// rear  : 5

// ---------------------

// index : 0 1 2 3 4  5

// ---------------------

// queue : 3 5 9 1 12 15

if(isFull()){

printf("Queue is full!\n");

}

// remove one item

int num = removeData();

printf("Element removed: %d\n",num);

// front : 1

// rear  : 5

// -------------------

// index : 1 2 3 4  5

// -------------------

// queue : 5 9 1 12 15

// insert more items insert(16);

// front : 1

// rear  : -1

// ----------------------

// index : 0  1 2 3 4  5

// ----------------------

// queue : 16 5 9 1 12 15

// As queue is full, elements will not be inserted. insert(17);

insert(18);

// ----------------------

// index : 0  1 2 3 4  5

// ----------------------

// queue : 16 5 9 1 12 15 printf("Element at front: %d\n",peek());

printf("----------------------\n");

printf("index : 5 4 3 2  1  0\n"); printf("----------------------\n");

printf("Queue:   ");

while(!isEmpty()){

int n = removeData(); printf("%d ",n);

}

}

If we compile and run the above program, it will produce the following result −

Queue is full! Element removed: 3 Element at front: 5

----------------------

index : 5 4 3 2 1 0

---------------------- Queue: 5 9 1 12 15 16

DEQUE(Double Ended Queue):

A double-ended queue (dequeue, often abbreviated to deque, pronounced deck) generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).It is also often called a head-tail linked list. Like an ordinary queue, a double-ended queue is a data structure it supports the following operations: enq_front, enq_back, deq_front, deq_back, and empty. Dequeue can be behave like a queue by using only enq_front and deq_front , and behaves like a stack by using only enq_front and deq_rear.

The DeQueue is represented as follows.

DEQUE can be represented in two ways they are

1)  Input restricted DEQUE(IRD)

2)  output restricted DEQUE(ORD)

The output restricted DEQUE allows deletions from only one end and input restricted DEQUE allow insertions at only one end. The DEQUE can be constructed in two ways they are

1)  Using array 2)Using linked list

Operations in DEQUE

1.       Insert element at back

2.       Insert element at front

3.       Remove element at front

4.       Remove element at back

Applications of DEQUE:

1.       The A-Steal algorithm implements task scheduling for several processors (multiprocessor scheduling).

2.       The processor gets the first element from the deque.

3.       When one of the processor completes execution of its own threads it can steal a thread from another processor.

4.       It gets the last element from the deque of another processor and executes it.

Circular Queue:

Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node is connected back to the first node to make a circle.

·         Circular linked list fallow the First In First Out principle

·         Elements are added at the rear end and the elements are deleted at front end of the queue

·         Both the front and the rear pointers points to the beginning of the array.

·         It is also called as “Ring buffer”.

·         Items can inserted and deleted from a queue in O(1) time. Circular Queue can be created in three ways they are

1.       Using single linked list

2.       Using double linked list

3.       Using arrays

Representation of Circular Queue:

Let us consider a circular queue, which can hold maximum (MAX) of six elements. Initially the queue is empty.

F   R

1                               Q u e u e  E mp t y

4                                                                                   M A X = 6

F RO N T  = RE A R = 0 C O U N T  = 0

C irc u l ar Q u e u e

Now, insert 11 to the circular queue. Then circular queue status will be:

F

R

F RO NT  = 0

4                                                                                   RE A R = ( RE A R + 1) % 6 = 1

C O U NT  = 1

C irc u l ar Q u e u e

Insert new elements 22, 33, 44 and 55 into the circular queue. The circular queue status is:

F

R

0

5

11

4      55

3

44          33

22      1

2

F RO NT  = 0, RE A R = 5 RE A R = RE A R % 6 = 5 C O U NT  = 5

C irc u l ar Q u e u e

Now, delete an element. The element deleted is the element at the front of the circular queue. So, 11 is deleted. The circular queue status is as follows:

R

F

F RO NT  = ( F R O NT  + 1) % 6 = 1

4                                                                                   RE A R = 5

C O U NT  = C O U NT - 1 = 4

C irc u l ar Q u e u e

Again, delete an element. The element to be deleted is always pointed to by the FRONT pointer. So, 22 is deleted. The circular queue status is as follows:

R

F RO NT  = ( F R O NT  + 1)  % 6 = 2

4                                                                                   RE A R  = 5

C O U NT  = C O U NT - 1 = 3

F

C irc u lar Q u e u e

Again, insert another element 66 to the circular queue. The status of the circular queue is:

R

4                                                                                   F RO NT  = 2

RE A R = ( RE A R + 1) % 6 = 0 C O U NT  = C O U NT  + 1 = 4

F

C irc u l ar Q u e u e

Now, insert new elements 77 and 88 into the circular queue. The circular queue status is:

0

5

66      77

4    55

3

88    1

44        33 

2           R

F