3 Queue

source:[5]
Table of contents

1. What is Queue?
2. Privmitive Operations of Queue
3. Abstract Data Type of Queue
4. Enqueue Operation of Queue
5. Dequeue Operation of Queue
6. Algorithm Efficiency( Time Complexity)
7. Algorithm Efficiency( Space Complexity
8. Queue Overflow
9. Queue Underflow
10. Types of Queue
a. Linear Queue
b. Circular Queue
c. Priority Queue
d. Double Ended Queue
What is Queue?

● Queue is an ordered collections of items.

● Items that are inserted is called rear of the
queue.
● Items that are deleted or removed is called
front of the queue.
● The first element inserted into a queue is
the first element to be removed.
● Queue is also called First in First Out(FIFO).
● Analogy:
○ A queue is like a line waiting to purchase
tickets, where the first person in lines is
the first person to be served- First come
first served.

source:[1][2][3]
What is Queue(continued..)
Primitive Operation of Queue

1. Enqueue – insert element to the rear of the queue.

2. Dequeue – remove element from front of the queue.
3. Front – view first element at front without removing it.
4. Rear- view the last element at rear without removing it.
5. IsEmpty – check if queue is empty.
6. IsFull – check if queue is full.

source:[1][2][3][4]
Primitive Operation of Queue

source:[11]
Abstract Data Type of Queue
abstract typedef <<eltype>> QUEUE(eltype);

Abstract isempty(q)
QUEUE(eltype) q;
Postcondition empty == (len(q)==0);

Abstract eltype dequeue(q)

QUEUE(eltype) q;
Precondition empty(q) == FALSE;
Postcondition remove== first(q);
q == sub(q’,1,len(q’-1);

Abstract enqueue(q,elt)
QUEUE(eltype) q;
Eltype elt;
Postcondiont q==q’+ <elt>; source:[1]
Enqueue Operation of Queue

Algorithm Enqueue(Q, item)

1. If IsFull(Q)
Print "Overflow"
Return
2. If IsEmpty(Q)
[Link] ← 0
3. [Link] ← [Link] + 1
4. Q[[Link]] ← item

source:[1][3][6]
Dequeue Operation of Queue

Algorithm Dequeue(Q)

1. If IsEmpty(Q)
Print "Underflow"
Return
2. item ← Q[[Link]]
3. If [Link] == [Link]
[Link] ← -1
[Link] ← -1
Else
[Link] ← [Link] + 1
4. Return item

source:[1][3][6]
Algorithm Efficiency (Time Complexity

Operations Time Complexity

Enqueue O(1)
Dequeue O(1)
Peek O(1)
IsEmpty / IsFull O(1)

source:[1][3][6]
Algorithm Efficiency (Space Complexity)

● Depends on queue implementation

● Array-based queue → O(n)

● Linked-list queue → Dynamic memory

source:[1][3][6]
Queue Overflow
Definition
● Occurs when inserting into a full
queue

Condition (Array Queue)

rear == MAX - 1

Causes
● Fixed-size array

● Poor memory utilization

source:[1][3][4][7]
Queue Underflow

Definition
● Occurs when removing from an
empty queue

Condition (Array Queue)

front == -1 Fig: Representation of Queue

Underflow
Causes
● When there is no element or data
exists in queue.

source:[1][3][4][1]
Types of Queue

1. Linear Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue(deque)

source:[1][3][4][1]
1. Linear Queue

Definition
● Elements inserted at rear.

● Elements deleted from

front.

● Uses array or linked list.

source:[1][3][8]
Problem with Linear Queue

source:[11][10]
2. Circular Queue

source:[12]
Circular Queue
Definition
● Last position connects to first. Queue
forms a circle.
● A queue where the start and end of the
queue are joined together.
● A circular queue is one in which the
insertion of a new element is done at very
first location of the queue if the last
location of the queue is full.
● Formula
a. rear = (rear + 1) % MAX
b. front = (front + 1) % MAX
source:[11][12]
Circular Queue conditions

● Empty Condition
front == -1
rear == -1

● Full Condition
(front == (rear + 1) % MAX)

source:[11][12]
Linear Queue vs Circular Queue

Feature Linear Queue Circular Queue

Space usage Inefficient Efficient

Overflow Early Reduced

Complexity Simple Moderate

3. Priority Queue

Priority Queue
Definition
● Each element has a priority.

● Element with highest priority is processed

first.

FIFO Rule
● Applied when priorities are equal.

source:[5]
Types of Priority Queue

Types of Priority Queue

1. Ascending Priority Queue

○ Lower value → higher priority

2. Descending Priority Queue

○ Higher value → higher priority

source:[13]
Priority Queue Operations

● Unlike a standard queue FIFO, elements with higer priority

are served first. If two elements have same priority, they are
served according to their order in the queue.

● There are main two types:

○ Max- priority queue: element with the highest values
has highest priority.
○ Min- priority queue: element with lowest value has
highest priority.

source:[14]
Priority Queue Operations: Enqueue Operation

Algorithm INSERT_PQ(Q, item, priority)

1. If Q is full
Print "Overflow"
Return
2. i ← last index of Q
3. While i >= 0 AND Q[i].priority < priority
Q[i+1] ← Q[i]
i←i-1
4. Q[i+1].data ← item
5. Q[i+1].priority ← priority

source:[1][2][14]
Priority Queue Operations: Dequeue Operation
Algorithm DELETE_PQ(Q)
1. If Q is empty
Print "Underflow"
Return
2. item ← Q[0]
3. Shift all elements one position left
4. Return item

Note:
● Elements are ordered by priority, not by insertion time.

● Highest priority element is always deleted first.

source:[1][2][14]
Priority Queue: Real world examples

Hospital emergency room:

1. Critical patient → Highest priority → Treated first

2. Normal patient → Lower priority → Waits

3. In banks, VIP customers are served first.
4. In gaming, critical game events are processed before less
important ones.
5. Priority queues are used in A* search to explore paths based
on their cost and estimated distance to the target.

source:[1][2][14]
Priority Queue Time Complexity (Array Implementation)

Operation Complexity

Insert O(n)

Delete O(n)

Peek O(1)

source:[1][2][14]
4. Double Ended Queue(deque)

● A deque allows insertion and removal of elements from both end(front

and rear) of the queue.
● Examples:
○ Undo and Redo operations-Text Editors
○ Navigation: Back and Forward button logic

source:[14]
References
● [1]Data Structures using c and c++, Tanenbaum, Langsam, Aaron

● [2]Introduction to algorithms / Thomas H. Cormen

● [3][Link]

cript-implementation/

● [4][Link]

d-performance-exploring-the-queue-data-structure-d135e34cd402

● [5][Link]

● [6][Link]

● [7][Link]

● [8][Link]
References
● [9][Link]

● [10][Link]

● [11][Link]

● [12][Link]

● [13][Link]

● [14][Link]