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 stack using a deque.

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

  • push(x): Push element x onto the stack.
  • pop(): Removes the element on top of the stack and returns it.
  • top(): Get the top element.
  • isEmpty(): Return whether the stack is empty.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

 Input: 
 Operations: ["push(1)", "push(2)", "top()", "pop()", "isEmpty()"]
 Output: 
 [null, null, 2, 2, false]
 Explanation: 
 - push(1) adds 1 to the stack.
 - push(2) adds 2 to the stack.
 - top() returns the current top element, which is 2.
 - pop() removes and returns the current top element, which is 2.
 - isEmpty() returns false as the stack 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<>();
    }

    // Push element x onto stack
    public void push(int x) {
        deque.addLast(x);
    }

    // Removes the element on top of the stack and returns it
    public int pop() {
        return deque.removeLast();
    }

    // Get the top element
    public int top() {
        return deque.peekLast();
    }

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

    public static void main(String[] args) {
        Solution stack = new Solution();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.top());     // Outputs: 2
        System.out.println(stack.pop());     // Outputs: 2
        System.out.println(stack.isEmpty()); // Outputs: false
        stack.push(5);
        System.out.println(stack.pop());     // Outputs: 5
        System.out.println(stack.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

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

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

    def pop(self) -> int:
        return self.deque.pop()

    def top(self) -> int:
        return self.deque[-1]

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

# Example usage
stack = Solution()
stack.push(1)
stack.push(2)
print(stack.top())     # Outputs: 2
print(stack.pop())     # Outputs: 2
print(stack.isEmpty()) # Outputs: False
stack.push(5)
print(stack.pop())     # Outputs: 5
print(stack.isEmpty()) # Outputs: True