Implement Stack with Queue, Implement Queue with Stack
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 225. Implement Stack using Queues | 🟢 |
| 232. Implement Queue using Stacks | 🟢 |
Prerequisite Knowledge
Before reading this article, you should first learn:
A queue is a data structure that follows the first-in, first-out (FIFO) principle, while a stack follows the first-in, last-out (FILO) principle. Here's a simple illustration:
Both of these data structures are fundamentally implemented using arrays or linked lists, with their characteristics defined by the API. For detailed implementation, refer to the foundational chapter on Principles and Implementation of Queues/Stacks.
Today, we'll explore how to use the characteristics of a "stack" to implement a "queue" and how to use a "queue" to implement a "stack."
1. Implementing a Queue Using Stacks
LeetCode Problem 232, "Implement Queue using Stacks," requires us to implement the following API:
class MyQueue {
// add element to the end of the queue
public void push(int x);
// remove the element at the front of the queue and return it
public int pop();
// return the front element
public int peek();
// check if the queue is empty
public boolean empty();
}class MyQueue {
public:
// add element to the end of the queue
void push(int x);
// delete the front element of the queue and return it
int pop();
// return the front element
int peek();
// check if the queue is empty
bool empty();
};class MyQueue:
# add element to the back of the queue
def push(self, x: int) -> None:
pass
# remove and return the front element of the queue
def pop(self) -> int:
pass
# return the front element of the queue
def peek(self) -> int:
pass
# check if the queue is empty
def empty(self) -> bool:
passtype MyQueue struct {}
// add element to the end of the queue
func (q *MyQueue) push(x int) {
}
// remove and return the element at the front of the queue
func (q *MyQueue) pop() int {
return 0
}
// return the element at the front of the queue
func (q *MyQueue) peek() int {
}
// check if the queue is empty
func (q *MyQueue) empty() bool {
}var MyQueue = function() {
// add element to the end of the queue
this.push = function(x) {
}
// remove and return the front element of the queue
this.pop = function() {
}
// return the front element of the queue
this.peek = function() {
}
// check if the queue is empty
this.empty = function() {
}
}We can use two stacks, s1 and s2, to implement the functionality of a queue (arranging the stacks this way might make it easier to understand):
When calling push to enqueue an element, simply push the element into s1. For example, if you push three elements, 1, 2, and 3, the underlying structure will be as follows:
Now, what if you use peek to view the front element of the queue? Logically, the front element should be 1, but in s1, 1 is at the bottom of the stack. This is where s2 comes into play as an intermediary: when s2 is empty, transfer all elements from s1 to s2. At this point, the elements in s2 are in a first-in, first-out order:
When there are elements in s2, directly call the pop operation on s2, and the element popped will be the one that was inserted first, thus achieving the queue's pop operation.
The complete code is as follows:
class MyQueue {
private Stack<Integer> s1, s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
// add element to the end of the queue
public void push(int x) {
s1.push(x);
}
// return the front element of the queue
public int peek() {
if (s2.isEmpty())
// push elements from s1 to s2
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
return s2.peek();
}
// remove the front element and return it
public int pop() {
// call peek to ensure s2 is not empty
peek();
return s2.pop();
}
// check if the queue is empty
// the queue is empty only if both stacks are empty
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}#include <stack>
class MyQueue {
private:
std::stack<int> s1, s2;
public:
MyQueue() {
}
// add element to the end of the queue
void push(int x) {
s1.push(x);
}
// return the front element
int peek() {
if (s2.empty())
// push elements from s1 to s2
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
return s2.top();
}
// delete the front element and return
int pop() {
// call peek first to ensure s2 is not empty
peek();
int poppedValue = s2.top();
s2.pop();
return poppedValue;
}
// check if the queue is empty
// the queue is empty only if both stacks are empty
bool empty() {
return s1.empty() && s2.empty();
}
};class MyQueue:
def __init__(self):
# use two stacks s1 and s2
self.s1 = []
self.s2 = []
# add element to the end of the queue
def push(self, x: int) -> None:
self.s1.append(x)
# return the front element of the queue
def peek(self) -> int:
if not self.s2:
# push elements from s1 to s2
while self.s1:
self.s2.append(self.s1.pop())
return self.s2[-1]
# remove and return the front element of the queue
def pop(self) -> int:
# call peek first to ensure s2 is not empty
self.peek()
return self.s2.pop()
# check if the queue is empty
# the queue is empty if both stacks are empty
def empty(self) -> bool:
return not self.s1 and not self.s2type MyQueue struct {
s1, s2 []int
}
func Constructor() MyQueue {
return MyQueue{
s1: make([]int, 0),
s2: make([]int, 0),
}
}
// add element to the back of the queue
func (this *MyQueue) Push(x int) {
this.s1 = append(this.s1, x)
}
// return the front element
func (this *MyQueue) Peek() int {
if len(this.s2) == 0 {
// push elements from s1 to s2
for len(this.s1) > 0 {
this.s2 = append(this.s2, this.s1[len(this.s1)-1])
this.s1 = this.s1[:len(this.s1)-1]
}
}
return this.s2[len(this.s2)-1]
}
// remove and return the front element
func (this *MyQueue) Pop() int {
// call peek first to ensure s2 is not empty
this.Peek()
retval := this.s2[len(this.s2)-1]
this.s2 = this.s2[:len(this.s2)-1]
return retval
}
// check if the queue is empty
// the queue is empty if both stacks are empty
func (this *MyQueue) Empty() bool {
return len(this.s1) == 0 && len(this.s2) == 0
}var MyQueue = function() {
// create two stacks s1 and s2
this.s1 = [];
this.s2 = [];
};
// add element to the end of the queue
MyQueue.prototype.push = function(x) {
this.s1.push(x);
};
// return the front element of the queue
MyQueue.prototype.peek = function() {
// if s2 is empty, push elements from s1 to s2
if (this.s2.length == 0)
while (this.s1.length) {
this.s2.push(this.s1.pop());
}
// return the top element of s2
return this.s2[this.s2.length-1];
};
// remove the front element of the queue and return it
MyQueue.prototype.pop = function() {
// call peek first to ensure s2 is not empty
this.peek();
// then return the top element of s2
return this.s2.pop();
};
// check if the queue is empty
MyQueue.prototype.empty = function() {
// the queue is empty if both stacks are empty
return this.s1.length == 0 && this.s2.length == 0;
};At this point, we have implemented a queue using a stack structure. The core idea is to use two stacks to complement each other.
An interesting question is, what is the time complexity of these operations?
The peek operation stands out. When called, it may trigger a while loop, making the time complexity O(N). However, in most cases, the while loop won't be triggered, so the time complexity is O(1). Since the pop operation calls peek, its time complexity is the same as peek.
In such scenarios, we can say their worst-case time complexity is O(N) because the while loop might need to move elements from s1 to s2.
However, their amortized time complexity is O(1). This is understood as: each element is moved at most once. That is, the time complexity of the peek operation averaged over each element is O(1).
For more on analyzing time complexity, see Practical Methods for Time Complexity Analysis.
2. Implementing a Stack Using a Queue
If implementing a queue with two stacks is clever, then implementing a stack with a queue is relatively straightforward. You only need a single queue as the underlying data structure.
LeetCode problem 225 "Implement Stack Using Queues" asks us to implement the following API:
class MyStack {
// add element to the top of the stack
public void push(int x);
// remove the top element of the stack and return it
public int pop();
// return the top element of the stack
public int top();
// check if the stack is empty
public boolean empty();
}class MyStack {
// add element to the top of the stack
void push(int x);
// remove the top element of the stack and return it
int pop();
// return the top element of the stack
int top();
// check if the stack is empty
bool empty();
};class MyStack:
# push element onto stack
def push(self, x: int) -> None:
pass
# remove the top element and return it
def pop(self) -> int:
pass
# return the top element
def top(self) -> int:
pass
# check if the stack is empty
def empty(self) -> bool:
passtype MyStack struct {
}
// add element to the top of the stack
func (s *MyStack) Push(x int) {
}
// remove the top element of the stack and return it
func (s *MyStack) Pop() int {
}
// return the top element of the stack
func (s *MyStack) Top() int {
}
// check if the stack is empty
func (s *MyStack) Empty() bool {
}var MyStack = function() {
// add element to the top of the stack
this.push = function(x) {
};
// remove the top element of the stack and return it
this.pop = function() {
};
// return the top element of the stack
this.top = function() {
};
// check if the stack is empty
this.empty = function() {
};
};First, let's talk about the push API. It directly adds an element to the queue and records the last element, because the last element in the queue is equivalent to the top element of the stack. If you want to top to view the top element of the stack, you can directly return it:
class MyStack {
Queue<Integer> q = new LinkedList<>();
int top_elem = 0;
// add element to the top of the stack
public void push(int x) {
// x is the tail of the queue, which is the top of the stack
q.offer(x);
top_elem = x;
}
// return the top element of the stack
public int top() {
return top_elem;
}
public boolean empty() {
return q.isEmpty();
}
}#include<queue>
using namespace std;
class MyStack {
queue<int> q;
int top_elem = 0;
public:
// add element to the top of the stack
void push(int x) {
// x is the tail of the queue, which is the top of the stack
q.push(x);
top_elem = x;
}
// return the top element of the stack
int top() {
return top_elem;
}
bool empty() {
return q.empty();
}
};class MyStack:
def __init__(self):
# use a queue q to implement a stack
self.q = []
# top element of the stack
self.top_elem = 0
# add an element to the top of the stack
def push(self, x: int) -> None:
# x is the rear of the queue, which is the top of the stack
self.q.append(x)
self.top_elem = x
# return the top element of the stack
def top(self) -> int:
return self.top_elem
# check if the stack is empty
def empty(self) -> bool:
return len(self.q) == 0import "container/list"
type MyStack struct {
q *list.List
top_elem int
}
// MyStack constructor
func Constructor() MyStack {
return MyStack{q: list.New()}
}
// push an element onto the stack
func (this *MyStack) Push(x int) {
// x is the tail of the queue, which is the top of the stack
this.q.PushBack(x)
this.top_elem = x
}
// return the top element of the stack
func (this *MyStack) Top() int {
return this.top_elem
}
// check if the stack is empty
func (this *MyStack) Empty() bool {
return this.q.Len() == 0
}var MyStack = function() {
this.q = [];
this.top_elem = 0;
};
// push element to the top of the stack
MyStack.prototype.push = function(x) {
// x is the tail of the queue, which is the top of the stack
this.q.push(x);
this.top_elem = x;
};
// return the top element of the stack
MyStack.prototype.top = function() {
return this.top_elem;
};
MyStack.prototype.empty = function() {
return this.q.length === 0;
};我们的底层数据结构是先进先出的队列，每次 pop 只能从队头取元素；但是栈是后进先出，也就是说 pop API 要从队尾取元素：
解决方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了：
class MyStack {
// To save space, the code above is omitted...
// Delete the top element of the stack and return it
public int pop() {
int size = q.size();
while (size > 1) {
q.offer(q.poll());
size--;
}
// The previous last element of the queue is now at the front
return q.poll();
}
}class MyStack {
// To save space, the code above is omitted...
// remove and return the top element of the stack
int pop() {
int size = q.size();
while (size > 1) {
q.push(q.front());
q.pop();
size--;
}
// the previous last element of the queue is now at the front
int res = q.front();
q.pop();
return res;
}
};class MyStack:
# To save space, the code provided above is omitted...
# Remove the top element of the stack and return it
def pop(self):
size = len(self.q)
while size > 1:
self.q.append(self.q.pop(0))
size -= 1
# The previous last element of the queue is now at the front
return self.q.pop(0)// To save space, the code given above is omitted...
func (this *MyStack) Pop() int {
size := len(this.q)
for size > 1 {
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
size--
}
// The previous tail element of the queue has moved to the front
poppedElement := this.q[0]
this.q = this.q[1:]
return poppedElement
}// To save space, the code portion given above is omitted...
MyStack.prototype.pop = function() {
var size = this.q.length;
while (size > 1) {
this.q.push(this.q.shift());
size--;
}
// the previous tail element of the queue is now at the head
return this.q.shift();
};There is a small issue with this implementation: the original element at the end of the queue is pushed to the front and removed, but the top_elem variable is not updated. We need to make a small adjustment:
class MyStack {
// To save space, the code given above is omitted...
// remove the top element and return it
public int pop() {
int size = q.size();
// leave the last 2 elements
while (size > 2) {
q.offer(q.poll());
size--;
}
// record the new last element
top_elem = q.peek();
q.offer(q.poll());
// remove the previous last element
return q.poll();
}
}class MyStack {
// To save space, the code given above is omitted...
// Remove the top element of the stack and return it
public:
int pop() {
int size = q.size();
// Leave the last 2 elements in the queue
while (size > 2) {
q.push(q.front());
q.pop();
size--;
}
// Record the new last element of the queue
top_elem = q.front();
q.push(q.front());
q.pop();
// Remove the previous last element of the queue
int target = q.front();
q.pop();
return target;
}
};class MyStack:
# To save space, the code given above is omitted...
# Remove the top element of the stack and return it
def pop(self):
size = len(self.q)
# Keep the last 2 elements of the queue
while size > 2:
self.q.append(self.q.pop(0))
size -= 1
# Record the new last element of the queue
self.top_elem = self.q[0]
self.q.append(self.q.pop(0))
# Remove the previous last element of the queue
return self.q.pop(0)// To save space, the code given above is omitted...
// Remove the top element of the stack and return it
func (this *MyStack) Pop() int {
size := len(this.q)
// Leave the last 2 elements in the queue
for size > 2 {
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
size--
}
// Record the new last element in the queue
top_elem := this.q[0]
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
// Remove the previous last element in the queue
result := this.q[0]
this.q = this.q[1:]
return result
}// omit the previously given code part...
// remove the top element of the stack and return it
MyStack.prototype.pop = function() {
var size = this.q.length;
// leave the last 2 elements in the queue
while (size > 2) {
this.q.push(this.q.shift());
size--;
}
// record the new last element of the queue
this.top_elem = this.q[0];
this.q.push(this.q.shift());
// remove the previous last element of the queue
return this.q.shift();
}That's it, the implementation is complete. The full code is as follows:
class MyStack {
Queue<Integer> q = new LinkedList<>();
int top_elem = 0;
// add element to the top of the stack
public void push(int x) {
q.offer(x);
top_elem = x;
}
// remove the top element of the stack and return it
public int pop() {
int size = q.size();
while (size > 2) {
q.offer(q.poll());
size--;
}
top_elem = q.peek();
q.offer(q.poll());
return q.poll();
}
// return the top element of the stack
public int top() {
return top_elem;
}
// check if the stack is empty
public boolean empty() {
return q.isEmpty();
}
}#include <queue>
class MyStack {
private:
std::queue<int> q;
int top_elem = 0;
public:
// push element onto stack
void push(int x) {
q.push(x);
top_elem = x;
}
// remove the top element and return it
int pop() {
int size = q.size();
while (size > 2) {
q.push(q.front());
q.pop();
size--;
}
top_elem = q.front();
q.push(q.front());
q.pop();
int value = q.front();
q.pop();
return value;
}
// return the top element
int top() {
return top_elem;
}
// check if the stack is empty
bool empty() {
return q.empty();
}
};from queue import Queue
class MyStack:
def __init__(self):
self.q = Queue()
self.top_elem = 0
# add element to the top of the stack
def push(self, x: int) -> None:
self.q.put(x)
self.top_elem = x
# remove the top element of the stack and return it
def pop(self) -> int:
size = self.q.qsize()
while size > 2:
self.q.put(self.q.get())
size -= 1
self.top_elem = self.q.queue[0]
self.q.put(self.q.get())
return self.q.get()
# return the top element of the stack
def top(self) -> int:
return self.top_elem
# check if the stack is empty
def empty(self) -> bool:
return self.q.empty()type MyStack struct {
q []int
topElement int
}
func Constructor() MyStack {
return MyStack{}
}
// add element to the top of the stack
func (this *MyStack) Push(x int) {
this.q = append(this.q, x)
this.topElement = x
}
// remove the top element of the stack and return it
func (this *MyStack) Pop() int {
size := len(this.q)
for i := 0; i < size - 2; i++ {
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
}
this.topElement = this.q[0]
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
popElement := this.q[0]
this.q = this.q[1:]
return popElement
}
// return the top element of the stack
func (this *MyStack) Top() int {
return this.topElement
}
// check if the stack is empty
func (this *MyStack) Empty() bool {
return len(this.q) == 0
}var MyStack = function() {
this.q = [];
this.top_elem = 0;
// add element to the top of the stack
this.push = function(x) {
this.q.push(x);
this.top_elem = x;
}
// remove the top element of the stack and return it
this.pop = function() {
var size = this.q.length;
while (size > 2) {
this.q.push(this.q.shift());
size--;
}
this.top_elem = this.q[0];
this.q.push(this.q.shift());
return this.q.shift();
}
// return the top element of the stack
this.top = function() {
return this.top_elem;
}
// check if the stack is empty
this.empty = function() {
return this.q.length === 0;
}
}It is clear that when using a queue to implement a stack, the pop operation has a time complexity of O(N), while other operations are O(1).
In my opinion, implementing a stack with a queue isn't particularly interesting, but implementing a queue with two stacks is worth learning.
After transferring elements from stack s1 to s2, the elements in s2 follow the queue's first-in-first-out order. This feature is somewhat similar to the concept of "a double negative makes a positive," which is indeed not easy to think of.