👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Linear Data Structures
Study mode

Queues

Study Practice Revise 🔒 Test

Introduction to Queues in Linear Data Structures

In computer science, data structures are ways to organize and store data so that it can be accessed and modified efficiently. One important category is linear data structures, where elements are arranged in a sequence, one after another.

Examples of linear data structures include arrays, linked lists, stacks, and queues. Each has its unique way of adding, removing, or accessing elements.

In this section, we focus on queues, a linear data structure that follows a special rule for adding and removing elements called First In, First Out (FIFO). This means the first element added to the queue will be the first one to be removed.

Think of a queue as a line of people waiting at a ticket counter. The person who arrives first stands at the front and is served first, while new people join the line at the rear. This simple, everyday example helps us understand how queues work in computers.

Queues are widely used in computer science and appear frequently in competitive exams because they model many real-world processes such as task scheduling, buffering, and resource management.

Queue Definition and FIFO Principle

A queue is a collection of elements that supports two main operations:

  • Insertion of elements at one end called the rear.
  • Deletion of elements from the other end called the front.

The key characteristic of a queue is the FIFO (First In, First Out) principle. This means that the element inserted first will be the first to be removed, just like people standing in a queue at a bus stop.

Elements enter the queue at the rear and leave from the front, maintaining the order of arrival.

A B C D Front Rear Enqueue (Insert) Dequeue (Remove)

Queue Operations

Queues support several fundamental operations that allow us to manage the data inside them efficiently. These operations are:

1. Enqueue (Insertion)

This operation adds an element at the rear of the queue. For example, if a new customer arrives at a bank, they join the end of the line.

2. Dequeue (Deletion)

This operation removes an element from the front of the queue. Continuing the example, the customer at the front of the line is served and leaves the queue.

3. Peek or Front

This operation returns the element at the front without removing it. It helps to know who is next in line without changing the queue.

4. IsEmpty

Checks whether the queue has any elements. If the queue is empty, no dequeue operation can be performed.

5. IsFull

Checks whether the queue has reached its maximum capacity (important in fixed-size implementations like arrays).

graph TD    Start[Start Operation] --> CheckFull{Is Queue Full?}    CheckFull -- Yes --> RejectEnqueue[Reject Enqueue]    CheckFull -- No --> Enqueue[Add element at Rear]    Enqueue --> End[End Operation]    Start --> CheckEmpty{Is Queue Empty?}    CheckEmpty -- Yes --> RejectDequeue[Reject Dequeue]    CheckEmpty -- No --> Dequeue[Remove element from Front]    Dequeue --> End

Types of Queues

There are several variations of queues designed to solve different problems or improve efficiency:

Type Insertion Point Deletion Point Key Features Typical Applications
Simple Queue Rear Front Linear, FIFO, fixed start and end Basic task scheduling, buffering
Circular Queue Rear (wraps around) Front (wraps around) Efficient use of space, avoids "false full" CPU scheduling, resource management
Priority Queue Based on priority Highest priority element Elements dequeued by priority, not arrival order Emergency systems, print spooling
Deque (Double Ended Queue) Front and Rear Front and Rear Insertion and deletion at both ends Undo operations, palindrome checking

Queue Implementations

Queues can be implemented using different data structures, each with its own advantages and disadvantages.

1. Array-based Queue

In this method, a fixed-size array is used to store queue elements. Two pointers or indices, front and rear, track the positions for deletion and insertion respectively.

Advantages: Simple to implement, fast access.

Disadvantages: Fixed size leads to wasted space when elements are dequeued; requires shifting or circular logic.

2. Linked List-based Queue

Here, each element is a node containing data and a pointer to the next node. The queue maintains pointers to the front and rear nodes.

Advantages: Dynamic size, no wasted space.

Disadvantages: Requires extra memory for pointers, slightly more complex.

Array-based Queue 10 20 30 Front -> Rear -> Linked List-based Queue 10 20 30 Front -> Rear ->

Worked Examples

Example 1: Enqueue and Dequeue in a Simple Queue Easy
Consider a queue implemented using an array of size 5. Initially, the queue is empty. Perform the following operations step-by-step:
  1. Enqueue 10
  2. Enqueue 20
  3. Enqueue 30
  4. Dequeue one element
  5. Enqueue 40
Show the state of the queue after each operation.

Step 1: Initially, queue is empty. front = -1, rear = -1.

Operation: Enqueue 10

Since queue is empty, set front = 0 and rear = 0. Insert 10 at index 0.

Queue: [10, _, _, _, _]

Step 2: Enqueue 20

Increment rear to 1, insert 20 at index 1.

Queue: [10, 20, _, _, _]

Step 3: Enqueue 30

Increment rear to 2, insert 30 at index 2.

Queue: [10, 20, 30, _, _]

Step 4: Dequeue one element

Remove element at front = 0 (which is 10). Increment front to 1.

Queue logically: [_, 20, 30, _, _]

Step 5: Enqueue 40

Increment rear to 3, insert 40 at index 3.

Queue: [_, 20, 30, 40, _]

Final state: front = 1, rear = 3, queue elements from index 1 to 3 are [20, 30, 40].

Example 2: Circular Queue Operation Medium
A circular queue of size 5 is initially empty. Perform the following operations and show the queue state after each:
  1. Enqueue 100
  2. Enqueue 200
  3. Enqueue 300
  4. Dequeue one element
  5. Enqueue 400
  6. Enqueue 500
  7. Enqueue 600

Step 1: Enqueue 100

front = 0, rear = 0, queue: [100, _, _, _, _]

Step 2: Enqueue 200

rear = (0 + 1) mod 5 = 1, queue: [100, 200, _, _, _]

Step 3: Enqueue 300

rear = (1 + 1) mod 5 = 2, queue: [100, 200, 300, _, _]

Step 4: Dequeue one element

Remove element at front = 0 (100), front = (0 + 1) mod 5 = 1

Queue logically: [_, 200, 300, _, _]

Step 5: Enqueue 400

rear = (2 + 1) mod 5 = 3, queue: [_, 200, 300, 400, _]

Step 6: Enqueue 500

rear = (3 + 1) mod 5 = 4, queue: [_, 200, 300, 400, 500]

Step 7: Enqueue 600

Now, rear = 4, next rear would be (4 + 1) mod 5 = 0. Since front = 1, the queue is not full yet.

Insert 600 at index 0 (wrap-around), queue: [600, 200, 300, 400, 500]

Final pointers: front = 1, rear = 0

Example 3: Priority Queue Example Medium
Insert the following elements into a priority queue where lower numeric value means higher priority: (Data, Priority) pairs are (A, 3), (B, 1), (C, 2), (D, 4). Then, perform two dequeue operations and show which elements are removed.

Step 1: Insert (A, 3)

Queue: [(A,3)]

Step 2: Insert (B, 1)

Queue sorted by priority: [(B,1), (A,3)]

Step 3: Insert (C, 2)

Queue sorted: [(B,1), (C,2), (A,3)]

Step 4: Insert (D, 4)

Queue sorted: [(B,1), (C,2), (A,3), (D,4)]

Step 5: Dequeue first element

Remove (B,1) because it has the highest priority (lowest number).

Queue now: [(C,2), (A,3), (D,4)]

Step 6: Dequeue second element

Remove (C,2), next highest priority.

Queue now: [(A,3), (D,4)]

Example 4: Implementing Queue Using Linked List Medium
Show stepwise insertion of elements 5, 10, 15 into an empty queue implemented using a singly linked list. Then perform one dequeue operation. Illustrate pointer changes at each step.

Initial state: front = null, rear = null

Insert 5:

  • Create a new node with data 5.
  • Since queue is empty, set front and rear to this node.

Queue: front -> [5] <- rear

Insert 10:

  • Create new node with data 10.
  • Set rear.next to new node.
  • Update rear to new node.

Queue: front -> [5] -> [10] <- rear

Insert 15:

  • Create new node with data 15.
  • Set rear.next to new node.
  • Update rear to new node.

Queue: front -> [5] -> [10] -> [15] <- rear

Dequeue one element:

  • Remove node at front (5).
  • Update front to front.next (node with 10).
  • If front becomes null, set rear to null (not the case here).

Queue: front -> [10] -> [15] <- rear

Example 5: Real-life Application - CPU Scheduling Using Queue Hard
A CPU scheduler uses a queue to manage processes in a round-robin fashion. Given processes P1, P2, P3 arriving in that order, simulate the scheduling where each process gets 2 milliseconds of CPU time per turn. Show the order of execution for 3 cycles.

Step 1: Initialize queue with processes in order: P1, P2, P3

Queue: front -> [P1] -> [P2] -> [P3] <- rear

Step 2: First cycle of execution

  • Dequeue P1, execute for 2 ms, then enqueue P1 at rear.
  • Dequeue P2, execute for 2 ms, then enqueue P2 at rear.
  • Dequeue P3, execute for 2 ms, then enqueue P3 at rear.

Queue after first cycle: [P1, P2, P3]

Step 3: Second cycle

  • Dequeue P1, execute, enqueue at rear.
  • Dequeue P2, execute, enqueue at rear.
  • Dequeue P3, execute, enqueue at rear.

Queue after second cycle: [P1, P2, P3]

Step 4: Third cycle

  • Repeat the same steps.

Execution order over 3 cycles: P1 -> P2 -> P3 -> P1 -> P2 -> P3 -> P1 -> P2 -> P3

This demonstrates how queues efficiently manage CPU time-sharing among processes in operating systems.

Tips & Tricks

Tip: Remember FIFO by imagining a queue at a railway station ticket counter.

When to use: Helps recall the fundamental principle of queues during conceptual questions.

Tip: Use modulo operation to handle circular queue indices.

When to use: When implementing or solving problems related to circular queues.

Tip: For priority queues, always check the priority before dequeueing.

When to use: When solving problems that involve priority-based processing.

Tip: Visualize queue operations with simple diagrams to avoid confusion between front and rear pointers.

When to use: Useful during implementation and debugging.

Tip: Practice implementing queues both with arrays and linked lists to strengthen understanding.

When to use: Prepares for coding and theory questions in competitive exams.

Common Mistakes to Avoid

❌ Confusing front and rear pointers during enqueue and dequeue operations.
✓ Remember: front points to the element to be dequeued, rear points to the last inserted element.
Why: Similar terminology and lack of visualization cause mix-ups.
❌ Not using modulo operation in circular queue leading to index out of bounds errors.
✓ Always apply modulo with capacity to wrap indices correctly.
Why: Forgetting this causes runtime errors and incorrect queue behavior.
❌ Assuming priority queue dequeues elements in FIFO order.
✓ Priority queue dequeues based on priority, not arrival time.
Why: Misunderstanding the priority mechanism leads to wrong answers.
❌ Overlooking the isFull condition in array-based queues causing overflow.
✓ Check isFull before enqueue to prevent overflow errors.
Why: Ignoring this leads to data loss or program crashes.
❌ Implementing dequeue in linked list queues without updating front pointer.
✓ Always update front pointer to next node after dequeue.
Why: Neglecting this causes dangling pointers and incorrect queue state.

Formula Bank

Queue Size Calculation (Array Implementation)
\[ \text{Size} = (\text{rear} - \text{front} + \text{capacity}) \bmod \text{capacity} \]
where: rear = index of last element, front = index of first element, capacity = total size of the queue array
Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Queues · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.