Problem

Implement a queue data structure using a dynamic array that resizes itself when it becomes full. 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.
  • 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

Method 1 - Using resizing or dynamic arrays

Here is how we can do it:

  1. Initialize an array with an initial capacity.
  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. If the array is full, resize the array to double its current capacity.
  4. dequeue(): Remove the element from the position indicated by the front pointer and update the pointer. If the array is too sparse, resize the array to half its current capacity.
  5. isEmpty(): Check if the count of elements is zero.
  6. front(): Return the element at the front pointer.
  7. 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

class Solution {
    private int[] arr;
    private int front, rear, count, capacity;

    // Constructor to initialize the queue
    public Solution(int initialCapacity) {
        arr = new int[initialCapacity];
        capacity = initialCapacity;
        front = 0;
        rear = 0;
        count = 0;
    }

    // Resize the array to the new capacity
    private void resize(int newCapacity) {
        int[] newArr = new int[newCapacity];
        for (int i = 0; i < count; i++) {
            newArr[i] = arr[(front + i) % capacity];
        }
        arr = newArr;
        front = 0;
        rear = count;
        capacity = newCapacity;
    }

    // Enqueue operation
    public boolean enqueue(int item) {
        if (count == capacity) {
            resize(2 * capacity);
        }
        arr[rear] = item;
        rear = (rear + 1) % capacity;
        count++;
        return true;
    }

    // Dequeue operation
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int item = arr[front];
        front = (front + 1) % capacity;
        count--;
        if (count > 0 && count == capacity / 4) {
            resize(capacity / 2);
        }
        return item;
    }

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

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

    // Return the size of the queue
    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
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution:
    def __init__(self, initial_capacity: int):
        self.arr = [None] * initial_capacity
        self.front = 0
        self.rear = 0
        self.count = 0
        self.capacity = initial_capacity

    # Resize the array to the new capacity
    def resize(self, new_capacity: int):
        new_arr = [None] * new_capacity
        for i in range(self.count):
            new_arr[i] = self.arr[(self.front + i) % self.capacity]
        self.arr = new_arr
        self.front = 0
        self.rear = self.count
        self.capacity = new_capacity

    # Enqueue operation
    def enqueue(self, item: int) -> bool:
        if self.count == self.capacity:
            self.resize(2 * self.capacity)
        self.arr[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.count += 1
        return True

    # Dequeue operation
    def dequeue(self) -> int:
        if self.is_empty():
            raise IndexError("Queue is empty")
        item = self.arr[self.front]
        self.front = (self.front + 1) % self.capacity
        self.count -= 1
        if self.count > 0 and self.count == self.capacity // 4:
            self.resize(self.capacity // 2)
        return item

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

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

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

Complexity

  • ⏰ Time complexity: 
    • Enqueue: Average O(1), Worst-case O(n) when resizing.
    • Dequeue: Average O(1), Worst-case O(n) when resizing.
    • Front: O(1).
    • isEmpty: O(1).
    • Size: O(1).
  • 🧺 Space complexity: O(n), where n is the number of elements in the queue.