Queue Implementation Using Array in DSA Python

Mental Model

A queue is like a line where the first person in is the first person out. Using an array, we keep track of where the line starts and ends.

Analogy: Imagine a line of people waiting to buy tickets. The first person to get in line is the first to get the ticket and leave the line. The array holds the people, and two markers show who is first and last.

front -> [ ] [ ] [ ] [ ] [ ] ← rear
indexes  0   1   2   3   4

Dry Run Walkthrough

Input: Start with empty queue of size 5, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements enter and leave the queue using array indexes

Step 1: enqueue 10 at rear

front=0, rear=0, array=[10, _, _, _, _]

Why: Add first element at start of queue

Step 2: enqueue 20 at rear+1

front=0, rear=1, array=[10, 20, _, _, _]

Why: Add next element behind the first

Step 3: dequeue element at front

front=1, rear=1, array=[10, 20, _, _, _]

Why: Remove first element by moving front forward

Step 4: enqueue 30 at rear+1

front=1, rear=2, array=[10, 20, 30, _, _]

Why: Add new element behind current rear

Result:

front=1, rear=2, array=[10, 20, 30, _, _]
Queue elements: 20 -> 30 -> null

Annotated Code

DSA Python

class Queue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = -1
        self.rear = -1

    def is_empty(self):
        return self.front == -1

    def is_full(self):
        return self.rear == self.size - 1

    def enqueue(self, value):
        if self.is_full():
            print("Queue is full")
            return
        if self.is_empty():
            self.front = 0
        self.rear += 1  # move rear forward to add new element
        self.queue[self.rear] = value

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
            return None
        value = self.queue[self.front]
        if self.front == self.rear:  # only one element
            self.front = -1
            self.rear = -1
        else:
            self.front += 1  # move front forward to remove element
        return value

    def display(self):
        if self.is_empty():
            print("Queue is empty")
            return
        result = []
        for i in range(self.front, self.rear + 1):
            result.append(str(self.queue[i]))
        print(" -> ".join(result) + " -> null")

# Driver code
q = Queue(5)
q.enqueue(10)
q.enqueue(20)
q.dequeue()
q.enqueue(30)
q.display()

if self.is_full():

check if queue has no space left to add

if self.is_empty():

initialize front when adding first element

self.rear += 1 # move rear forward to add new element

advance rear pointer to next free slot

if self.is_empty():

check if queue is empty before removing

if self.front == self.rear: # only one element

reset queue when last element is removed

self.front += 1 # move front forward to remove element

advance front pointer to next element

for i in range(self.front, self.rear + 1):

iterate from front to rear to display queue

Output

20 -> 30 -> null

Complexity Analysis

Time: O(1) for enqueue and dequeue because we only move pointers without shifting elements

Space: O(n) because we use an array of fixed size n to store elements

vs Alternative: Compared to linked list queue, array queue uses fixed space and can be faster but may waste space if not circular

Edge Cases

enqueue when queue is full

prints 'Queue is full' and does not add element

DSA Python

if self.is_full():

dequeue when queue is empty

prints 'Queue is empty' and returns None

DSA Python

if self.is_empty():

dequeue last element

resets front and rear to -1 to mark empty queue

DSA Python

if self.front == self.rear:

When to Use This Pattern

When you need a first-in-first-out order and want fast add/remove at ends, use a queue with front and rear pointers to track positions in an array.

Common Mistakes

Mistake: Not updating front pointer on dequeue, causing repeated removal of same element
Fix: Advance front pointer by one after removing element

Mistake: Not resetting front and rear when queue becomes empty after dequeue
Fix: Set front and rear to -1 when last element is removed

Mistake: Trying to enqueue without checking if queue is full, causing index error
Fix: Check is_full before adding new element

Summary

Implements a queue using an array with front and rear pointers to add and remove elements in order.

Use when you want a simple queue with fixed size and fast enqueue/dequeue operations.

