Back to DSA
Implement Stack using Queues
easyBuild a LIFO stack using only queue operations (enqueue at back, dequeue from front, peek at front, check if empty). Your MyStack class must provide push, pop, top, and empty, behaving identically to a standard stack.
Examples
Example 1:
Input:
MyStack(), push(3), push(7), top(), pop(), empty()Output:
[null,null,null,7,7,false]Hints
import java.util.*;
class MyStack {
private Queue<Integer> queue = new LinkedList<>();
public void push(int x) {
queue.offer(x);
for (int i = 0; i < queue.size() - 1; i++) queue.offer(queue.poll());
}
public int pop() { return queue.poll(); }
public int top() { return queue.peek(); }
public boolean empty() { return queue.isEmpty(); }
}Time complexity
O(n) for push, O(1) for othersSpace complexity
O(n)