用栈实现队列 ( LeetCode 232 )

一、题目描述

请你仅使用两个栈实现先入先出队列。

队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

实现 MyQueue 类:

  • void push(int x)将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty()如果队列为空,返回 true ;否则,返回 false

二、题目解析

入队操作

如果是栈的插入操作,那我们可以把元素都先插入到 stackIn 中,也就实现了队列的 入队操作

出队操作

  • 当 stackOut 中不为空时,直接操作,此时在 stackOut 中的栈顶元素是最先进入队列的元素,返回该元素即可;
  • 如果 stackOut 为空且 stackIn 不为空,首先需要把 stackIn 中的元素逐个弹出并压入到 stackOut 中,然后返回 stackOut 的栈顶元素即可。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 用栈实现队列 ( LeetCode 232 ):https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue {
    // 首先定义好两个栈

    // 一个栈叫做 stackIn,负责进栈操作,相当于队列 queue 中的入队操作
    Stack<Integer> stackIn;
    // 一个栈叫做 stackOut,负责出栈操作,相当于队列 queue 中的出队操作
    Stack<Integer> stackOut;

    public MyQueue() {
        // 在这个函数中初始化两个栈,传入的参数为空,返回也为空

        // 初始化 stackIn
        stackIn = new Stack<>();
        // 初始化 stackOut
        stackOut = new Stack<>();
    }


    public void push(int x) {
        // 新添加的元素添加到 stackIn 中
        stackIn.push(x);
    }

    public int pop() {

        // 如果 stackOut 为空,首先需要将 stackIn 中的所有元素添加到 stackOut 中
        // 注意 stackIn 是栈,栈的性质是先进后出,后进先出,所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if (stackOut.isEmpty()) {
            // 通过 while 循环将 stackIn 中的所有元素都取出
            while (!stackIn.isEmpty()) {
                // stackOut 不断的添加 stackIn 的栈顶元素
                stackOut.push(stackIn.pop());
            }
        }
        // 此时,stackIn 已经为空,直接「移除」 stackOut 的栈顶元素
        return stackOut.pop();
    }


    public int peek() {

        // peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        // 如果 stackOut 为空,首先需要将 stackIn 中的所有元素添加到 stackOut 中
        // 注意 stackIn 是栈,栈的性质是先进后出,后进先出,所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if (stackOut.isEmpty()) {
            // 通过 while 循环将 stackIn 中的所有元素都取出
            while (!stackIn.isEmpty()) {
                // stackOut 不断的添加 stackIn 的栈顶元素
                stackOut.push(stackIn.pop());
            }
        }

        // peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        // 此时,stackIn 已经为空,直接「返回」 stackOut 的栈顶元素
        return stackOut.peek();

    }

    public boolean empty() {
        // 队列是否为空,判断 stackIn 和 stackOut 是否同时不存在元素
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 用栈实现队列 ( LeetCode 232 ):https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue {
public:
 // 首先定义好两个栈

    // 一个栈叫做 stackIn,负责进栈操作,相当于队列 queue 中的入队操作
    stack<int> stackIn;
    // 一个栈叫做 stackOut,负责出栈操作,相当于队列 queue 中的出队操作
    stack<int> stackOut;

    MyQueue() {

    }


    void push(int x) {
        // 新添加的元素添加到 stackIn 中
        stackIn.push(x);
    }

    int pop() {

        // 如果 stackOut 为空,首先需要将 stackIn 中的所有元素添加到 stackOut 中
        // 注意 stackIn 是栈,栈的性质是先进后出,后进先出,所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if (stackOut.empty()){
            // 通过 while 循环将 stackIn 中的所有元素都取出
            while (!stackIn.empty()) {
                // stackOut 不断的添加 stackIn 的栈顶元素
                int pop = stackIn.top();

                stackIn.pop();

                stackOut.push(pop);
            }
        }
        // 此时,stackIn 已经为空,直接「移除」 stackOut 的栈顶元素

        int pop = stackOut.top();

        stackOut.pop();

        return pop;
    }


    int peek() {

        // peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        // 如果 stackOut 为空,首先需要将 stackIn 中的所有元素添加到 stackOut 中
        // 注意 stackIn 是栈,栈的性质是先进后出,后进先出,所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if (stackOut.empty()) {
            // 通过 while 循环将 stackIn 中的所有元素都取出
            while (!stackIn.empty()) {
                // stackOut 不断的添加 stackIn 的栈顶元素
                int pop = stackIn.top();

                stackIn.pop();

                stackOut.push(pop);
            }
        }

        // peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        // 此时,stackIn 已经为空,直接「返回」 stackOut 的栈顶元素
        return stackOut.top();

    }

    bool empty() {
        // 队列是否为空,判断 stackIn 和 stackOut 是否同时不存在元素
        return stackIn.empty() && stackOut.empty();
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 用栈实现队列 ( LeetCode 232 ):https://leetcode-cn.com/problems/implement-queue-using-stacks/
class MyQueue:
    def __init__(self):
        # 一个栈叫做 stackIn,负责进栈操作,相当于队列 queue 中的入队操作
        self.stackIn = []
        # 一个栈叫做 stackOut,负责出栈操作,相当于队列 queue 中的出队操作
        self.stackOut = []


    def push(self, x: int) -> None:
        # 新添加的元素添加到 stackIn 中
        self.stackIn.append(x)


    def pop(self) -> int:
        # 如果 stackOut 为空,首先需要将 stackIn 中的所有元素添加到 stackOut 中
        #注意 stackIn 是栈,栈的性质是先进后出,后进先出,所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if not self.stackOut:
            # 通过 while 循环将 stackIn 中的所有元素都取出
            while self.stackIn:
                # stackOut 不断的添加 stackIn 的栈顶元素
                self.stackOut.append(self.stackIn.pop())
        # 此时,stackIn 已经为空,直接「移除」 stackOut 的栈顶元素
        return self.stackOut.pop()


    def peek(self) -> int:
        # peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        # 如果 stackOut 为空,首先需要将 stackIn 中的所有元素添加到 stackOut 中
        # 注意 stackIn 是栈,栈的性质是先进后出,后进先出,所以是不断的将 stackIn 中的栈顶元素添加进 stackOut 中
        if not self.stackOut:
            # 通过 while 循环将 stackIn 中的所有元素都取出
            while self.stackIn:
                # stackOut 不断的添加 stackIn 的栈顶元素
                self.stackOut.append(self.stackIn.pop())

        # peek 和 pop 的区别在于是返回栈顶元素而非删除栈顶元素
        # 此时,stackIn 已经为空,直接「返回」 stackOut 的栈顶元素
        return self.stackOut[-1]


    def empty(self) -> bool:
        # 队列是否为空,判断 stackIn 和 stackOut 是否同时不存在元素
        return not self.stackIn and not self.stackOut

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注