Queue
A queue is linear data structure and collection of elements. 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. The principle of
queue is a “FIFO” or “First-in-first-out”. Queue is an abstract data structure. A queue is a useful data
structure in programming. It is similar to the ticket queue outside a cinema hall, where the first person
entering the queue is the first person who gets the ticket. A real-world example of queue can be a single-lane
one-way road, where the vehicle enters first, exits first.
Operations on QUEUE:
A queue is an object or more specifically an abstract data structure (ADT) that allows the
following operations:
Enqueue or insertion: which inserts an element at the end of the queue.
Dequeue or deletion: which deletes an element at the start of the queue.
Queue operations work as follows:
1. Two pointers called FRONT and REAR are used to keep track of the first and last
elements in the queue.
2. When initializing the queue, we set the value of FRONT and REAR to 0.
3. On enqueing an element, we increase the value of REAR index and place the new
element in the position pointed to by REAR.
4. On dequeueing an element, we return the value pointed to by FRONT and increase
the FRONT index.
5. Before enqueing, we check if queue is already full.
6. Before dequeuing, we check if queue is already empty.
7. When enqueing the first element, we set the value of FRONT to 1.
8. When dequeing the last element, we reset the values of FRONT and REAR to 0.
Representation of Queue (or) Implementation of Queue:
The queue can be represented in two ways:
1. Queue using Array
2. Queue using Linked List
1. Queue using Array:
Let us consider a queue, which can hold maximum of five elements. Initially the queue is
empty.
Now, insert 11 to the queue. Then queue status will be:
Next, insert 22 to the queue. Then the queue status is:
Again insert another element 33 to the queue. The status of the queue is:
Now, delete an element. The element deleted is the element at the front of the [Link]
the status of the queue is:
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:
Now, insert new elements 44 and 55 into the queue. The queue status is:
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:
Now it is not possible to insert an element 66 even though there are two vacant positions in
the linear queue. To overcome 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:
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.
Queue operations using array:
a. enqueue() or insertion():which inserts an element at the end of the queue.
void insertion() Algorithm: Procedure for insertion():
{ Step-1:START
if(rear==max) Step-2: if rear==max then
printf("\n Queue is Full"); Write ‘Queue is full’
else Step-3: otherwise
{ 3.1: read element ‘queue[rear]’
printf("\n Enter no %d:",j++); Step-4:STOP
scanf("%d",&queue[rear++]);
}
}
b. dequeue() or deletion(): which deletes an element at the start of the queue.
void deletion() Algorithm: procedure for deletion():
{ Step-1:START
if(front==rear) Step-2: if front==rear then
{ Write’ Queue is empty’
printf("\n Queue is empty"); Step-3: otherwise
} 3.1: print deleted element
else Step-4:STOP
{
printf("\n Deleted Element is
%d",queue[front++]);
x++;
}}
c. display(): which displays an elements in the queue.
void deletion() Algorithm: procedure for deletion():
{ Step-1:START
if(front==rear) Step-2: if front==rear then
{ Write’ Queue is empty’
printf("\n Queue is empty"); Step-3: otherwise
} 3.1 : for i=front to rear then
else 3.2 : print ‘queue[i]’
{ Step-4:STOP
for(i=front; i<rear; i++)
{
printf("%d",queue[i]);
printf("\n");
}
}
}
2. Queue using Linked list:
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 alist. We use
two pointers front and rear for our linked queue implementation.
The linked queue looks as shown in figure:
Applications of Queue:
1. It is used to schedule the jobs to be processed by the CPU.
2. When multiple users send print jobs to a printer, each printing job is kept in the printing
queue. Then the printer prints those jobs according to first in first out (FIFO) basis.
3. Breadth first search uses a queue data structure to find an element from a graph.
CIRCULAR QUEUE
A more efficient queue representation is obtained by regarding the array Q[MAX] as
circular. Any number of items could be placed on the queue. This implementation of a
queue is called a circular queue because it uses its storage array as if it were a circle instead
of a linear list.
There are two problems associated with linear queue. They are:
Time consuming: linear time to be spent in shifting the elements to the beginning of
the queue.
Signaling queue full: even if the queue is having vacant position.
For example, let us consider a linear queue status as follows:
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:
This difficulty can be overcome if we treat queue position with index zero as a position that
comes after position with index four then we treat the queue as a circular queue.
In circular queue if we reach the end for inserting elements to it, it is possible to insert new
elements if the slots at the beginning of the circular queue are empty.
Representation of Circular Queue:
Let us consider a circular queue, which can hold maximum (MAX) of six elements. Initially
the queue is empty.
Now, insert 11 to the circular queue. Then circular queue status will be:
Insert new elements 22, 33, 44 and 55 into the circular queue. The circular queue status is:
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:
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:
Again, insert another element 66 to the circular queue. The status of the circular queue is:
Now, insert new elements 77 and 88 into the circular queue. The circular queue status is:
Now, if we insert an element to the circular queue, as COUNT = MAX we
cannot add the element to circular queue. So, the circular queue is full.
Operations on Circular queue:
a. Enqueue() or insertion():This function is used to insert an element into
the circular queue. In a circular queue, the new element is always
inserted at Rear position.
void insertCQ() Algorithm: procedure of insertCQ():
{
int data; Step-1:START
if(count ==MAX) Step-2: if count==MAX then
{ Write “Circular queue is full”
printf("\n Circular Queue is Full"); Step-3:otherwise
} 3.1 : read the data element
else 3.2 : CQ[rear]=data
{ 3.3 : rear=(rear+1)%MAX
printf("\n Enter data: "); 3.4 : count=count+1
scanf("%d", &data); Step-4:STOP
CQ[rear] = data;
rear = (rear + 1) % MAX;
count ++;
printf("\n Data Inserted in the Circular
Queue ");
}
}
b. Dequeue() or deletion(): This function is used to delete an element
from the circular queue. In a circular queue, the element is always
deleted from front position.
void deleteCQ() Algorithm: procedure of deleteCQ():
{
if(count ==0) Step-1:START
{ Step-2: if count==0 then
printf("\n\nCircular Queue is Empty.."); Write “Circular queue is empty”
} Step-3:otherwise
else 3.1 : print the deleted element
{ 3.2 : front=(front+1)%MAX
printf("\n Deleted element from Circular 3.3 : count=count-1
Queue is %d ", CQ[front]); Step-4:STOP
front = (front + 1) % MAX;
count --;
}
}
c. Display(): This function is used to display the list of elements in the circular queue.
void displayCQ() Algorithm: procedure of displayCQ():
{
int i, j; Step-1:START
if(count ==0) Step-2: if count==0 then
{ Write “Circular queue is empty”
printf("\n\n\t Circular Queue is Empty "); Step-3:otherwise
} 3.1 : print the list of elements
else 3.2 : for i=front to j!=0
{ 3.3 : print CQ[i]
printf("\n Elements in Circular Queue are: 3.4 : i=(i+1)%MAX
"); Step-4:STOP
j = count;
for(i = front; j != 0; j--)
{
printf("%d\t", CQ[i]);
i = (i + 1) % MAX;
}
}
}
Deque (Double Ended Queue)
In the preceding section we saw that a queue in which we insert items at one
end and from which we remove items at the other end. In this section we
examine an extension of the queue, which provides a means to insert and
remove items at both ends of the queue. This data structure is a deque. The
word deque is an acronym derived from double-ended queue. Below figure
shows the representation of a deque.
deque provides four operations. Below Figure shows the basic operations on a deque.
• enqueue_front: insert an element at front.
• dequeue_front: delete an element at front.
• enqueue_rear: insert element at rear.
• dequeue_rear: delete element at rear.
There are two variations of deque. They are:
• Input restricted deque (IRD)
• Output restricted deque (ORD)
An Input restricted deque is a deque, which allows insertions at one end but
allows deletions at both ends of the list.
An output restricted deque is a deque, which allows deletions at one end but
allows insertions at both ends of the list.
Priority Queue
A priority queue is a collection of elements such that each element has been
assigned a priority. We can insert an element in priority queue at the rare
position. We can delete an element from the priority queue based on the
elements priority and such that the order in which elements are deleted and
processed comes from the following rules:
1. An element of higher priority is processed before any element of lower priority.
2. Two elements with same priority are processed according to the order in
which they were added to the queue. It follows FIFO or FCFS(First Comes
First serve) rules.
We always remove an element with the highest priority, which is given by the
minimal integer priority assigned.
A prototype of a priority queue is time sharing system: programs of high
priority are processed first, and programs with the same priority form a
standard queue. An efficient implementation for the Priority Queue is to use
heap, which in turn can be used for sorting purpose called heap sort
Priority queues are two types:
1. Ascending order priority queue
2. Descending order priority queue
1. Ascending order priority queue: It is Lower priority number to high
priority number. Examples: order is 1,2,3,4,5,6,7,8,9,10
2. Descending order priority queue: It is high priority number to lowest
priority number. Examples: Order is 10,9,8,7,6,5,4,3,2,1
Implementation of Priority Queue:
Implementation of priority queues are two types:
1. Through Queue(Using Array)
2. Through Sorted List(Using Linked List)
1. Through Queue (Using Array): In this case element is simply added at
the rear end as usual. For deletion, the element with highest priority is
searched and then deleted.
2. Through sorted List (Using Linked List): In this case insertion is costly
because the element insert at the proper place in the list based on the
priority. Here deletion is easy since the element with highest priority will
always be in the beginning of the list.
Difference between stacks and Queues
stacks Queues
1. stack is a linear list of elements in which 1. A Queue is a linerar list of elements in which
the element may be inserted or deleted at the elements are added at one end and
one end. deletes the elements at another end.
2. . In Queue the element which is inserted
2. In stacks, elements which are inserted first is the element deleted first.
last is the first element to be deleted.
3. Queues are called FIFO (First In First
3. Stacks are called LIFO (Last In First Out)list.
Out)list
4. In Queue elements are removed in the
4. In stack elements are removed in reverse same order in which thy are inserted.
order in which thy are inserted.
5. Suppose the elements a,b,c,d,e are inserted
5. suppose the elements a,b,c,d,e are in the Queue, the deletion of elements will be
inserted in the stack, the deletion of in the same order in which thy are inserted.
elements will be e,d,c,b,a.
6. In Queue there are two pointers one for
6. In stack there is only one pointer to insert insertion called “Rear” and another for
and delete called “Top”. deletion called “Front”.
7. Initially top=-1 indicates a stack is empty. 7. Initially Rear=Front=-1 indicates a Queue is
empty.
8. Stack is full represented by the condition
TOP=MAX-1(if array index starts from ‘0’). 8. Queue is full represented by the condition
Rear=Max-1.
9. To push an element into a stack, Top is
incremented by one 9. To insert an element into Queue, Rear is
incremented by one.
10. To POP an element from stack, top
is decremented by one. 10. To delete an element from Queue,
Front is incremented by one.