Leetcode 225. Implement Stack using Queues
Problem
The problem requires us to implement a stack using only operations of a queue. A stack is a Last-In-First-Out (LIFO) data structure, meaning the last element added to the stack will be the first one to be removed. A queue on the other hand is a First-In-First-Out (FIFO) data structure, where the first element added is the first one to be removed. Therefore, we need to provide a manner to reverse the order of elements to mirror the behavior of a stack using only the operations of a queue.
The stack should support the following operations:
push(x)
: Add an element to the top of the stack.pop()
: Remove and return the top element from the stack.top()
: Get the value of the top element without removing it.empty()
: Return true if the stack is empty, false otherwise.
Example:
1
2
3stack = new MyStack();
4
5stack.push(1);
6stack.push(2);
7stack.top(); // returns 2
8stack.pop(); // returns 2
9stack.empty(); // returns false
Approach
The solution uses one queue to mimic a stack, utilizing the feature that we can rearrange queue order by popping front elements and pushing back to the queue. To simulate stack operation, whenever a new element is pushed, the element is inserted into the front of the queue. This requires moving all the older elements to the back of the queue in order to ensure the newly inserted element remains at the front, thus realising the LIFO principle.
For instance, when pushing 1 and 2:
1 2 3push 1: [1] 4push 2: [2, 1]
The top operation is straightforward since the top element of the stack is always at the front of the queue.
The pop operation is also simple as it just involves removing the front element of the queue.
The empty operation returns true if the queue is empty.
C++ Solution
1 2cpp 3class MyStack { 4public: 5 queue<int> q; 6 7 /** Initialize your data structure here. */ 8 MyStack() { 9 } 10 11 /** Push element x onto stack. */ 12 void push(int x) { 13 q.push(x); 14 for (int i = 0; i < q.size() - 1; ++i) { 15 q.push(q.front()); 16 q.pop(); 17 } 18 } 19 20 /** Removes the element on top of the stack and returns that element. */ 21 int pop() { 22 int val = q.front(); 23 q.pop(); 24 return val; 25 } 26 27 /** Get the top element. */ 28 int top() { 29 return q.front(); 30 } 31 32 /** Returns whether the stack is empty. */ 33 bool empty() { 34 return q.empty(); 35 } 36};
Java Solution
1 2java 3class MyStack { 4 5 Queue<Integer> q = new LinkedList<>(); 6 7 // Push element x onto stack. 8 public void push(int x) { 9 q.add(x); 10 for(int i = 1; i < q.size(); i++) { //rotate the queue to have last element in the front 11 q.add(q.remove()); 12 } 13 } 14 15 // Removes the element on top of the stack. 16 public int pop() { 17 return q.remove(); 18 } 19 20 // Get the top element. 21 public int top() { 22 return q.peek(); 23 } 24 25 // Return whether the stack is empty. 26 public boolean empty() { 27 return q.isEmpty(); 28 } 29}
Python Solution
1 2python 3from queue import Queue 4 5class MyStack(object): 6 7 def __init__(self): 8 self.q = Queue() 9 10 def push(self, x): 11 self.q.put(x) 12 for _ in range(self.q.qsize() - 1): 13 self.q.put(self.q.get()) 14 15 def pop(self): 16 return self.q.get() 17 18 def top(self): 19 return self.q.queue[0] # peek the front element of the queue 20 21 def empty(self): 22 return self.q.empty()
Javascript Solution
1 2javascript 3var MyStack = function() { 4 this.q = []; 5}; 6 7MyStack.prototype.push = function(x) { 8 this.q.push(x); 9 for(let i=1; i<this.q.length; i++) { 10 this.q.push(this.q.shift()); 11 } 12}; 13 14MyStack.prototype.pop = function() { 15 return this.q.shift(); 16}; 17 18MyStack.prototype.top = function() { 19 return this.q[0]; 20}; 21 22MyStack.prototype.empty = function() { 23 return this.q.length === 0; 24};
C# Solution
1
2csharp
3public class MyStack {
4
5 Queue<int> q = new Queue<int>();
6
7 // Push element x onto stack.
8 public void Push(int x) {
9 q.Enqueue(x);
10 for(int i = 1; i < q.Count; i++) {
11 q.Enqueue(q.Dequeue());
12 }
13 }
14
15 // Removes the element from in front of stack.
16 public int Pop() {
17 return q.Dequeue();
18 }
19
20 // Get the front element.
21 public int Top() {
22 return q.Peek();
23 }
24
25 // Return whether the stack is empty.
26 public bool Empty() {
27 return q.Count == 0;
28 }
29}
All these solutions have a time complexity of O(n) for the push operation and O(1) for the pop, top, and empty operations. The space complexity is O(n), where n is the number of elements in the stack.# PHP Solution
1
2php
3class MyStack {
4 private $queue;
5
6 public function __construct() {
7 $this->queue = new SplQueue();
8 }
9
10 public function push($x) {
11 $this->queue->enqueue($x);
12 for($i = 1; $i < count($this->queue); $i++) {
13 $this->queue->enqueue($this->queue->dequeue());
14 }
15 }
16
17 public function pop() {
18 return $this->queue->dequeue();
19 }
20
21 public function top() {
22 return $this->queue->bottom();
23 }
24
25 public function empty() {
26 return count($this->queue) == 0;
27 }
28}
A PHP solution is also possible by using the SplQueue
class provided by the Standard PHP Library (SPL). The enqueue
method is used to add elements to the top of the stack while dequeue
is used to remove elements from the bottom of the stack. The bottom
method is used to peek at the bottom element of the queue which simulates the stack's top operation. The empty
method checks whether the stack is empty by comparing the count of the elements in the queue to zero.
Ruby Solution
1 2ruby 3class MyStack 4 attr_accessor :queue 5 6 def initialize 7 @queue = [] 8 end 9 10 def push(x) 11 @queue.push(x) 12 (1...@queue.size).each { @queue.push(@queue.shift) } 13 end 14 15 def pop 16 @queue.shift 17 end 18 19 def top 20 @queue.first 21 end 22 23 def empty 24 @queue.empty? 25 end 26end
In Ruby, we can simply use an array to simulate a queue. The push
method adds an element to the array and rearranges the remaining elements to ensure the newly added element is on top. The shift
method removes and returns the first element in the array replicating a stack's pop operation. The first
method returns the first element in the array mirroring a stack's top operation. The empty
method checks if the array is empty reflecting a stack's empty operation.
Swift Solution
1
2swift
3class MyStack {
4 var queue: [Int]
5
6 init() {
7 self.queue = []
8 }
9
10 func push(_ x: Int) {
11 self.queue.insert(x, at: 0)
12 for _ in 1..<self.queue.count {
13 self.queue.insert(self.queue.popLast()!, at: 0)
14 }
15 }
16
17 func pop() -> Int {
18 return self.queue.removeFirst()
19 }
20
21 func top() -> Int {
22 return self.queue.first!
23 }
24
25 func empty() -> Bool {
26 return self.queue.isEmpty
27 }
28}
In Swift, an array can also be used to mimic a queue. The insert(_:at:)
and popLast()
functions enable manipulation of the array to simulate stack-like behavior. The removeFirst()
, first
and isEmpty
properties are used to implement the pop, top and empty operations respectively.
These solutions all have a time complexity of O(n) for the push operation and O(1) for the pop, top and empty operations. The space complexity is O(n) where n is the number of elements in the stack.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.