Data Structures
Queue and Circular Queue
Instructor: Mr. hassan siddique
Fall 2025
Problem to be Solved
It is so often necessary to wait one’s turn before having access to
something.
We may want to simulate a real life situation of a waiting line, like
A line of people waiting to purchase tickets, where the first person in
line is the first person served.
With in a computer system there may be lines of tasks
Waiting for the printer
Waiting for access to disk storage
Or in a time sharing system for use of the CPU.
The data structures used to solve this type of problems is called
Queue
Queue
A linear list in which items may be added only at one end and
items may be removed-only at the other end
The name "queue" likely comes from the everyday use of the
term e.g. queue at Bus Stop
Another example of a queue is a batch of jobs waiting to be
processed, assuming no job has higher priority than the others
Queue
We define a queue to be a list in which
All additions to the list are made at one end, and
All deletions from the list are made at the other end
Queues are also called First-In, First-Out lists, or FIFO for
short.
The entry in a queue ready to be served, will be
the first entry that will be removed from the queue,
We call this the front of the queue.
The last entry in the queue is the one most recently added,
Queue
Deletion (Dequeue) can take place only at one end, called
the front
Insertion (Enqueue) can take place only at the other end,
called the rear
The general Queue model is
Queue Q
Dequeue( ) Enqueue (x)
5
Graphic Model of Queue
Rear: Front:
All new items All items are
are added on deleted from
this end this end
Applications of Queues
Operating system
Multi-user/multitasking environments, where several users
or task may be requesting the same resource
simultaneously.
Communication Software
Queues to hold information received over networks and dial
up connections. (Information can be transmitted faster than
it can be processed, so is placed in a queue waiting to be
processed)
Some other?
Types of Queues in Data
Structures
Types of Queues in Data
Structures
Simple Queue/Linear Queue: Here, elements are inserted
from one end i.e. rear end, and removed from the other end
i.e. front. It follows the FIFO (First In First Out) order.
Circular Queue: It is similar to a simple queue, but the last
element is connected to the first element, creating a circular
structure. This allows for efficient use of memory.
Priority Queue: It is a special type of queue in which each
element has a priority assigned to it. The element with the
highest priority is removed first. This is useful in situations
where certain elements need to be processed before others.
Dequeue (Double-Ended Queue): In this, the elements
can be added or removed from both ends, front and rear of
the queue.
Common Operations on Queue
Create an empty queue
Destroy a queue
Determine whether a queue is empty
Add a new item to the queue
Remove the item that was added earliest
Common Operations on Queue
MAKENULL(Q): Makes Queue Q be an empty list.
FRONT(Q): Returns the first element on Queue Q.
ENQUEUE(x,Q): Inserts element x at the end of Queue Q.
DEQUEUE(Q): Deletes the first element of Q.
EMPTY(Q): Returns true if and only if Q is an empty
queue.
Representation of Queue
Static
Queue is implemented by an array and
the size of the queue remains fix
Dynamic
A queue can be implemented as a linked list and
expand or shrink with each enqueue or dequeue operation
13
Queue – Array Representation
Maintained by a linear array QUEUE and Two variables:
FRONT containing the location of the front element of the queue;
and
REAR, containing the location of the rear element of the queue
Condition FRONT = -1 will indicate that the queue is empty
whenever an element is deleted from the queue, FRONT = FRONT +
1
whenever an element is added to the queue, REAR = REAR +1
Representation of Queues
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
34 12 53 61 9 23 -8 15 24 42
front rear
Queues Working
Currently Queue Status
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
front = 0 rear = 0
Queues Working
Currently Queue Status
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
32
front
rear QInsert(32)
front = 1 rear = 1
Queues Working
Currently Queue Status
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
32 44
front rear
QInsert(44)
front = 1 rear = 2
Queues Working
Currently Queue Status
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
32 44 65
front rear
QInsert(65)
front = 1 rear = 3
Queues Working
Currently Queue Status
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
32 44 65 25
front rear
QInsert(25)
front = 1 rear = 4
Queues Working
Currently Queue Status
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
32 44 65 25 53
front rear
QInsert(53)
front = 1 rear = 5
Queues Working
Currently Queue Status
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
44 65 25 53
front rear
QDelete()
front = 2 rear = 5
Queues Working
Currently Queue Status
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
65 25 53
front rear
QDelete()
front = 3 rear = 5
Queue using Array
front rear
1 7 5 2
1 7 5 2
0 1 2 3 4 5 6 7
front rear
0 3
Queue using Array
enqueue(6)
front rear
1 7 5 2 6
1 7 5 2 6
0 1 2 3 4 5 6 7
front rear
0 4
Queue using Array
enqueue(8)
front rear
1 7 5 2 6 8
1 7 5 2 6 8
0 1 2 3 4 5 6 7
front rear
0 5
Queue using Array
dequeue()
front rear
7 5 2 6 8
7 5 2 6 8
0 1 2 3 4 5 6 7
front rear
1 5
Queue using Array
dequeue()
front rear
5 2 6 8
5 2 6 8
0 1 2 3 4 5 6 7
front rear
2 5
Queue using Array
enqueue(9)
enqueue(12)
front rear
5 2 6 8 9 12
5 2 6 8 9 12
0 1 2 3 4 5 6 7
front rear
2 7
Algorithms of Insert Operation
QInsert (X)
Algorithm for Insert element into the Queue
1. Start
2. if rear = Max-1 then
Print “Queue Overflow!” and Return
3. if rear = -1 then
rear = front = 0
else
rear = rear + 1
end if
4. Q[rear] = X
5. Return
Algorithms of Delete Operation
QDelete ()
Algorithm for delete element into the Queue
1. Start
2. if front = -1 then
Print “Queue Underflow!” and Return
3. E = Q[front]
4. if front = rear then // one and only element in the queue that
would be deleted
front = rear = -1 // after removing , queue
becomes empty
else
front = front + 1
end if
5. Return
Queue – Linked
Representation
Implementing Queue
Using linked List:
front rear front rear
1 7 5 2 1 7 5 2
Implementing Queue
Using linked List:
front rear front rear
1 7 5 2 1 7 5 2
dequeue()
front rear front rear
7 5 2 1 7 5 2
Implementing Queue
Using linked List:
front rear front rear
1 7 5 2 1 7 5 2
enqueue(9)
front rear front rear
7 5 2 9 7 5 2 9
Enqueue Operation - Algorithm
//(linked list) enqueue:
Make newNode point at a new node allocated
from heap
Copy new data into node newNode
Set newNode's pointer next field to NULL
Set the next in the rear node to point to
newNode
Set rear = newNode;
Implementing Enqueue Operation
void enqueue(int x, Node *rear){
Node* newNode;
newNode = new Node;
newNode->data = x;
newNode->next = NULL;
if (rear == NULL) { // queue is empty
rear = newNode;
front = rear; }
else {
rear->next = newNode;
rear = newNode; }
}
Dequeue Operation - Algorithm
//(linked list) dequeue:
If front is NULL then message “Queue is Empty”
Else
Copy front to a temporary pointer
Set front to the next of the front
Delete the temporary pointer
Implementing Dequeue
Operation
void dequeue(Node *front) {
Node *temp; // temporary pointer
if (front == NULL)
cout<< “Queue is Empty”;
else {
temp = front;
front = front->next;
if (front == NULL)
rear = NULL;
delete temp;
}}
Displaying the Elements of Queue
We can use the following steps to display the elements
(nodes) of a queue...
Step 1 - Check whether queue is Empty (front == NULL).
Step 2 - If it is Empty then, display 'Queue is Empty!!!' and
terminate the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp'
and initialize with front.
Step 4 - Display 'temp → data --->' and move it to the next
node. Repeat the same until 'temp' reaches to 'rear' (temp
→ next != NULL).
Step 5 - Finally! Display 'temp → data ---> NULL'.
Displaying the Elements of
Queue
void Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
Print (‘’Queue is empty“);
while (temp != NULL) {
Print <<temp->data<<" ";
temp = temp->next;
} }
Linear Queue – Array
Representation
After N insertions, the rear element of the queue will occupy QUEUE [N] or,
eventually the queue will occupy the last part of the array
This occurs even through the queue itself may not contain many elements
Suppose we want to insert an element ITEM into a queue at the time the
queue occupies the last part of the array, i.e., when REAR = N and queue has
empty spaces at the start of the queue due to deletion of elements from FRONT
end.
One way to do this is to simply move the entire queue to the beginning of
the array, changing FRONT and REAR accordingly, and then inserting ITEM as above
This procedure may be very expensive. It takes Ω(N) times if the queue has length N
The other way is to insert the new element at first index
by updating REAR =1
Disadvantages of linear queue
On deletion of an element from existing queue, front
pointer is shifted to next position.
This results into virtual deletion of an element.
By doing so memory space which was occupied by
deleted element is wasted and hence inefficient
memory utilization is occur.
Overcome disadvantage of linear queue:
To overcome disadvantage of linear queue, circular queue is
used.
We can solve this problem by joining the front and rear end
of a queue to make the queue as a 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 Queue:
It is also called as “Ring buffer”.
Items can inserted and deleted from a queue in O(1) time.
CIRCULAR QUEUE
A queue, in which the last node is connected back to the first node
to form a cycle, is called as circular queue.
Circular queue are the queues implemented in circular form rather
than in a straight line.
Circular queues overcome the problem of unutilized space in
linear queue implemented as an array.
The main disadvantage of linear queue using array is that when
elements are deleted from the queue, new elements cannot be
added in their place in the queue, i.e. the position cannot be
reused.
CIRCULAR QUEUE IMPLEMENTATION
After rear reaches the last position, i.e. MAX-1 in order to
reuse the vacant positions, we can bring rear back to the 0th
position, if it is empty, and continue incrementing rear in same
manner as earlier.
Thus rear will have to be incremented circularly.
For deletion, front will also have to be incremented
circularly..
Circular queue example
Circular Queue
7 6 12 67
0 1 2 3 4 5 6 7 8
Front=5
Rear=8
Enqueue 39 Rear=(Rear+1) mod Queue Size = (8+1) mod 9 = 0
39 7 6 12 67
0 1 2 3 4 5 6 7 8
Front=5
Rear=0
Queue Using Array
Basic idea is to picture the array as a circular
array.
0 1
front rear front
7 2 2
12 5
5 2 6 8 9 12
6 9 2
8 6 3 rear
7
5 4
Queue Using Array
enqueue(21)
0 1
front rear 21 front size
7 2 2 8
12 5
5 2 6 8 9 12 21
6 9 2
8 6 3 rear noElements
0 7
5 4
void enqueue(int x)
{
rear = (rear+1)%size;
array[rear] = x;
noElements = noElements+1;
}
Queue Using Array
enqueue(7)
0 1
front rear 21 7 front size
7 2 2 8
12 5
5 2 6 8 9 12 21 7
6 9 2
8 6 3 rear noElements
1 8
5 4
int isFull()
{
return noElements == size;
}
int isEmpty()
{
return noElements == 0;
}
Queue Using Array
dequeue()
dequeue()
0 1
front rear 21 7 front size
7 2 4 8
12
6 8 9 12 21 7
6 9
8 6 3 rear noElements
1 6
5 4
int dequeue()
{
int x = array[front];
front = (front+1)%size; //here only making
the circular array
noElements = noElements-1;
return x;
}
Enqueue(Insert) operation on Circular Queue:
Step 1: Check for queue full
If (rear=max–1 and front=0) or if (front=rear+1)
then circular queue is full and insertion operation is not possible.
otherwise go to step 2
Step 2: Check position of rear pointer
If rear=–1
then set rear=front=0
else
rear=(rear+1)%MAX //increment rear by 1.
Step 3: Insert element at the position pointer by rear pointer.
q[rear]=Data
Step 4: Return
Dequeue (Delete) operation on Circular
Queue:
Step 1: Check for queue empty if (front = -1)
then circular queue is empty and deletion operation
is not possible. otherwise go to step 2
Step 2: assign deleted value to Data
Data = q[front];
Step 3: Check for position of front and rear pointers.
if front = rear then
set front=rear=-1
else
front = (front+1)%MAX
Step 4: Return
Circular Queue Implementation
using Array in C++
Key Points:
isFull() → checks if next rear would overlap with
front.
isEmpty() → front is -1.
enqueue() → adds new item at (rear+1)%capacity.
dequeue() → removes item and moves front
(front+1)%capacity.
peek() → shows front element without deleting.
Circular Queue Implementation
using Linkedlistin C++
Each node has data and a next pointer.
The rear node’s next pointer always points to the
front node → this makes it circular.
We’ll implement:
enqueue() → add at rear
dequeue() → remove from front
peek() → check front element
isEmpty()
display()
Applications of Circular
Queue
1. Memory Management:
The unused memory locations in the case of ordinary
queues can be utilized in circular queues.
2. Traffic system:
In computer controlled traffic system, circular queues
are used to switch on the traffic lights one by one
repeatedly as per the time set.
3. CPU Scheduling:
Operating systems often maintain a queue of
processes that are ready to execute or that are
waiting for a particular event to occur.
Distinguish Between Stack And Queue
Sr STACK QUEUE
.
N
o
It is LIFO(Last In First Out) data It is FIFO (First In First Out) data
1
structure structure.
Insertion and deletion take
Insertion takes place at rear and
2 place at only one end called
deletion takes place at front.
top
3 It has only one pointer variable It has two pointer variables.
4 No memory wastage Memory wastage in linear queue
Operations: Operations:
5
[Link]() [Link]() [Link]() [Link]()
In computer system it is used
In computer system it is used
6 in evaluation of postfix
time/resource sharing
expression, recursive functions