队列实现栈以及栈实现队列

225. 用队列实现栈 https://leetcode.cn/problems/implement-stack-using-queues

225. Implement Stack using Queues https://leetcode.com/problems/implement-stack-using-queues

232. 用栈实现队列 https://leetcode.cn/problems/implement-queue-using-stacks

232. Implement Queue using Stacks https://leetcode.com/problems/implement-queue-using-stacks

剑指 Offer 09. 用两个栈实现队列 https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

剑指 Offer 09. 用两个栈实现队列 LCOF https://leetcode.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
225. Implement Stack using Queues	🟢
232. Implement Queue using Stacks	🟢

Prerequisites

Before reading this article, you need to study:

• Array Basics
• Linked List Basics
• Queue Basics

A queue is a First-In-First-Out (FIFO) data structure, while a stack is a Last-In-First-Out (LIFO) data structure. Here's a simple illustration:

Both of these data structures are essentially implemented using arrays or linked lists, but their APIs define their unique characteristics. For detailed implementations, refer to the Principles and Implementations of Queues/Stacks section in the basics.

Today, let's see how to use the features 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:

java 🟢

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();
}

cpp 🤖

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();
};

python 🤖

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:
        pass

go 🤖

type 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 {
    
}

javascript 🤖

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 like this might be 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 look like this:

Now, what if you want to use peek to see the front of the queue? Ideally, the front element should be 1, but in s1, 1 is at the bottom of the stack. This is where s2 comes into play: when s2 is empty, you can transfer all elements from s1 to s2. At this point, the elements in s2 are in a first-in, first-out order:

When s2 has elements, simply call the pop method on s2, and the element popped will be the first one inserted, thus simulating the queue's pop operation.

Here is the complete code:

java 🟢

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();
    }
}

cpp 🤖

#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();
    }
};

python 🤖

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.s2

go 🤖

type 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
}

javascript 🤖

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:

java 🟢

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();
}

cpp 🤖

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();
};

python 🤖

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:
        pass

go 🤖

type 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 {
}

javascript 🤖

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:

java 🟢

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();
    }
}

cpp 🤖

#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();
    }
};

python 🤖

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) == 0

go 🤖

import "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
}

javascript 🤖

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 要从队尾取元素：

解决方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了：

java 🟢

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();
    }
}

cpp 🤖

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;
    }
};

python 🤖

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)

go 🤖

// 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
}

javascript 🤖

// 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:

java 🟢

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();
    }
}

cpp 🤖

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;
    }
};

python 🤖

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)

go 🤖

// 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
}

javascript 🤖

// 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:

java 🟢

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();
    }
}

cpp 🤖

#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();
    }
};

python 🤖

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()

go 🤖

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
}

javascript 🤖

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;
    }
}

Obviously, if you use 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, using a queue to implement a stack isn't very impressive, but using two stacks to implement a queue is worth learning.

After moving elements from stack s1 to stack s2, the elements in s2 are in the queue's first-in-first-out order. This characteristic is somewhat like "two negatives make a positive" and is indeed not easy to think of.

---

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode	力扣
-	剑指 Offer 09. 用两个栈实现队列

---