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:

1
2
3
4
5
6
7
8
9

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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)