Problem

A deque, also known as a double-ended queue, is a special kind of queue where insertions and deletions can be done at both the beginning and the end. A deque can be visualized as a linked list where each node points to the next node as well as the previous node, allowing constant time O(1) insertions and deletions at both ends.

Now, deque can be used to implement a stack and queue. The task is to implement a queue using a deque.

 A queue is a linear data structure that follows the First In First Out (FIFO) principle. The queue operations to implement are:

  • enqueue(x): Add element x to the end of the queue.
  • dequeue(): Removes the element from the front of the queue and returns it.
  • front(): Get the front element.
  • isEmpty(): Return whether the queue is empty.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: 
Operations: ["enqueue(1)", "enqueue(2)", "front()", "dequeue()", "isEmpty()"]
Output: 
[null, null, 1, 1, false]
Explanation: 
- enqueue(1) adds 1 to the queue.
- enqueue(2) adds 2 to the queue.
- front() returns the current front element, which is 1.
- dequeue() removes and returns the current front element, which is 1.
- isEmpty() returns false as the queue is not empty.

Solution

Method 1 - Using Deque

Given that a deque (double-ended queue) allows for insertion and deletion at both ends, we can map its operations to those of a stack and a queue appropriately. Here is a more structured explanation:

Deque Stack Queue
size() size()) size()
isEmpty() isEmpty() isEmpty()
insertFirst()
insertLast() push() enqueue()
removeFirst() dequeue()
removeLast() pop()

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

public class Solution {
    private Deque<Integer> deque;

    public Solution() {
        deque = new LinkedList<>();
    }

    // Enqueue element x to the end of the queue
    public void enqueue(int x) {
        deque.addLast(x);
    }

    // Removes the element from the front of the queue and returns it
    public int dequeue() {
        return deque.removeFirst();
    }

    // Get the front element
    public int front() {
        return deque.peekFirst();
    }

    // Return whether the queue is empty
    public boolean isEmpty() {
        return deque.isEmpty();
    }

    public static void main(String[] args) {
        Solution queue = new Solution();
        queue.enqueue(1);
        queue.enqueue(2);
        System.out.println(queue.front());     // Outputs: 1
        System.out.println(queue.dequeue());   // Outputs: 1
        System.out.println(queue.isEmpty());   // Outputs: false
        queue.enqueue(5);
        System.out.println(queue.dequeue());   // Outputs: 5
        System.out.println(queue.isEmpty());   // Outputs: true
    }
}
 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

class Solution:
    def __init__(self) -> None:
        self.deque: deque[int] = deque()

    def enqueue(self, x: int) -> None:
        self.deque.append(x)

    def dequeue(self) -> Optional[int]:
        if not self.isEmpty():
            return self.deque.popleft()
        return None

    def front(self) -> Optional[int]:
        if not self.isEmpty():
            return self.deque[0]
        return None

    def isEmpty(self) -> bool:
        return len(self.deque) == 0

# Example usage
queue = Solution()
queue.enqueue(1)
queue.enqueue(2)
print(queue.front())     # Outputs: 1
print(queue.dequeue())   # Outputs: 1
print(queue.isEmpty())   # Outputs: False
queue.enqueue(5)
print(queue.dequeue())   # Outputs: 5
print(queue.isEmpty())   # Outputs: True