Stacks & QueuesProblem 21 of 38
Implement Stack using Deque
Problem Statement
Implement a Stack using a Deque (Double-ended Queue). The stack should support the following operations efficiently:
push(x): Push element x onto the stackpop(): Remove and return the top elementtop(): Return the top element without removing itempty(): Return whether the stack is empty
Example:
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.top(); // returns 3
stack.pop(); // returns 3
stack.pop(); // returns 2
stack.empty(); // returns false
Approach 1: Using Back Operations
Intuition
A deque supports operations at both ends in O(1) time. To implement a stack, we can use one end consistently. Using the back of the deque for all operations naturally implements LIFO behavior.
Algorithm
- For push(x): Add element to the back of deque
- For pop(): Remove and return element from the back
- For top(): Return the element at the back
- For empty(): Check if deque is empty
java
import java.util.*;
class MyStack {
private Deque<Integer> dq;
public MyStack() {
dq = new ArrayDeque<>();
}
// O(1)
public void push(int x) {
dq.addLast(x);
}
// O(1)
public int pop() {
return dq.removeLast();
}
// O(1)
public int top() {
return dq.peekLast();
}
// O(1)
public boolean empty() {
return dq.isEmpty();
}
// O(1)
public int size() {
return dq.size();
}
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Top: " + stack.top()); // 3
System.out.println("Pop: " + stack.pop()); // 3
System.out.println("Pop: " + stack.pop()); // 2
System.out.println("Empty: " + stack.empty()); // false
}
}Complexity Analysis
- Time Complexity: O(1) for all operations
- Space Complexity: O(n) - storing n elements
Approach 2: Using Front Operations
Intuition
Alternatively, we can use the front of the deque for all operations. This also implements LIFO behavior since we're consistently adding and removing from the same end.
Algorithm
- For push(x): Add element to the front of deque
- For pop(): Remove and return element from the front
- For top(): Return the element at the front
- For empty(): Check if deque is empty
java
import java.util.*;
class MyStack {
private Deque<Integer> dq;
public MyStack() {
dq = new ArrayDeque<>();
}
// O(1)
public void push(int x) {
dq.addFirst(x);
}
// O(1)
public int pop() {
return dq.removeFirst();
}
// O(1)
public int top() {
return dq.peekFirst();
}
// O(1)
public boolean empty() {
return dq.isEmpty();
}
// O(1)
public int size() {
return dq.size();
}
}Complexity Analysis
- Time Complexity: O(1) for all operations
- Space Complexity: O(n) - storing n elements
Approach 3: Complete Implementation with Additional Features
Intuition
Implement a more complete stack with additional utility functions like peek(), search(), and displaying the stack contents.
Algorithm
- Basic operations: push, pop, top, empty
- Additional operations: size, search, display
- Error handling for operations on empty stack
java
import java.util.*;
class MyStack {
private Deque<Integer> dq;
public MyStack() {
dq = new ArrayDeque<>();
}
public void push(int x) {
dq.addLast(x);
}
public int pop() {
if (empty()) {
throw new RuntimeException("Stack is empty");
}
return dq.removeLast();
}
public int top() {
if (empty()) {
throw new RuntimeException("Stack is empty");
}
return dq.peekLast();
}
public boolean empty() {
return dq.isEmpty();
}
public int size() {
return dq.size();
}
// Returns 1-based position from top, -1 if not found
public int search(int x) {
int pos = 1;
Iterator<Integer> it = dq.descendingIterator();
while (it.hasNext()) {
if (it.next() == x) return pos;
pos++;
}
return -1;
}
public void display() {
System.out.print("Stack (top to bottom): ");
Iterator<Integer> it = dq.descendingIterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println();
}
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.display(); // 40 30 20 10
System.out.println("Top: " + stack.top()); // 40
System.out.println("Size: " + stack.size()); // 4
System.out.println("Search 20: " + stack.search(20)); // 3
System.out.println("Search 50: " + stack.search(50)); // -1
System.out.println("Pop: " + stack.pop()); // 40
stack.display(); // 30 20 10
}
}Complexity Analysis
- Time Complexity: O(1) for push, pop, top, empty, size; O(n) for search
- Space Complexity: O(n) - storing n elements
Key Takeaways
- Deque Advantage: Deque provides O(1) operations at both ends, making stack implementation trivial
- Consistent End: Use either front or back consistently - both work equally well
- Flexibility: Deque can implement both stack (LIFO) and queue (FIFO) efficiently
- Preferred Choice: In practice, deque is often preferred over vector/list for stack implementation
- ArrayDeque in Java: Java's ArrayDeque is faster than LinkedList for stack operations
- This is a simpler variant compared to implementing stack using queues