Implement Queue Using Array: Complete Guide with Normal and Optimal Solutions

Problem Statement

You need to implement a queue using an array (Python list works as an array here). The queue should support two main operations:

• Push(x): Insert element x at the rear (end) of the queue.
• Pop(): Remove and return the front (first) element of the queue. If the queue is empty, return -1.

Here’s the [Problem Link] to begin with.

What is a Queue?

• A queue is a simple data structure that works on FIFO (First In, First Out) principle.
• That means: the first item that was added (pushed) is the first item to be removed (popped).

Think of a queue like a line of people waiting for a movie ticket: the first person in line (front) gets served first, and new people join at the end (rear).

Solution 1: Normal Approach (Using Python List with append and pop(0))

Intuition

The simplest way is to use a Python list like a dynamic array. We add new elements to the end (using append, like the rear of the queue) and remove from the beginning (using pop(0), like the front). It’s like having a flexible line where people join at the back, but when someone leaves from the front, everyone else has to shift forward – which can be slow if the queue is long!

Detailed Approach

1. Initialization: Create an empty list self.arr.
2. Push(x): Append x to the end of the list (rear).
3. Pop(): If the list is empty, return -1. Otherwise, remove and return the first element (front) using pop(0).
4. Why Normal?: This is easy to code, but pop(0) shifts all elements, making it slow for large queues.
5. Edge Cases: Handle empty queue by checking len(self.arr) == 0.

Code

class MyQueue:
    def __init__(self):
        self.arr = []  # Empty list for queue
    
    # Function to push an element x in a queue.
    def push(self, x):
        self.arr.append(x)  # Add to end (rear)
    
    # Function to pop an element from queue and return that element.
    def pop(self):
        if len(self.arr) == 0:
            return -1  # Queue empty
        e = self.arr.pop(0)  # Remove from start (front)
        return e

Code Explanation

We use Python’s list as our queue storage. push adds to the end with append (O(1) time). pop checks if empty (return -1), else uses pop(0) to remove the first element (front). But pop(0) is O(n) because it shifts all remaining elements left by one position.

Time and Space Complexity

• push(): O(1) – Append is constant time
• pop(): O(n) – pop(0) shifts n elements
• Space: O(n) – For n elements in the list

Simplifying It

This is like a line where people join at the back quickly, but when the first person leaves, everyone else has to scoot forward one by one. Easy to set up, but gets slow with many people!

Solution 2: Optimal Approach (Using Fixed-Size Array with Front and Rear Pointers)

Intuition

To make both push and pop fast (O(1)), we use a fixed-size array and two pointers: front (points to the start) and rear (points to the next empty spot at the end). We add at rear and remove from front, just moving the pointers without shifting elements. It’s like reserving seats in a row: people sit from left to right, and when someone leaves from the front, we just move the “front” marker right – no need to shift everyone!

Detailed Approach

1. Initialization: Create a fixed array of size 100005 (big enough), set front = 0 and rear = 0.
2. Push(x): Put x at arr[rear], then increment rear (add to end).
3. Pop(): If front == rear (empty), return -1. Else, get arr[front], increment front, and return it (remove from start).
4. Why Optimal?: No shifting – just pointer moves, so O(1) for both operations.
5. Edge Cases: Empty when front == rear. (Note: This is a simple queue without wrapping around.)

Code

class MyQueue:
    def __init__(self):
        self.arr = [0] * 100005  # Fixed-size array
        self.front = 0            # Pointer to front
        self.rear = 0             # Pointer to next empty spot at rear
    
    # Function to push an element x in a queue.
    def push(self, x):
        self.arr[self.rear] = x   # Place at rear
        self.rear += 1            # Move rear forward
    
    # Function to pop an element from queue and return that element.
    def pop(self):
        if self.front == self.rear:
            return -1             # Queue empty
        temp = self.arr[self.front]  # Get front element
        self.front += 1           # Move front forward
        return temp

Code Explanation

We use a fixed array with front tracking the first element and rear tracking where to add next. push writes to arr[rear] and increments rear (O(1)). pop reads arr[front] and increments front (O(1)), without shifting. Empty when front catches up to rear. (Note: Array size is fixed to 100005 as per common constraints; it won’t overflow in typical use.)

Dry Run

Let’s trace through operations:

Initialize: arr = [0,0,0,…], front=0, rear=0

push(2): arr=2, rear=1 → arr=[2,0,0,…]
push(3): arr=3, rear=2 → arr=[2,3,0,…]
push(5): arr=5, rear=3 → arr=[2,3,5,…]

pop(): front=0 !=3, temp=2, front=1, return 2 (arr unchanged, but front moved)
pop(): front=1 !=3, temp=3, front=2, return 3
pop(): front=2 !=3, temp=5, front=3, return 5
pop(): front=3 ==3, return -1 (empty)

Time and Space Complexity

• push(): O(1) – Just assign and increment pointer
• pop(): O(1) – Just increment pointer and return
• Space: O(1) fixed (array size is constant 100005, doesn’t grow with n)

Simplifying It

This is like a fixed row of seats where you add people from left to right (increasing rear). When removing, you just say “the front person left” and move the front marker right – no one shifts seats. Super fast for both adding and removing!

Summary

The optimal approach is better for speed (O(1) pop) and is what you’d implement in interviews to show you understand efficient queues. The normal way is fine for small queues but slows down with large ones due to shifting.

Key Takeaways

• Queues are FIFO: First in, first out.
• Python lists can mimic queues, but pop(0) is slow – use pointers for efficiency.
• In interviews, mention why the pointer method is better (no shifting, O(1) operations).
• Practice: Try adding more features like checking if full (when rear reaches array end) or making it circular for reuse!

This covers the basics, now you can implement queues easily!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.