Remember to move front and rear pointers correctly and reset them when queue is empty.

Practice

1. What is the main characteristic of a queue implemented using an array?

easy

A. It follows First-In-First-Out (FIFO) order

B. It follows Last-In-First-Out (LIFO) order

C. It allows random access to elements

D. It automatically sorts elements

Solution

1. Step 1: Understand queue behavior

   A queue adds elements at the rear and removes from the front, following FIFO.

2. Step 2: Compare options

   LIFO is for stacks, random access and sorting are not queue properties.

3. Final Answer:

   It follows First-In-First-Out (FIFO) order -> Option A

4. Quick Check:

   Queue = FIFO [OK]

Hint: Queue always removes the oldest element first [OK]

Common Mistakes:

• Confusing queue with stack (LIFO)
• Thinking queue allows random access
• Assuming queue sorts elements automatically

2. Which of the following is the correct way to initialize an empty queue using an array in Python?

easy

A. queue = ()

B. queue = {}

C. queue = set()

D. queue = []

Solution

1. Step 1: Identify array type in Python

   Python lists are used as arrays and initialized with [] for empty list.

2. Step 2: Check other options

   {} is dict, () is tuple, set() is a set, none are arrays.

3. Final Answer:

   queue = [] -> Option D

4. Quick Check:

   Empty array = [] [OK]

Hint: Use [] to create empty list (array) in Python [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Using () which creates a tuple
• Using set() which is unordered

3. What will be the output of the following code?

queue = []
queue.append(10)
queue.append(20)
queue.append(30)
print(queue.pop(0))
print(queue)

medium

A. 30
[10, 20]

B. 10
[20, 30]

C. 10
[10, 20, 30]

D. 20
[10, 30]

Solution

1. Step 1: Trace queue operations

   Append adds 10, 20, 30 to queue: [10, 20, 30]. pop(0) removes first element 10.

2. Step 2: Check print outputs

   First print outputs 10, second print outputs remaining queue [20, 30].

3. Final Answer:

   10 [20, 30] -> Option B

4. Quick Check:

   pop(0) removes front = 10 [OK]

Hint: pop(0) removes front element in queue [OK]

Common Mistakes:

• Using pop() instead of pop(0) removes last element
• Confusing append order
• Expecting pop(0) to remove last element

4. Identify the error in this queue implementation using an array:

queue = []
queue.append(1)
queue.append(2)
queue.pop()
print(queue)

medium

A. pop() removes last element, not front

B. append() is used incorrectly

C. queue should be a dictionary

D. print statement syntax error

Solution

1. Step 1: Understand pop() behavior

   pop() without index removes last element, not front as queue requires.

2. Step 2: Check queue correctness

   Queue must remove front element, so pop(0) should be used instead of pop().

3. Final Answer:

   pop() removes last element, not front -> Option A

4. Quick Check:

   Queue removal = pop(0) front [OK]

Hint: Use pop(0) to dequeue from front [OK]

Common Mistakes:

• Using pop() removes last, not front
• Confusing append usage
• Thinking queue is a dictionary

5. Given a fixed-size array of length 3, what happens if you try to enqueue 4 elements in a queue implemented using this array without resizing or circular logic?

hard

A. The queue automatically resizes to fit 4 elements

B. The 4th element replaces the first element

C. The queue overflows and cannot add the 4th element

D. The queue removes the last element to add the 4th

Solution

1. Step 1: Understand fixed-size array limits

   An array of length 3 can hold only 3 elements; no extra space for 4th.

2. Step 2: Check enqueue behavior without resizing

   Without resizing or circular logic, adding 4th element causes overflow error or failure.

3. Final Answer:

   The queue overflows and cannot add the 4th element -> Option C

4. Quick Check:

   Fixed array size = no extra elements [OK]

Hint: Fixed array size limits enqueue capacity [OK]

Common Mistakes:

• Assuming automatic resizing happens
• Thinking 4th element replaces first
• Believing queue removes last element automatically