Implementing a queue using a fixed-size array

Problem

Implement a queue data structure using a fixed-size array. The queue should support the following operations:

• enqueue(x): Add an element x to the end of the queue.
• dequeue(): Remove the element from the front of the queue.
• isEmpty(): Check if the queue is empty.
• isFull(): Check if the queue is full.
• front(): Get the front element of the queue without removing it.
• size(): Get the number of elements currently in the queue.

Examples

Example 1:

Input:
Operations: ["enqueue(1)", "enqueue(2)", "front()", "dequeue()", "isEmpty()"]
Output: [null, null, 1, 1, false]
Explanation:
1. Enqueue 1: The queue becomes [1].
2. Enqueue 2: The queue becomes [1, 2].
3. Front: The front element is 1.
4. Dequeue: Remove the front element 1. The queue becomes [2].
5. isEmpty: The queue is not empty, hence returns false.

Solution

A queue data structure allows elements to be added at the rear and removed from the front. An array can be effectively used to implement a fixed-size queue by maintaining two pointers: one for the front and one for the rear. Additionally, we maintain a variable to keep track of the number of elements in the queue.

Method 1 - Bad dequeue function

Here is how we can implement it:

1. Enqueue: Add an element to the queue after ensuring it is not full. If rear < n, indicating that the array has space, store the element at arr[rear] and increment rear by 1. If rear == n, it is an Overflow condition as the array is full.
2. Dequeue: Remove an element from the queue if there is at least one element to delete, i.e., rear > 0. Delete the element at arr[front], and shift all remaining elements to the left by one position to allow for the dequeuing of the next element at the front.
3. Front: Retrieve the front element from the queue, i.e., arr[front], if the queue is not empty.
4. Display: Print all elements of the queue. Traverse and print elements from index front to rear if the queue is not empty.

Code

Java

public class FixedArrayQueueBadRemove {
    private int[] arr;      // array to store queue elements
    private int front;      // front points to the front element in the queue
    private int rear;       // rear points to the last element in the queue
    private int capacity;   // maximum capacity of the queue
    private int count;      // current size of the queue

    // Constructor to initialize a queue
    public FixedArrayQueueBadRemove(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = 0;
        count = 0;
    }

    // Insert an element at the rear
    public boolean enqueue(int item) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        arr[rear++] = item;
        count++;
        return true;
    }

    // Remove and return the front element
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int temp = arr[front];
        for (int i = 0; i < rear - 1; i++) {
            arr[i] = arr[i + 1];
        }
        arr[--rear] = 0;
        count--;
        return temp;
    }

    // Return the front element without removing it
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return arr[front];
    }

    // Return the size of the queue
    public int size() {
        return count;
    }

    // Check if the queue is empty
    public boolean isEmpty() {
        return count == 0;
    }

    // Check if the queue is full
    public boolean isFull() {
        return rear == capacity;
    }
}

Python

class FixedArrayQueueBadRemove:
    def __init__(self, size: int):
        self.arr = [0] * size  # array to store queue elements
        self.front = 0         # front points to the front element in the queue
        self.rear = 0          # rear points to the last element in the queue
        self.capacity = size   # maximum capacity of the queue
        self.count = 0         # current size of the queue

    # Insert an element at the rear
    def enqueue(self, item: int) -> bool:
        if self.is_full():
            raise OverflowError("Queue is full")
        self.arr[self.rear] = item
        self.rear += 1
        self.count += 1
        return True

    # Remove and return the front element
    def dequeue(self) -> int:
        if self.is_empty():
            raise IndexError("Queue is empty")
        temp = self.arr[self.front]
        for i in range(self.rear - 1):
            self.arr[i] = self.arr[i + 1]
        self.rear -= 1
        self.count -= 1
        self.arr[self.rear] = 0
        return temp

    # Return the front element without removing it
    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.arr[self.front]

    # Return the size of the queue
    def size(self) -> int:
        return self.count

    # Check if the queue is empty
    def is_empty(self) -> bool:
        return self.count == 0

    # Check if the queue is full
    def is_full(self) -> bool:
        return self.rear == self.capacity

Complexity

• ⏰ Time complexity
  • Enqueue: O(1).
  • Dequeue: O(n) due to the shifting of elements.
  • Front: O(1).
  • Display: O(n).
• 🧺 Space complexity: O(n) where n is the capacity of the array.

Method 2 - Using modulo operator

Here is a better approach:

1. Initialize an array of a fixed size.
2. Pointers: Use front and rear pointers to manage the enqueue and dequeue operations.
3. enqueue(x): Add the element x at the position indicated by the rear pointer and update the pointer.
4. dequeue(): Remove the element from the position indicated by the front pointer and update the pointer.
5. isEmpty(): Check if the count of elements is zero.
6. isFull(): Check if the count of elements is equal to the size of the array.
7. front(): Return the element at the front pointer.
8. size(): Return the count of the elements in the queue.

