Unit 4: Queues
Data Structures-I notes · PTU syllabus (UGCC2506)
On this page
Unit summary
A queue is a list where items join at one end (the rear) and leave from the other (the front) — like a ticket line. Queues manage printing, CPU scheduling and data buffers. This unit covers simple, circular, double-ended and priority queues.
After this unit you can
- Represent a queue using an array and a linked list
- Write insertion and deletion algorithms for simple and circular queues
- Explain deques and priority queues
- List applications of queues
PTU syllabus topics
- Definition
- array and linked-list representation
- simple queue
- circular queue
- double-ended queue
- priority queue
- operations on simple and circular queues
- applications of queues
Structure
Linear array, front and rear move forward
Rear wraps to the start
Wasted space
Freed slots at the front cannot be reused
All slots are reused
Full condition
rear = size − 1
(rear + 1) % size = front
Use
Simple buffering
CPU scheduling, streaming buffers
Topic 1
Queue: definition and representation
A queue is a linear data structure that follows FIFO (First In, First Out). Insertion (enqueue) happens at the REAR; deletion (dequeue) happens at the FRONT.
- Array representation: QUEUE[MAX] with FRONT and REAR (both −1 when empty).
- Linked representation: a linked list with pointers to the front and rear nodes; insert at the rear, delete from the front.
Principle
LIFO
FIFO
Insertion
At TOP (PUSH)
At REAR (enqueue)
Deletion
At TOP (POP)
At FRONT (dequeue)
Example
Undo history
Printer jobs
Topic 2
Simple queue operations
- 1Check overflow
If REAR = MAX − 1
- 2First element?
If FRONT = −1, set FRONT = 0
- 3Increase REAR
- 4Store
QUEUE[REAR] = ITEM
Deletion checks underflow (FRONT = −1 or FRONT > REAR), takes QUEUE[FRONT] and increases FRONT. Drawback: in a simple array queue, the spaces freed at the front cannot be reused, so the queue may report "full" even when there is empty space.
Topic 3
Circular queue
A circular queue connects the last position back to the first, so freed spaces are reused. Positions move with modulo arithmetic:
- REAR = (REAR + 1) mod MAX, FRONT = (FRONT + 1) mod MAX
- Full when (REAR + 1) mod MAX = FRONT; empty when FRONT = −1.
Example
With MAX = 5, after inserting 5 items and deleting 2, a simple queue says it is full, but a circular queue can store 2 more by wrapping REAR to positions 0 and 1.
Topic 4
Deque and priority queue
- Deque (double-ended queue): insertion and deletion at both ends. Input-restricted deque: insert at one end only; output-restricted deque: delete at one end only.
- Priority queue: each element has a priority; the highest-priority element is removed first, and equal priorities follow FIFO. It can be implemented with an ordered list, multiple queues (one per priority) or a heap.
Simple queue
FIFO, insert at rear, delete at front
Circular queue
Reuses freed space with wrap-around
Deque
Insert and delete at both ends
Priority queue
Highest priority served first
Topic 5
Applications of queues
- CPU scheduling (round robin uses a circular queue) and disk scheduling.
- Print spooling: printing jobs in the order sent.
- Buffers in keyboards, networks and streaming.
- Breadth-first search in graphs.
- Call-centre and ticket systems.
Key terms
- Queue
- A FIFO list with insertion at the rear and deletion at the front
- Circular queue
- A queue in which the last position wraps to the first
- Deque
- A queue allowing insertion and deletion at both ends
- Priority queue
- A queue that serves elements by priority
- Enqueue / dequeue
- Insertion / deletion in a queue
Quick revision
- Queue = FIFO; rear for insert, front for delete.
- Simple array queue wastes freed space; circular queue fixes it.
- Circular full: (REAR + 1) mod MAX = FRONT.
- Deque: both ends; priority queue: by priority.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define a queue.
- Q2.Differentiate between a stack and a queue.
- Q3.What is the drawback of a simple queue?
- Q4.What is a deque? Name its two types.
- Q5.Give two applications of a priority queue.
- Q6.Write the condition for a full circular queue.
Long-answer questions
- Q1.Write algorithms for insertion and deletion in a circular queue and explain with an example.
- Q2.Explain the linked representation of a queue with insertion and deletion.
- Q3.Explain deques and priority queues and their implementations.
- Q4.Discuss the applications of queues in computer science.
Stuck on this unit?
Message SBS on WhatsApp for help with Data Structures-I, or to ask about studying BCA at Synetic.