# Study notes for Queues

By Mukesh Kumar|Updated : July 28th, 2021

It is a non-primitive, linear data structure in which elements are added/inserted at one end (called the REAR) and elements are removed/deleted from the other end (called the FRONT). A queue is logically a FIFO (First in First Out) type of list.

### Operations on Queue

• Enqueue: Adds an item onto the end of the queue ENQUEUE(Q, i); Adds the item i onto the end of queue.
• Dequeue: Removes the item from the front of the queue. DEQUEUE (Q); Removes the first element and returns it as a function value.

### Queue Implementation

Queue can be implemented in two ways.
• Static implementation (using arrays)
• Dynamic implementation (using linked lists)

### Queue Implementation Using Arrays

void enqueue()
{
int element;
if(rear==max)
{
printf("\nOverflow!!");
}
else
{
printf("\nEnter Element:");
scanf("%d",&element);
queue[rear++]=element;
printf("\n %d Enqueued at %d",element,rear);
}
}

void dequeue()
{
if(rear==front)
{
printf("\nUnderflow!!");
}
else
{
front++;
printf("\nElement is Dequeued from %d",front);
}
}

### Queue Implementation Using Linked Lists

typedef struct qnode
{
int data;
}node;

node *front=NULL;
node *rear=NULL;

void enqueue()
{
int item;
node *temp;
printf("Enter the item\n");
scanf("%d",&item);
temp=(node*)malloc(sizeof(node));
temp->data=item;
if(rear==NULL)
{
front=temp;
rear=temp;
}
else
{
rear=temp;
}
}

void dequeue()
{
int item;
if(front==NULL)
printf("Queue is empty\n");
else
{
item=front->data;
printf("The element deleted = %d\n",item);
}
if(front==rear)
{
front=NULL;
rear=NULL;
}
else
}

### Circular Queue

In a circular queue, the first element comes just after the last element or a circular queue is one in which the insertion of a new element is done at the very first location of the queue, if the last location of queue is full and the first location is empty.

Note: A circular queue overcomes the problem of un-utilized space in linear queues implemented as arrays. We can make following assumptions for circular queue.
• If : (Rear+1) % n == Front, then queue is Full
• If Front = Rear, the queue will be empty.
• Each time a new element is inserted into the queue, the Rear is incremented by 1. Rear = (Rear + 1) ) % n
• Each time, an element is deleted from the queue, the value of Front is incremented by one. Front = (Front + 1) % n

### Double Ended Queue

It is a list of elements in which insertion and deletion operations are performed from both the ends. That is why it is called double-ended queue.

### Priority Queues

This type of queue enables us to retrieve data items on the basis of priority associated with them. Below are the two basic priority queue choices.

### Applications of Queue

• Breadth first Search can be implemented.
• CPU Scheduling
• Handling of interrupts in real-time systems
• Routing Algorithms
• Computation of shortest paths
• Computation a cycle in the graph

### Some examples on QUEUE :

#### 1. Reversing the Queue Q using the Stack S

void reverse( Queue ∗Q)
{
Stack S ; // Empty Stack S is created
while ( ! isEmpty (Q) )
{
S.push(&S , deQueue (Q ) ) ;
}
while ( ! isEmpty(&S ) )
{
enQueue (Q, pop(&S ) ) ;
}
}

#### 2. Find the effect of the following code with Circular Queue Q having locations from 0 to 6.

for (int k = 1; k <= 7; k++)
Q.enqueue(k);
for (int k = 1; k <= 4; k++)
{
Q.enqueue(Q.dequeue());
Q.dequeue();
}

Answer: After the above code execution on empty queue will result the following elements.
• 3 is stored at location 1,
• 5 is stored at location 2, and
• 7 is stored at location 3.

### Implementation of Queue Using Two Stacks

Method 1: Let S1 and S2 be the two stacks to be used in the implementation of queue Q.

Enqueue(int a)
S1.push(a);
}

int Dequeue( )
{
if (S1 is empty)
return(error);
while(S1 is not empty)
{
S2.push(S1.pop());
}
r = S2.pop();
while(S2 is not empty)
{
S1.push(S2.pop());
}
return(r);
}

Method2: Let S1 and S2 be the two stacks to be used in the implementation of queue Q.

Enqueue(int a)
{
S1.push(a);
}

int dequeue( )
{
if (S1 is empty & S2 is empty)
return(error);
if (S2 is empty)
{
while(S1 is not empty)
{
S2.push(S1.pop());
}
}
return(S2.pop());
}

### Implementation of Stack Using two Queues

Method 1: Let Q1 and Q2 be two queues.
• push:
• Enqueue in queue1
• pop:
• while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
• Dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Push is constant time but Pop operation is O(n) time

void push(int data)

{
Enqueue(Q1, data)
}
int pop()

{
int returnValue =-1; // indicate Stack Empty.
while(!isEmpty(Q1))
{
returnValue = Dequeue(Q1);
// If it was last element of queue1. return it.
if(isEmpty(Q1))
break;
else
Enqueue(Q1, returnValue);
}
// swap the names of queue1 and queue2.
// If swapping is not possible then we will have to move all the elements from queue2 to queue1

// or have another flag to indicate the active queue.
Node * temp = Q1;
Q1 = Q2;
Q2 = temp;
return Value;
}

Method 2:
• push:
• Enqueue in queue2
• Enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2
• pop:
• Deqeue from queue1

Pop is constant time but Push operation is O(n) time

void push(int data)

{
Enqueue(Q2, data);
while(!isEmpty(Q1))

{
Enqueue(Q2, Dequeue(Q1));
}
// swap the names of queue1 and queue2.
// If swapping is not possible then we will have to move all the elements from queue2 to queue1
// or have another flag to indicate the active queue.
Node * temp = Q1;
Q1 = Q2;
Q2 = temp;

}

int pop()

{
return Dequeue(Q1);
}

### Applications of Queue:

BFS using queue:

• Queues operate on a first in, first out (FIFO) principle of item access. It is like a standard line at the grocery story. Anyone that enters the line will be served in the order in which they entered.
• When enqueue is performed, element is pushing the element onto the array (think of this as getting in line at the store).
• When an element is dequeued, it is removed from the queue, and the next element is then ready to be dequeued (ie. you check out of the grocery line, and the next customer is ready to be served at the register).

Priority Queue

• A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority.
• If elements with the same priority occur, they are served according to their order in the queue. GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com