Code

Java

class FixedSizeQueue {
    private int[] arr;
    private int front, rear, count, size;

    public FixedSizeQueue(int size) {
        this.size = size;
        arr = new int[size];
        front = 0;
        rear = -1;
        count = 0;
    }

    public boolean enqueue(int item) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear + 1) % size;
        arr[rear] = item;
        count += 1;
        return true;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int item = arr[front];
        front = (front + 1) % size;
        count -= 1;
        return item;
    }

    public int front() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return arr[front];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == size;
    }

    public int size() {
        return count;
    }
}

Python

class FixedSizeQueue:
    def __init__(self, size: int):
        self.size = size
        self.arr = [None] * size
        self.front = 0
        self.rear = -1
        self.count = 0

    def enqueue(self, item: int) -> bool:
        if self.is_full():
            raise OverflowError("Queue is full")
        self.rear = (self.rear + 1) % self.size
        self.arr[self.rear] = item
        self.count += 1
        return True

    def dequeue(self) -> int:
        if self.is_empty():
            raise IndexError("Queue is empty")
        item = self.arr[self.front]
        self.front = (self.front + 1) % self.size
        self.count -= 1
        return item

    def front(self) -> int:
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.arr[self.front]

    def is_empty(self) -> bool:
        return self.count == 0

    def is_full(self) -> bool:
        return self.count == self.size

    def size(self) -> int:
        return self.count

Complexity

• ⏰ Time complexity: O(1). The complexity for all operations (enqueue, dequeue, isEmpty, isFull, front, and size) is O(1) since we are using direct indexing and simple arithmetic operations.
• 🧺 Space complexity: O(n)

Method 3 - Generic Queue Implementation

This approach implements a generic queue that can work with any data type, providing type safety and reusability. The implementation uses array reflection in Java and TypeVar in Python to achieve generics.

1. Generic Type Support: Use generics to allow the queue to store any type of element.
2. Dynamic Array Creation: Create arrays of generic types using reflection (Java) or typing (Python).
3. Circular Buffer Logic: Similar to Method 2 but with generic type support.
4. Type Safety: Compile-time type checking ensures type safety.

Code

Java

import java.lang.reflect.Array;
import java.util.Arrays;

public class GenericQueue<E> {
    private E[] arr;
    private int head = -1;
    private int tail = -1;
    private int size;
    private int capacity;

    public GenericQueue(Class<E> clazz, int capacity) {
        this.capacity = capacity;
        this.arr = (E[]) Array.newInstance(clazz, capacity);
        this.size = 0;
    }

    public boolean enqueue(E element) {
        if (size == capacity) {
            throw new IllegalStateException("Queue is full");
        }

        head = (head + 1) % capacity;
        arr[head] = element;
        size++;

        if (tail == -1) {
            tail = head;
        }

        return true;
    }

    public E dequeue() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty");
        }

        E result = arr[tail];
        arr[tail] = null;
        size--;
        tail = (tail + 1) % capacity;

        if (size == 0) {
            head = -1;
            tail = -1;
        }

        return result;
    }

    public E front() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        return arr[tail];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return Arrays.toString(arr);
    }
}

Python

from typing import TypeVar, Generic, List, Optional

T = TypeVar('T')

class GenericQueue(Generic[T]):
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.arr: List[Optional[T]] = [None] * capacity
        self.head = -1
        self.tail = -1
        self.size = 0

    def enqueue(self, element: T) -> bool:
        if self.size == self.capacity:
            raise OverflowError("Queue is full")

        self.head = (self.head + 1) % self.capacity
        self.arr[self.head] = element
        self.size += 1

        if self.tail == -1:
            self.tail = self.head

        return True

    def dequeue(self) -> T:
        if self.size == 0:
            raise IndexError("Queue is empty")

        result = self.arr[self.tail]
        self.arr[self.tail] = None
        self.size -= 1
        self.tail = (self.tail + 1) % self.capacity

        if self.size == 0:
            self.head = -1
            self.tail = -1

        return result

    def front(self) -> T:
        if self.size == 0:
            raise IndexError("Queue is empty")
        return self.arr[self.tail]

    def is_empty(self) -> bool:
        return self.size == 0

    def is_full(self) -> bool:
        return self.size == self.capacity

    def get_size(self) -> int:
        return self.size

    def __str__(self) -> str:
        return str(self.arr)

# Example usage with type hints
# queue_int: GenericQueue[int] = GenericQueue(5)
# queue_str: GenericQueue[str] = GenericQueue(10)

Complexity

• ⏰ Time complexity: O(1). All operations maintain constant time complexity regardless of the generic type used.
• 🧺 Space complexity: O(n) where n is the capacity of the queue, same as previous methods but with additional type safety.