Experiment No - 4
QUEUE
Objectives:
To understand the abstract data types queue and deque.
To understand the performance of the implementations of basic linear data structures.
To use queues for basic timing simulations.
To be able to recognize problem properties where queues require appropriate data
structures.
To be able to implement the abstract data type list as a linked list using the node and
reference pattern.
Queue
Queue is a linear data structure in which the insertion and deletion operations are
performed at two different ends. In a queue data structure, adding and removing elements are
performed at two different positions. The insertion is performed at one end and deletion is
performed at another end. In a queue data structure, the insertion operation is performed at a
position which is known as 'rear' and the deletion operation is performed at a position which
is known as 'front'. In queue data structure, the insertion and deletion operations are
performed based on FIFO (First In First Out) principle.
In a queue data structure, the insertion operation is performed using a function called
"enQueue()" and deletion operation is performed using a function called "deQueue()".
Types of Queue
Single Ended Queue
Double Ended Queue
Circular Queue
Common Queue Operations
enqueue() – Insert an element at the end of the queue.
dequeue() – Remove and return the first element of the queue, if the queue is not empty.
peek() – Return the element of the queue without removing it, if the queue is not empty.
size() – Return the number of elements in the queue.
isEmpty() – Return true if the queue is empty, otherwise return false
isFull() – Return true if the queue is full, otherwise return false.
Algorithm for Enqueue Operation
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.
Algorithm for Dequeue Operation
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.
peek ()
This function helps to see the data at the front of the queue. The algorithm of peek()
function is as follows
Algorithm
begin procedure peek
return queue[front]
end procedure
isfull ()
check for the rear pointer to reach at MAXSIZE to determine that the queue is full.
Algorithm
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
isempty()
Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
Circular Queue
Circular Queue is a linear data structure in which first position of the queue is
connected with last position of the queue.
Illustration of Enqueue and Dequeue
Conditions used in Circular Queue
Front must point to the first element.
The queue will be empty if Front = Rear.
When a new element is added the queue is incremented by value one(Rear = Rear +
1).
When an element is deleted from the queue the front is incremented by one (Front =
Front + 1).
Steps Involved in Enqueue
Check whether queue is Full or not by using the following condition
((rear == SIZE-1 && front == 0) || (rear == front-1))
If queue is full, display the queue is full else we can insert an element by
incrementing rear pointer.
Steps Involved in Dequeue
Check whether queue is Empty or not by using the following condition
if(front==-1).
If it is empty then display Queue is empty, else we can delete the element.
Priority Queue
• Priority Queue is an extension of a queue with following properties.
• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low priority.
• If two elements have the same priority, they are served according to their order in the
queue.
Operations Involved
insert(item, priority): Inserts an item with given priority.
getHighestPriority(): Returns the highest priority item.
pull_highest_priority_element: remove the element from the queue that has the
highest priority, and return it.
Insertion
Ask the data and its priority from the user.
If front is equal to 0 and rear is equal to n-1 then Queue is full.
o Else if front is equal to the -1 them queue is empty so we have initialize front
and rear with 0.
Insert the data entered by user in Queue using rear.
If rear is equal to n-1 and front is not equal to 0 then there is empty space in queue
before the front for using that space we will shift the elements of the queue with the
help of front and rear.
Insert the data in the queue before at the position where given priority is greater
then priority of the element in queue.
Deletion
Remove the element and the priority from the front of the queue.
Increase front with 1.
Print
Using loop take the starting point from the front of the queue and ending point from
the rear of the queue and print the data.
Double Ended Queue
• Double Ended Queue is also a Queue data structure in which the insertion and
deletion operations are performed at both the ends (front and rear).
Double Ended Queue can be represented inTWO ways
• Input Restricted Double Ended Queue
• Output Restricted Double Ended Queue
•
Input Restricted Double Ended Queue
In input restricted double ended queue, the insertion operation is performed at only one end
and deletion operation is performed at both the ends.
Output Restricted Double Ended Queue
In output restricted double ended queue, the deletion operation is performed at only one end
and insertion operation is performed at both the ends.
There are four basic operations in usage of Deque
Insertion at rear end
Insertion at front end
Deletion at front end
Deletion at rear end
Algorithm for Insertion at rear end
Step-1: [Check for overflow]
if(rear==MAX)
Print("Queue is Overflow”);
return;
Step-2: [Insert Element]
else
rear=rear+1;
q[rear]=no;
[Set rear and front pointer]
if rear=0
rear=1;
if front=0
front=1;
Step-3: return
Algorithm for Insertion at front end
Step-1 : [Check for the front position]
if(front<=1)
Print("Cannot add item at the front”);
return;
Step-2 : [Insert at front]
else
front=front-1;
q[front]=no;
Step-3 : Return
Algorithm for Deletion from front end
Step-1 [ Check for front pointer]
if front=0
print(" Queue is Underflow”);
return;
Step-2 [Perform deletion]
else
no=q[front];
print(“Deleted element is”,no);
[Set front and rear pointer]
if front=rear
front=0;
rear=0;
else
front=front+1;
Step-3 : Return
Algorithm for Deletion from rear end
Step-1 : [Check for the rear pointer]
if rear=0
print(“Cannot delete value at rear end”);
return;
Step-2: [ perform deletion]
else
no=q[rear];
[Check for the front and rear pointer]
if front= rear
front=0;
rear=0;
else
rear=rear-1;
print(“Deleted element is”,no);
Step-3 : Return
Applications of Queue
Queue, as the name suggests is used whenever we need to manage any group of objects in an
order in which the first one coming in, also gets out first while the others wait for their turn,
like in the following scenarios:
1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life scenario, Call Center phone systems uses Queues to hold people calling
them in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same
order as they arrive i.e First come first served.
4. Breadth First Search Traversal
5. Level Order Traversal of a tree
Pre-Lab:
1. What is queue data structure?
2. What are the basic operations of queue?
3. What are the types of queue?
Post-Lab:
1. Write an C program to delete an item from a queue.
2. Write an C program to search an element in a queue.
Sample Problem Statements:
1. Your task is to construct a tower in N days by following these conditions:
* Every day you are provided with one disk of distinct size.
* The disk with larger sizes should be placed at the bottom of the tower.
* The disk with smaller sizes should be placed at the top of the tower.
The order in which tower must be constructed is as follows:
* You cannot put a new disk on the top of the tower until all the larger disks that are given to
you get placed.
Print N lines denoting the disk sizes that can be put on the tower on the ith day.
Constraints:
1<N<10^6
1<size < N
Input format
« First line: N denoting the total number of disks that are given to you in the N subsequent
days
* Second line: N integers in which the ith integers denote the size of the disks that are given
to you on
the ith day
Note: All the disk sizes are distinct integers in the range of 1 to N.
Output format
Print N lines. In the ith line, print the size of disks that can be placed on the top of the tower
in descending
order of the disk sizes.
If on the ith day no disks can be placed, then leave that line empty.
Logical Test Cases:
Test Case 1
INPUT (STDIN)
5
54327
EXPECTED OUTPUT
5
4
3
2
Test Case 2
INPUT (STDIN)
8
97532685
EXPECTED OUTPUT
8765
Solution:
#include<stdio.h>
int main()
{
long int disk,temp[1000]={0},size,i,max;
scanf("%ld",&disk);
max=disk;
for(i=0;i<disk;i++)
{
scanf("%ld",&size);
temp[size]=size;
if(size==max)
{
while(temp[size])
{
printf("%ld ",temp[size]);
size--;
}
max=size;
printf("\n");
}
else
printf("\n");
}
return 0;
}
2. Umesh is an DS expert training youngsters struggling in DS to make them better. Umesh
usually gives interesting problems to the youngsters to make them love the DS. One such day
Umesh provided to the youngsters to solve the task such that, Reverse a Queue, Queue data
structures work on the FIFO architecture so the element that has entered first in the list will
go out from the list first.
Youngsters were lacking the idea to solve the problem.
Being an exciting youngster can you solve it?
Function Description
INITIALIZE FRONT AND REAR = -1
CALL ENQUEUE FUNCTION WHILE(I<GIVEN SIZE OF QUEUE)
CALL REVERSE
MAKE A FOR LOOP(I=FRONT,J=REAR}I<J ; I++;J++)
SWAP(FRONT,REAR)
Constraints:
O<size <100
O<data<1000
Input format:
First line indicates the size of the queue
Second line indicates the elements of the queue.
Output Format:
first line indicates the enqueue of each element
last line indicates the reversed queue elements.
Solution:
#include <stdio.h>
#define SIZE 50
void enqueue(int,int);
void display();
void reverse();
int items[SIZE], front = -1, rear = -1;
int main() {
int n,t,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&t);
enqueue(t,n);
}
printf("Queue:");
display();
reverse();
printf("\nReversed Queue:");
display();
return 0;
}
void reverse(){
int i,j,temp;
for(i=front,j=rear;i<j;i++,j--){
temp=items[i];
items[i]=items[j];
items[j]=temp;
}
}
void enqueue(int data,int l) {
if (rear == l - 1)
printf("Queue is Full!!");
else {
if (front == -1)
front = 0;
rear++;
items[rear] = data;
// printf("Enqueuing %d\n", data);
}
}
void display() {
if (rear == -1)
printf("\nQueue is Empty!!!");
else {
int i;
for(i=front;i<=rear;i++)
printf("%d ", items[i]);
}
}
Result: