Understanding Queues in Programming
Concetps, Pseudocode, Examples
What is a Queue?
A Queue is a linear data structure that follows the FIFO (First In First Out) principle. The element that is inserted first is the one that gets removed first.
Imagine a line at a ticket counter — the person who comes first gets served first. This is exactly how a queue works in programming.
Key Operations in a Queue
- Enqueue: Add an element to the rear (end) of the queue
- Dequeue: Remove an element from the front of the queue
- Front: View the element at the front without removing it
- Rear: View the element at the end
- isEmpty: Check if the queue has no elements
Why Use Queues?
Queues are used in:
- Task scheduling (like CPU or printer jobs)
- Breadth-First Search (BFS) in graphs
- Handling requests in asynchronous operations
Example 1: Implementing a Simple Queue
Initialize Queue as empty list
Function enqueue(item):
Add item to the end of Queue
Function dequeue():
If Queue is not empty:
Remove and return first element of Queue
Else:
Return "Queue Underflow"
Function front():
If Queue is not empty:
Return first element
Else:
Return "Queue is empty"
Function isEmpty():
Return true if Queue is empty, else falseQueue: [] Enqueue 10 → Queue: [10] Enqueue 20 → Queue: [10, 20] Dequeue → Returned: 10, Queue: [20] Front → 20 isEmpty → false
Question:
Why do we remove elements from the front instead of the rear in a queue?
Answer: Because a queue follows FIFO — the first element that comes in should be the first to go out, just like a queue in real life.
Example 2: Handling Overflow in Fixed-Size Queue
Suppose we want to limit the queue to a fixed capacity. We need to check for overflow before enqueuing new items.
Initialize Queue as empty list
Set MAX_SIZE = 3
Function enqueue(item):
If length of Queue == MAX_SIZE:
Return "Queue Overflow"
Else:
Add item to end of Queue
Function dequeue():
If Queue is empty:
Return "Queue Underflow"
Else:
Remove and return first elementEnqueue 1 → [1] Enqueue 2 → [1, 2] Enqueue 3 → [1, 2, 3] Enqueue 4 → Queue Overflow Dequeue → Returned 1, Queue: [2, 3]
Question:
How can we improve space usage when using a fixed-size queue?
Answer: Use a circular queue where the rear pointer wraps around to the front once it reaches the end, making better use of space.
Concept Extension: Circular Queue Overview
In a circular queue, the last position is connected back to the first to form a circle. This allows insertion at the beginning when there's space available due to prior deletions at the front.
Summary
- Queues are ideal when order matters (first-in, first-out)
- They support operations like enqueue, dequeue, front, and isEmpty
- Commonly used in scheduling, buffering, and BFS
Practice Exercise
Implement a pseudocode queue that supports the following operations: enqueue, dequeue, front, size, isEmpty, and displayQueue().
Try adding elements beyond the queue size and removing elements from an empty queue to see how it behaves.
Comments
Loading comments...