Implement queue using deque

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.

deque-example.excalidraw

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:

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

Java

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
    }
}

Python

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

Problem#

Examples#

Example 1:#

Solution#

Method 1 - Using Deque#

Code#

Java#

Python#