1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 9-1 题] “用两个栈实现队列”做题记录

[剑指 Offer 第 2 版第 9-1 题] “用两个栈实现队列”做题记录

第 9-1 题:用两个栈实现队列

传送门:AcWing:用两个栈实现队列牛客网 online judge 地址

请用栈实现一个队列,支持如下四种操作:

  • push(x) – 将元素x插到队尾;
  • pop() – 将队首的元素弹出,并返回该元素;
  • peek() – 返回队首元素;
  • empty() – 返回队列是否为空;

注意:

  • 你只能使用栈的标准操作:push to toppeek/pop from top, sizeis empty
  • 如果你选择的编程语言没有栈的标准库,你可以使用list或者deque等模拟栈的操作;
  • 输入数据保证合法,例如,在队列为空时,不会进行pop或者peek等操作;

样例

``` MyQueue queue = new MyQueue();

queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false ```

分析:+ 相关的练习还有 LeetCode 第 232 题,还有第 225 题。 + 在这里我设置了一个“上一次的操作”作为状态。具体应用如下:

如果“上一次的操作”是 push:

1、我继续 push 的时候,就可以继续往栈里存数据;
2、但是如果我 pop 的话,就要把“栈底”的元素拿出来,拿出之前,要把“栈底”以上的所有元素弹出到另一个栈中。此时,如果继续出队的话,就从临时栈中陆续弹出“栈顶”元素就可以了。

如果“上一次的操作”是 pop:

1、如果我继续 pop,因为在上一次 pop 的时候,就把之前那个栈中的元素全部弹出到一个新的栈,此时这个新栈继续弹出“栈顶”元素,其实就是原来入队的顺序;
2、如果我 push,就得恢复之前入队的顺序,因此,要把这个栈中的数据全部弹出到之前入队的那个栈。

总而言之,我们可以准备两个栈 stack1 和 stack2 :
1、使用 stack1 专门用于 push 的时候用,要“出队”之前,全部弹出到 stack2,从 stack2 弹出 ;
2、使用 stack2 专门用于 pop 的时候用,要“入队”之前,全部弹出到 stack1,从 stack1 压入 。

Java 代码:

  import java.util.Stack;

    public class Solution {
        /**
         * 专门 push 的时候用
         */
        private Stack<Integer> stack1 = new Stack<Integer>();
        /**
         * 专门 pop 的时候用
         */
        private Stack<Integer> stack2 = new Stack<Integer>();

        private State lastState = State.PUSH;

        enum State {
            PUSH, POP
        }

        public void push(int node) {
            if (lastState == State.PUSH) {
                stack1.add(node);
            } else {
                assert lastState == State.POP;
                // 如果上一步是 pop 的话,
                while (!stack2.isEmpty()) {
                    stack1.add(stack2.pop());
                }
                stack1.add(node);
                lastState = State.PUSH;
            }
        }

        public int pop() {
            if (lastState == State.POP) {
                if (stack2.empty()) {
                    throw new IllegalArgumentException("queue is empty");
                }
                return stack2.pop();
            } else {
                // 如果上一步是 PUSH 的话
                while (!stack1.empty()) {
                    stack2.add(stack1.pop());
                }
                lastState = State.POP;
                return stack2.pop();
            }
        }
    }

注意:下面这个逻辑是错的,应该是只要 stack2 是空的,才把 stack1 的元素全部搬到 stack2,这里要小心。

      def __shift(self):
            if self.stack1:
                while self.stack1:
                    self.stack2.append(self.stack1.pop())

Python 代码:

  class MyQueue(object):

        def __init__(self):
            """
            Initialize your data structure here.
            """

            self.stack1 = []
            self.stack2 = []

        def push(self, x):
            """
            Push element x to the back of queue.
            :type x: int
            :rtype: void
            """
            self.stack1.append(x)

        def __shift(self):
            if len(self.stack2) == 0:
                while self.stack1:
                    self.stack2.append(self.stack1.pop())

        def pop(self):
            """
            Removes the element from in front of queue and returns that element.
            :rtype: int
            """
            self.__shift()
            return self.stack2.pop()

        def peek(self):
            """
            Get the front element.
            :rtype: int
            """
            self.__shift()
            return self.stack2[-1]

        def empty(self):
            """
            Returns whether the queue is empty.
            :rtype: bool
            """
            return len(self.stack1) == 0 and len(self.stack2) == 0

    # Your MyQueue object will be instantiated and called as such:
    # obj = MyQueue()
    # obj.push(x)
    # param_2 = obj.pop()
    # param_3 = obj.peek()
    # param_4 = obj.empty()

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 9-1 题] “用两个栈实现队列”做题记录

链接:https://www.javajike.com/article/3308.html

« [剑指 Offer 第 2 版第 68 题] “树中两个节点的最近公共祖先”做题记录
[剑指 Offer 第 2 版第 9-2 题] “用队列实现栈”做题记录»

相关推荐

QR code