QUEUE

Queue
• A queue is a linear list of elements in which insertions can take
place at one end called the rear of the queue, and deletion can
take place only at other end, called the font of the queue.
• Queues are also called the FIFO lists (First In First Out) since first
element in queue is the first element out of the queue.
• An important example of a queue in computer science occurs in
time sharing systems in which programs with same priority form a
queue while waiting to be executed.
• Queues may be represented in computer in various ways, usually
by means of one-way lists or linear arrays
• Queue is a linear data structure that follows FIFO
(First In First Out) Principle, so the first
element inserted is the first to be popped out.

FIFO Principle in Queue:

• FIFO Principle states that the first element added
to the Queue will be the first one to be removed or
processed. So, Queue is like a line of people
waiting to purchase tickets, where the first person
in line is the first person served. (i.e. First Come
• Basic Terminologies of Queue
• Front: Position of the entry in a queue ready to be
served, that is, the first entry that will be removed
from the queue, is called the front of the queue. It
is also referred as the head of the queue.
• Rear: Position of the last entry in the queue, that
is, the one most recently added, is called
the rear of the queue. It is also referred as
the tail of the queue.
• Size: Size refers to the current number of
elements in the queue.
 Queue Operations
[Link]: Adds an element to the end (rear) of
the queue. If the queue is full, an overflow error
occurs.
[Link]: Removes the element from the front of
the queue. If the queue is empty, an underflow
error occurs.
[Link]/Front: Returns the element at the front
without removing it.
[Link]: Returns the number of elements in the
queue.
[Link]: Returns true if the queue is empty,
Complexity Analysis of Operations on Queue
Operations Time Complexity Space Complexity
enqueue O(1) O(1)

dequeue O(1) O(1)

front O(1) O(1)

size O(1) O(1)

isEmpty O(1) O(1)

isFull O(1) O(1)

 Circular Queue Data Structure

• A circular queue is the extended version of a regular queue where

the last element is connected to the first element. Thus forming a
circle-like structure.
 Applications of Queue

Queue is used when things don’t have to be processed

immediately, but have to be processed in First In First Out
order .This property of Queue makes it also useful in following kind
of scenarios.

• When a resource is shared among multiple consumers. Examples

include CPU scheduling, Disk Scheduling.

• When data is transferred asynchronously (data not necessarily

received at same rate as sent) between two processes. Examples
include IO Buffers, file IO, etc.
• Advantages of Queue:
• A large amount of data can be managed efficiently
with ease.
• Operations such as insertion and deletion can be
performed with ease as it follows the first in first
out rule.
• Queues are useful when a particular service is
• Disadvantages of Queue:
• No Random Access: Unlike arrays, you cannot access or modify an element in the middle of a
queue without first removing all the preceding elements. This makes searching for a specific
item inefficient, requiring a linear scan of the entire structure.
• Inefficient for Certain Operations: Operations that require accessing or manipulating elements
at arbitrary positions are cumbersome and computationally expensive with a queue.
• Overflow: If the number of elements exceeds the predefined size, the queue becomes full, and
no more elements can be added. This can result in data loss if not handled properly
• Underutilization of Memory: If the number of elements is significantly smaller than the array's
capacity, a large portion of the allocated memory remains unused, leading to inefficient memory
usage
• Not Ideal for Reversing or Sorting: Tasks that involve reversing the order of elements or sorting
them are not efficiently handled by a queue's inherent structure. Other data structures like
stacks or arrays are better suited for these operations.
 Implementation of Queue:

• Sequential allocation: A queue can be implemented

using an array. It can organize a limited number of
elements.

• Linked list allocation: A queue can be implemented

using a linked list. It can organize an unlimited number of
elements.
 Representing a Queue Using an Array
A Queue is maintained by a linear array queue and two pointer variables: FRONT, containing the
location of front element of the queue and REAR, containing the location of rear element of the
queue. The condition FRONT=NULL indicates that queue is empty. Whenever an element is
deleted from the queue, the value of FRONT is increased by 1. Similarly, whenever an element
is added to queue, the value of REAR is increased by 1.

Queue as a circular queue

It can be seen that after N insertions in a Queue represented by an array of N elements, the
rear element of Queue will occupy last part of array. This occurs even though the queue itself
may not contain many elements. Now, if we want to insert an element ITEM into a queue, we
have to move or rearrange the elements of entire queue to the beginning of the queue. This
procedure may be very expensive. Another method to do so is to represent a queue as a
circular queue i,e QUEUE[1] comes after QUEUE[N] in array. With this assumption, we insert
ITEM into queue by assigning ITEM to QUEUE[1]. Thus instead of increasing REAR to N+1, we
reset REAR=1 and then assign
QUEUE[REAR]=ITEM
Similarly, If FRONT=N and an element of QUEUE is deleted, we reset FRONT=1 instead of
increasing FRONT to N+1
• Suppose a circular queue of capacity (n – 1) elements is
implemented with an array of n elements. Assume that the
insertion and deletion operation are carried out using REAR
and FRONT as array index variables, respectively. Initially, REAR
= FRONT = 0. The conditions to detect queue full and queue
empty are:
• Full: (REAR+1) mod n== FRONT
• Empty: REAR== FRONT=0
 Algorithm for Inserting in a QUEUE
• Algorithm: QINSERT(QUEUE, N, FRONT, REAR,ITEM)
This algorithm inserts an element in a linear queue
• Step 1:[Queue already filled]
If REAR=N, then:
Write: ‘OVERFLOW’
Return
• Step 2: If FRONT=0, then: [Queue initially empty]
Set FRONT:=1 and REAR:=1
Else:
Set REAR:=REAR+1
[End of If structure]
• Step 3: Set QUEUE[REAR]:=ITEM
• Step 4: Return
• Algorithm: QDELETE(QUEUE,N,FRONT,REAR,ITEM)
• This algorithm deletes an element from a queue
• Step 1: If FRONT=0, then:
Write: ‘UNDERFLOW’
Return
• Step 2: Set ITEM:=QUEUE[FRONT]
• Step 3: If FRONT=REAR, then: [Empty Queue]
Set FRONT:=0 and REAR:=0
Else:
Set FRONT:=FRONT+1
[End of If structure]
• Step 4: Return
The circular queue solves the major limitation of
the normal queue. In a normal queue, after a bit of
insertion and deletion, there will be non-usable
empty space.
Algorithm: QINSERT(QUEUE, N, FRONT, REAR,ITEM)
This algorithm inserts an element in a circular queue
• Step 1:[Queue already filled]
If FRONT=1 and REAR=N or FRONT=REAR+1, then:
Write: ‘OVERFLOW’
Return
• Step 2: If FRONT=0, then: [Queue initially empty]
Set FRONT:=1 and REAR:=1
Else If REAR=N, then:
Set REAR:=1
Else:
Set REAR:=REAR+1
[End of If structure]
• Step 3: Set QUEUE[REAR]:=ITEM
• Step 4: Return
• Algorithm: QDELETE(QUEUE,N,FRONT,REAR,ITEM)
• This algorithm deletes an element from a circular
queue
• Step 1: If FRONT=0, then:
Write: ‘UNDERFLOW’
Return
• Step 2: Set ITEM:=QUEUE[FRONT]
• Step 3: If FRONT=REAR, then: [Empty Queue]
Set FRONT:=0 and REAR:=0
Else If FRONT=N, then:
Set FRONT:=1
Else:
Set FRONT:=FRONT+1
[End of If structure]
• Step 4: Return
• Consider the following queue of characters where QUEUE is
a circular array which is allocated six memory cells
FRONT=2, REAR=4 QUEUE: _ A C D _ _
Describe the queue as following operations take place:
(a) F is added to queue
(b) Two letters are deleted
(c) K , L and M are added
(d) Two letters are deleted
(e) R is added to queue
(f) Two letters are deleted
(g) S is added to queue
(h) Two letters are deleted
(i) One letter is deleted
(j) One letter is deleted
• Solution:
(a) FRONT=2, REAR=5 QUEUE: _ A C D F_
(b) FRONT=4, REAR=5 QUEUE: _ _ _ D F _
(c) REAR=2, FRONT=4 QUEUE: L M _ D F K
(d) FRONT=6, REAR=2 QUEUE: L M _ _ _ K
(e) FRONT=6, REAR=3 QUEUE: L M R_ _ K
(f) FRONT=2, REAR=3 QUEUE: _M R _ _ _
(g) REAR=4, FRONT=2 QUEUE: _ M R S _ _
(h) FRONT=4, REAR=4 QUEUE: _ _ _ S _ _
(i) FRONT=REAR=0 [ As FRONT=REAR, queue is empty]
(j) Since FRONT=NULL, no deletion can take place. Underflow
occurred
 Linked representation of the Queue
• A linked queue is a queue implemented as a linked list with two
pointer variables FRONT and REAR pointing to the nodes in the front
and rear of the queue. The INFO field of list hold the elements of the
queue and LINK field holds pointer to neighboring element of queue.
• In case of insertion in linked queue, a node borrowed from AVAIL list
and carrying the item to be inserted is added as the last node of
linked list representing the queue. Rear pointer is updated to point to
last node just added to the list
• In case of deletion, first node of list pointed to by FRONT is deleted
and FRONT pointer is updated to point to next node in the list.
• Unlike the array representation, linked queue functions as a linear
queue and there is no need to view it as circular for efficient
management of space.
Algorithm:LINKQINSRT(INFO,LINK,FRONT,REAR,AVAIL,ITEM)
This algorithm inserts an item in linked list implementation of
the queue
Step 1: If AVAIL=NULL,then:
Write: ‘OVERFLOW’
Return
Step 2: Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
Step 3: Set INFO[NEW]:=ITEM and LINK[NEW]:=NULL
Step 4: If FRONT=NULL, then:
Set FRONT=REAR=NEW
Else:
Set LINK[REAR]:=NEW and REAR:=NEW
Step 5: Return
Algorithm: LINKQDEL(INFO,LINK,FRONT,AVAIL,ITEM)
This algorithm deletes an element from the front of the queue
• Step 1: If FRONT=NULL,then:
Write:’UNDERFLOW’
Return
• Step 2: Set TEMP:=FRONT
• Step 3: Set ITEM:=INFO[FRONT]
• Step 4: Set FRONT:=LINK[FRONT]
• Step 5: Set LINK[TEMP]:=AVAIL and AVAIL:=TEMP
• Step 6: Return
• DEQUE(Double ended Queue)- A deque is a queue in which
elements can be added or removed at either end but not in the
middle. A deque is usually maintained by a circular array DEQUE with
pointers LEFT and RIGHT, which point to two ends of deque. The
elements extend from LEFT end to RIGHT end of deque. The term
circular comes from the fact that DEQUE[1] comes after DEQUE [N].
The condition LEFT=NULL will be used to indicate that a deque is
empty.
• There are two variations of a deque
• Input-restricted deque- It is a deque which allows insertions at only
one end of list but allows deletions at both ends of the list
• Output-restricted deque- It is a deque which allows deletions at only
one end of list but allows insertions at both ends of list
• Consider the following deque of characters where DEQUE is a circular array which is allocated six memory
cells.
LEFT=2, RIGHT=4 DEQUE: _ A,C,D, _ , _
• Describe deque while the following operation take place
(a) F is added to right of deque
LFET=2, RIGHT=5 _A C D F _
(b) Two letters on right are deleted
LEFT=2 RIGHT=3 _A C _ _ _
(c) K,L and M are added to the left of the deque
LEFT=5 RIGHT=3 KAC_ML
(d) One letter on left is deleted.
LEFT=6 RIGHT=3 KAC__L
(e) R is added to the left of deque.
LEFT=5 RIGHT= 3 KAC_RL
(f) S is added to right of deque
LEFT=5 RIGHT= 4 KACSRL
(g) T is added to the right of deque
Since LEFT= RIGHT+1, the array is full and hence T cannot be added to the deque
• Priority Queue- A priority queue is a collection of elements
such that each element has been assigned a priority and
such that the order in which elements are deleted and
processed comes from following rules:
• An element of higher priority is processed before any
element of lower priority
• Two elements of same priority are processed according to
the order in which they were added to queue
• An example of a priority queue is a time sharing system.
Programs of higher priority are processed first and
programs with same priority form a standard queue
 One-way list representation of a priority queue

• One way to maintain a priority queue in memory is by means of a

one-way list

• Each node in list will contain three items of information: an

information field INFO, a priority number PRN and a link field LINK

• A node X precedes a node Y in list

– If X has higher priority than Y

– Or when both have same priority but X was added to list before Y
 • Another way to maintain a priority queue in memory is to use a separate queue for
each level of priority . Each such queue will appear in its own circular array and
must have its own pair of pointers, FRONT and REAR.
• If each queue is allocated the same amount of space, a two dimensional array
QUEUE can be used instead of the linear arrays for representing a priority queue. If
K represents the row K of the queue, FRONT[K] and REAR[K] are the front and rear
indexes of the Kth row.
1 2 3 4 5 6
1 AAA
2 BBB CCC XXX
Priority

3
4 FFF DDD EEE
5 GGG
Complexity of Stack and Queue operations

• Stack push and pop operations are performed at

only one end of stack, i.e top of stack. Thus, both
the operations are O(1) as the size of stack has no
effect on the time of execution

• Queue insert and delete operations are done at rear

and front of queue respectively. Thus, they also are
O(1)
 Difference between stack and queue
Feature Stack Queue

A linear data structure that follows the Last In First Out A linear data structure that follows the First In First Out
Definition
(LIFO) principle. (FIFO)principle.

Primary Enqueue (add an item), Dequeue (remove an item), Front (view the
Push (add an item), Pop (remove an item), Peek (view the top item)
Operations first item), Rear (view the last item)

Insertion/
Elements are added and removed from the same end (the top). Elements are added at the rear and removed from the front.
Removal

Function call management (call stack), expression evaluation and Scheduling processes in operating systems, managing requests in a
Use Cases
syntax parsing, undo mechanisms in text editors. printer queue, breadth-first search in graphs.

Examples Browser history (back button), reversing a word. Customer service lines, CPU task scheduling.

Real-World A queue at a ticket counter: the first person in line is the first to be
A stack of plates: you add and remove plates from the top.
Analogy served.

Complexity
Push: O(1), Pop: O(1),Peek: O(1) Enqueue: O(1), Dequeue: O(1), Front: O(1), Rear: O(1)
(Amortized)

Memory
Typically uses a contiguous block of memory or linked list. Typically uses a circular buffer or linked list.
Structure

Implementation Can be implemented using arrays or linked lists. Can be implemented using arrays, linked lists, or circular buffers.