[Link].
in
Queue
• Queue is a collection whose elements are added at one end
(the rear of the queue) and removed from the other end
(the front of the queue).
• A queue is a FIFO (First In, First Out) data structure.
• Any waiting line is a queue:
The check-out line at a grocery store
The cars at a stop light
An assembly line
2/19/2026 nehasehta@[Link] 2
Conceptual View of a Queue
Insertion Deletion
IN DATA DATA DATA DATA DATA DATA DATA OUT
REAR
FRONT
2/19/2026 nehasehta@[Link] 3
Operations on a Queue
Adding an element
Front of
queue
New element is added to
the Rear of the queue
2/19/2026 nehasehta@[Link] 4
Operations on a Queue
Removing an element
New front element of
queue
Element is removed
from the front of the
queue
2/19/2026 nehasehta@[Link] 5
Operations on a Queue
The basic operations associated with queues −
• enqueue() − add (store) an item to the queue.
• dequeue() − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned
queue operation efficient. These are −
• peek() − Gets the element at the front of the queue without removing
it.
• isfull() − Checks if the queue is full.
• isempty() − Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer
and while enqueuing (or storing) data in the queue we take help
of rear pointer.
2/19/2026 nehasehta@[Link] 6
Algorithm
begin procedure isFull: Queue begin procedure isEmpty: Queue
if rear = MAXSIZE-1 if front = -1
return true return true
else else
return false return false
endif endif
end procedure end procedure
2/19/2026 nehasehta@[Link] 7
Enqueue
• Queues maintain two variables, front and rear.
• 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 queue is empty then
initialize front and rear with 0
else
increment rear to point the next location.
• Step 4 − Add data element to the queue location, where the
rear is pointing.
• Step 5 − Return success.
2/19/2026 nehasehta@[Link] 8
Enqueue
REAR FRONT
E D C B A
Queue Full
2/19/2026 nehasehta@[Link] 9
Enqueue
Empty REAR = FRONT=-1
Queue
REAR FRONT
A After
2/19/2026 nehasehta@[Link] 10
Enqueue
REAR FRONT
D C B A Before
REAR FRONT
E D C B A After
2/19/2026 nehasehta@[Link] 11
Algorithm
begin procedure enqueue: queue, data
if isFull(queue)
return -1
endif
if ( front = -1 and rear = -1)
set front = 0 and rear = 0
else
rear ← rear + 1
endif
queue[rear] ← data
end procedure
2/19/2026 nehasehta@[Link] 12
Dequeue
• Deleting data from the queue is a process of two tasks − access the
data where front is pointing
• 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.
• If the deleted data was last element i.e. front and rear are
equal then set front and rear to -1,
• else increment front to point next available data element.
2/19/2026 nehasehta@[Link] 13
Dequeue
REAR FRONT
Before E D C B A
REAR FRONT
After E D C B
2/19/2026 nehasehta@[Link] 14
Dequeue
REAR FRONT
Before E D C B A
REAR FRONT
After E D C B A
2/19/2026 nehasehta@[Link] 15
Algorithm
begin procedure dequeue : queue, data
if isEmpty(queue)
return -1
end if
data = queue[front]
if ( front = rear)
set front = -1 and rear = -1
else
front ← front + 1
endif
end procedure
2/19/2026 nehasehta@[Link] 16
Algorithm
begin procedure peek : queue, data
return queue[front]
end procedure
2/19/2026 nehasehta@[Link] 17
Applications
• Single-lane one-way road, where the
vehicle enters first, exits first.
• Call center phone systems
• It uses queues to hold people calling them in an
order, until a service representative is free.
2/19/2026 nehasehta@[Link] 18
Application
• More real-world examples can be seen as
queues at the ticket windows and doctor’s
clinic.
2/19/2026 nehasehta@[Link] 19
Applications
1. Serving requests on a single shared resource
• like a printer, CPU task scheduling etc.
2. Queue of packets in data communication.
3. Keyboard buffer.
4. Handling of interrupts in real-time systems
• The interrupts are handled in the same order
as they arrive i.e. first come first served.
2/19/2026 nehasehta@[Link] 20
Implementation using Array
#define MAX 100
struct queue{
int Data[MAX]; // define Array to store Queue elements
int front;
int rear;
};
void initialize(struct queue q) { // function to initialize queue
[Link]= -1;
[Link]= -1;
}
int isEmpty(struct queue q ) { //function to check if the queue is empty or not
return ([Link]==-1);
}
int isFull(struct queue q) { //function to check if the queue is full or not
return ([Link]== MAX – 1)
}
2/19/2026 nehasehta@[Link] 21
Implementation using Array
void enqueue(struct queue q, int item) //function to add an element x in
the queue
{ Queue Overflow
if (isFull(q)) The condition
{ resulting from
trying to enqueue
printf(“Queue is full \n"); an element onto a
exit(EXIT_FAILURE); full queue.
}
if([Link] == -1 && [Link] == -1)
[Link]=[Link]=0;
else
[Link]++;
[Link] [[Link]] = item;
}
2/19/2026 nehasehta@[Link] 22
Implementation using Array
int dequeue(struct queue q) // function to delete an element from the queue
{
int item;
if (isEmpty(q)) Queue Underflow
{ The condition resulting
from trying to
printf(“Queue is Empty\n"); dequeue an empty
exit(EXIT_FAILURE); Queue
}
item= [Link][[Link]]; int peek(struct queue q)
if( [Link] == [Link]) // function to return front element in a queue
[Link] = [Link] = -1; {
else if (!isEmpty(q)) // check for empty queue
[Link]++; return [Link] [[Link]];
return item; else
} exit(EXIT_FAILURE);
}
2/19/2026 nehasehta@[Link] 23
Illustration
rear
0 1 2 3 4 5
front
Queue After Adding an Element rear
0 1 2 3 4 5
front
2/19/2026 nehasehta@[Link] 24
Illustration
Queue After adding an Element
rear
0 1 2 3 4 5
front
Queue After removing an Element
rear
0 1 2 3 4 5
front
2/19/2026 nehasehta@[Link] 25
Illustration
Queue After removing an Element
rear
0 1 2 3 4 5
front
• The rear of the queue is at the end of the array (the highest index). Even if
there are empty cells at the beginning of the array, we still can't insert a new
item because Rear can't go any further.
• If we shift remaining elements forward in the array, then we can create space
for new elements.
2/19/2026 nehasehta@[Link] 26
Illustration
Queue After Shifting rear
0 1 2 3 4 5
front
• Shifting element forward is very time consuming if the length of queue is very
long.
• This difficulty can be overcome if we treat the queue position with index 0 as
a position that comes after the position with index 5 (the highest index).
• We treat the queue as circular queue.
2/19/2026 nehasehta@[Link] 27
Quiz
Q.1 If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted
one at a time, in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
Q.2 A normal queue, if implemented using an array of size MAX_SIZE, gets full
when
a) Rear = MAX_SIZE – 1
b) Front = (rear + 1)mod MAX_SIZE
c) Front = rear + 1
d) Rear = front
2/19/2026 nehasehta@[Link] 28
Circular Queue
• Circular queue which can be thought as Circular array
that conceptually loops around on itself
• The last index is thought to “precede” index 0
2/19/2026 nehasehta@[Link] 29
Circular Queue
front 2 3 2 After 5
1 4 1 3 dequeues
5
0 0
6 4
5
front
13 7 13
6
12 12
8 7
9 rear 11
11 9
10 rear
10 rear 8
After 8 enqueues 1
0
front
12
11
After 7 more enqueues
10
2/19/2026 nehasehta@[Link] 30
Circular Queue Operations
1. Enqueue- Adding an element in the queue if there is
space in the queue.
2. Dequeue- Removing elements from a queue if there
are any elements in the queue
3. Front- Get the first item from the queue.
4. Rear- Get the last item from the queue.
5. isEmpty/isFull- Checks if the queue is empty or full.
2/19/2026 nehasehta@[Link] 31
Circular Queue Operations
int isFull(struct queue q)
{
if([Link] == ([Link] +1) % MAX )
{
return 1;
}
else
return 0;
}
int isEmpty (struct queue q)
{
if([Link] == -1)
return 1;
else
return 0;
}
2/19/2026 nehasehta@[Link] 32
Circular Queue Operations
int enQueue(struct queue q ,int element)
{
if(isFull(q))
{
return 0;
}
if([Link] == -1)
{
[Link] = 0;
[Link] = 0;
}
else
[Link] = ([Link] + 1) % MAX;
[Link][[Link]] = element;
return 1;
}
2/19/2026 nehasehta@[Link] 33
Circular Queue Operations
int deQueue(struct queue q ){
int element;
if(isEmpty(q)) {
return 0;
}
else {
element = [Link][[Link]];
if([Link] == [Link]) {
[Link] = -1;
[Link] = -1;
}
else {
[Link] = ([Link]+1) % MAX;
}
return(element);
}}
2/19/2026 nehasehta@[Link] 34
Example
0 Empty Queue
1
F = R = -1
7
2 0
1
6 7 A
2
3
5 6
4
Insert A 3
F=R=0 5
4
2/19/2026 nehasehta@[Link] 35
Example
0 Insert B,C,D,E,F,G,H
1 F = 0, R = 7
7 A B
H
2
C
0
6 G 1
D 7 B
F
E 3 H
5 2
C
4 6 G
D
F
Delete A E 3
F = 1, R = 7 5
4
2/19/2026 nehasehta@[Link] 36
Example
0
1 Delete B
F = 2, R = 7
7
H 0
2 1
C
7 I
6 G
H
D 2
F C
E 3 G
6
5
4 D
F
E 3
Insert I 5
F = 2, R = 0 4
2/19/2026 nehasehta@[Link] 37
Example
0 0
1 1
7 I 7 I J
J
H H
2 2
C C
6 G 6 G
D D
F F
3 E 3
E
5 5
4 4
Insert K
Insert J
F = 2, R = 1
F = 2, R = 1
Can’t be inserted due to overflow
2/19/2026 nehasehta@[Link] 38
Quiz
1. A circular queue is implemented using an array of size 10. The array
index starts with 0, front is 6, and rear is 9. The insertion of next
element takes place at the array index.
A) 0
B) 7
C) 9
D) 10
2. If the MAX_SIZE is the size of the array used in the implementation
of circular queue, array index start with 0, front point to the first
element in the queue, and rear point to the last element in the queue.
Which of the following condition specify that circular queue is FULL?
A) Front=Rear= -1
B) Front=(Rear+1)%MAX_SIZE
C) Rear=Front+1
D) Rear=(Front+1)%MAX_SIZE
2/19/2026 nehasehta@[Link] 39
Double Ended Queue
• Double ended queue also called as deque (pronounced
as ‘deck’ or ‘dequeue’) is a more generalized form of
queue data structure .
• It allows insertion and removal of elements from both
the ends, i.e , front and rear.
add_front add_rear
0 1 2 3 4 5
front rear
remove_front remove_rear
2/19/2026 nehasehta@[Link] 40
Priority Queue
• A priority queue is a data structure that supports two basic operations:
• Inserting a new item.
• Removing element with the largest ( or smallest) key.
Example: Queue in hospital
( prioritize patient with emergency issue)
2/19/2026 nehasehta@[Link] 41
Example
• Suppose that you have a few assignments from different
courses. Which assignment will you want to work on first?
Course Due Date Priority
Data Structure 14/9/2022 1
OOPM 18/9/2022 3
DCS 20/9/2022 4
Discrete Structures 15/9/2022 2
• You set your priority based on due dates. How many days are
remaining is basically due days , which becomes key.
• A priority queue ranks its elements by key.
2/19/2026 nehasehta@[Link] 42
Types
• There are two types of priority queues :
a) Max Priority Queue
b) Min Priority Queue
2/19/2026 nehasehta@[Link] 43
Queue Simulation
• The word simulate means to imitate or to have the same effect as
original.
• Computer simulation imitates an activity in the real world using a
computer program in order to understand how the real-world process
behaves.
• It is a technique for modeling the behavior of natural and man-made
systems and useful for summarizing the performance of existing
systems or predicting the performance of proposed systems.
• The advantage of computer simulation is that we can easily change
the program and observe impact of modifications on the result.
Queue Simulation
• For simulation of real-world situations, let us take an example of a
bank
• For instance, a bank has four tellers.
• A customer enters the bank at time t1 to conduct
transaction with any teller.
• Transaction takes t2 time.
• If tellers are free, total time taken is t1+t2, but if not, there
may be line waiting at each teller.
• Given such a system, it is required to compute average time
spent by the customer in the bank.
Need Of Queue Simulation
• Waiting is the critical element of queues.
• The objective of a queuing system is to utilize the servers (the tellers,
CPU, operators, and so on) as fully as possible, while keeping the wait
time within a reasonable limit.
• One way is through experience. The bank (in our example) tries out
different numbers of teller machines and sees how things work out.
• There are two problems with this approach:
it takes too long, and
it is too expensive.
• Better approach is to use a computer simulation of the tellers,
customers, and wait time. This approach uses queues.
Terms used in Simulation
• Queuing System - consists of servers and queues of objects to
be served.
• Simulation - a program that determines how long items must wait
in line before being served.
• Inputs to the simulation
1. the length of the simulation
2. the average transaction time
3. the number of servers
4. the average time between job arrivals
• Output of simulation: average wait time.