Unit 4 of 4 · BCA Sem 2

Unit 4: Queues

Data Structures-I notes · PTU syllabus (UGCC2506)

3 min read5 topics10 exam questions
On this page
  1. Unit summary
  2. Queue: definition and representation
  3. Simple queue operations
  4. Circular queue
  5. Deque and priority queue
  6. Applications of queues
  7. Key terms
  8. Quick revision
  9. Important questions

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
1

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.
ComparisonStack vs queue
Stack
Queue

Principle

LIFO

FIFO

Insertion

At TOP (PUSH)

At REAR (enqueue)

Deletion

At TOP (POP)

At FRONT (dequeue)

Example

Undo history

Printer jobs

2

Topic 2

Simple queue operations

GraphA simple queue: insert at REAR, delete from FRONT (FIFO)
1020304050[0][1][2][3][4]FRONT (delete)REAR (insert)

Enqueue moves REAR forward; dequeue moves FRONT forward. In a simple array queue the freed cells at the front are wasted, which circular queues solve

ProcessInsert into a queue
  1. 1Check overflow

    If REAR = MAX − 1

  2. 2First element?

    If FRONT = −1, set FRONT = 0

  3. 3Increase REAR
  4. 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.

3

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.

Example

Circular queue trace with MAX = 4: start with FRONT = REAR = −1. Insert A, B, C, D → FRONT = 0, REAR = 3; now (3 + 1) mod 4 = 0 = FRONT, so the queue is full. Delete twice (A and B leave) → FRONT = 2. Insert E → REAR = (3 + 1) mod 4 = 0. Insert F → REAR = 1. Now (1 + 1) mod 4 = 2 = FRONT, so it is full again, holding C, D, E, F in that order.

Exam tip

Always state both conditions in an answer: full when (REAR + 1) mod MAX = FRONT, and empty when FRONT = −1. When the last item is deleted (FRONT = REAR), reset both to −1.

4

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.

Example

Priority queue order: jobs arrive as P1 (priority 2), P2 (priority 1), P3 (priority 2) and P4 (priority 3), where 1 is the highest priority. They are served as P2, P1, P3, P4 — P2 first because it has the highest priority, and P1 before P3 because equal priorities follow arrival order (FIFO).

ClassificationTypes of queue
Queues
  • 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

5

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

  1. Q1.Define a queue.
  2. Q2.Differentiate between a stack and a queue.
  3. Q3.What is the drawback of a simple queue?
  4. Q4.What is a deque? Name its two types.
  5. Q5.Give two applications of a priority queue.
  6. Q6.Write the condition for a full circular queue.

Long-answer questions

  1. Q1.Write algorithms for insertion and deletion in a circular queue and explain with an example.
  2. Q2.Explain the linked representation of a queue with insertion and deletion.
  3. Q3.Explain deques and priority queues and their implementations.
  4. 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.

WhatsApp us