极客时间-轻松学习，高效学习-极客邦

2018-10-25

接着shawn的优化一下。前面的步骤都一样，最后的input output可以不用互换，只需要在每次push/pull/peek操作前判断一下哪个队列不为空，就从不为空的队列开始操作到空的队列即可，省去了一次互换的操作，减少了一倍的时间复杂度。



 6

侯金彪

2018-10-13

老师能否指点下如何用队列实现栈呢？

 1

 5

driver

2018-10-19

我这提供一个队列实现栈的思路:入栈在非空队列中加入(如果都是空队列任选一个队列加入)，出栈和查看栈顶元素，把非空队列元素输入到空队列中，最后一个输入元素就是要出栈或者查看的元素。



 3

ada_shen

2019-07-16

老师，我刚刚又优化了下速度，因为刚刚在leetcode试了之前的方法才击败了50%，现在这个击败96%
# -*- coding: UTF-8 -*

class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.input_stack = []
        self.output_stack = []


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


    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if self.empty():
            return None
        else:
            if len(self.output_stack):
                return self.output_stack.pop()
            else:
                # for i in xrange(0, len(self.input_stack)):
                # self.output_stack.append(self.input_stack.pop())
                length = len(self.input_stack)
                self.output_stack = map(lambda x: self.input_stack.pop(), range(0, length))
                return self.output_stack.pop()


    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if self.empty():
            return None
        else:
            if len(self.output_stack):
                return self.output_stack[-1]
            else:
                # for i in xrange(0, len(self.input_stack)):
                # self.output_stack.append(self.input_stack.pop())
                length = len(self.input_stack)
                self.output_stack = map(lambda x: self.input_stack.pop(), range(0, length))
                return self.output_stack[-1]


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

展开



 2

他在她城断了弦

2018-11-12

关于用队列实现栈，大家可以看我写的博客，有两种比较好想的思路：https://blog.csdn.net/zpznba/article/details/83987480



 2

shawn

2018-10-23

队列变栈，应该是两个队列，input和output，入input，出的时候，出input全队放入output中，pop把最后出队的值返回不放回output，peek放回output，然后input output互换，后续操作都如此吧



 2

奔腾

2019-05-26

单队列双队列，都可以用来实现栈哟



 1

bywuu

2019-04-29

@tonyBoy:你那个Stack的两个变量根本没有初始化，当然会出错不通过了。
Stack<Integer> stack1 = new Stack<Integer>();
起码要这样才行啊。



 1

一弯年轮

2019-01-18

Python版本语言版实现：
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.input = []
        self.output = []

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

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if self.empty():
            return None
        if len(self.output) == 0:
            # self.output为空, self.input不为空,把input的值掉个顺序倒腾到output中去
            long = len(self.input)
            while long > 0:
                self.output.append(self.input.pop())
                long -= 1
            return self.output.pop()
        else:
            # self.output不为空, self.input为空
            return self.output.pop()

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if self.empty():
            return None
        if len(self.output) == 0:
            # self.output为空, self.input不为空,把input的值掉个顺序倒腾到output中去
            long = len(self.input)
            while long > 0:
                self.output.append(self.input.pop())
                long -= 1
            return self.output[-1]
        else:
            # self.output不为空, self.input为空
            return self.output[-1]

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        if len(self.output) == 0 and len(self.input) == 0:
            return True
        return False

展开



 1

何柄融

2020-02-09

这里用了输入输出栈来操作，我以前是输出完后再放回输入那里。。。多比一举了，尴尬。。





pikachu122

2020-01-16

LeetCode232 Java代码 0 ms 34.2 MB 打败100%Java提交

class MyQueue {
    Stack<Integer> in = new Stack<>();
    Stack<Integer> out = new Stack<>();
    /** Initialize your data structure here. */
    public MyQueue() {

    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        in.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (out.isEmpty()){
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
        return out.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

展开





Matrix

2020-01-01

实现了一个python版本的，但是提交test case 7会有错误。
求教大家问题在哪

class MyQueue:

    input = []
    output = []

    def __init__(self):
        pass

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        if self.output:
            return self.output.pop()

        self.__copy_input_to_output()

        return self.output.pop()

    def peek(self) -> int:
        if self.output:
            return self.output[-1]

        self.__copy_input_to_output()

        return self.output[-1]

    def empty(self) -> bool:
        return not (self.input or self.output)

    def __copy_input_to_output(self):
        while self.input:
            self.output.append(self.input.pop())

展开





翟玮

2019-12-26

class MyQueue {

    /** Initialize your data structure here. */
    public MyQueue() {

    }
    Stack<Integer> pu = new Stack<>();
    Stack<Integer> po = new Stack<>();
    /** Push element x to the back of queue. */
    public void push(int x) {
        if(!po.empty()){
            int poSize = po.size();
            for(int i = 0; i < poSize; i++){
                pu.push(po.pop());
            }
            pu.add(x);
            int puSize = pu.size();
            for(int i = 0; i < puSize; i++){
                po.push(pu.pop());
            }
        }else{
            pu.add(x);
            po.push(pu.pop());
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return po.pop();
    }

    /** Get the front element. */
    public int peek() {
        return po.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return po.size() == 0;
    }
}
用for循环实现，循环里的stack.size()拿出来，不然会遍历不完。。搞了半天，还是stack用的不熟。。。

展开





Uncle.Wang

2019-12-09

建议stack用push和pop，queue用enqueue和dequeue。





lzh

2019-12-01

队列实现栈：每插一个新数据的时候，把该数据前面的数据都出队，再入队....皮的一





ada_shen

2019-07-16

老师你好，python版本重新修改一下peek函数，当out_stack里有元素而in_stack里没有元素的情况，应返回out_stack第一个元素
class QueueByStack(object):
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def empty(self):
        """
        判断队列为空
        :return: bool
        """
        return bool(len(self.input_stack) == 0 and len(self.output_stack) == 0)

    def push(self, input):
        """
        元素进入队列
        :param input:list
        :return:
        """
        if isinstance(input, list) and len(input):
            for s in input:
                self.input_stack.append(s)

    def pop(self):
        """
        元素出队列
        :return: 队列出来的第一个元素
        """
        if self.empty():
            return None
        else:
            if len(self.output_stack):
                return self.output_stack.pop()
            else:
                for i in xrange(0, len(self.input_stack)):
                    self.output_stack.append(self.input_stack.pop())
                return self.output_stack.pop()

    def peek(self):
        """
        查看队列的最后一个元素
        :return: 队列的最后一个元素
        """
        if self.empty():
            return None
        else:
            if len(self.output_stack):
                return self.input_stack[-1] if len(self.input_stack) else self.output_stack[0]
            else:
                for i in xrange(0, len(self.input_stack)):
                    self.output_stack.append(self.input_stack.pop())
                return self.output_stack[0]

展开





ada_shen

2019-07-16

老师我试了下python版本，欢迎指正
class QueueByStack(object):
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def push(self, input):
        """
        元素进入队列
        :param input:list
        :return:
        """
        if isinstance(input, list) and len(input):
            for s in input:
                self.input_stack.append(s)

    def pop(self):
        """
        元素出队列
        :return: 队列出来的第一个元素
        """
        if len(self.input_stack):
            if len(self.output_stack):
                return self.output_stack.pop()
            else:
                for i in xrange(0, len(self.input_stack)):
                    self.output_stack.append(self.input_stack.pop())
                return self.output_stack.pop()
        else:
            return None

    def peek(self):
        """
        查看队列的最后一个元素
        :return: 队列的最后一个元素
        """
        if len(self.input_stack):
            if len(self.output_stack):
                return self.input_stack[-1]
            else:
                for i in xrange(0, len(self.input_stack)):
                    self.output_stack.append(self.input_stack.pop())
                return self.output_stack[0]
        else:
            return None

展开





一直等月落

2019-04-01

Java语言实现版，在push时候做翻转
class MyStack {

Queue<Integer> queue=new LinkedList<Integer>();

        /** Push element x onto stack. */
        public void push(int x) {
            Queue<Integer> temp=new LinkedList<Integer>();
            while (!queue.isEmpty()){
                temp.add(queue.poll());
            }
            queue.add(x);
            while (!temp.isEmpty()){
                queue.add(temp.poll());
            }
        }

        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
            return queue.poll();
        }

        /** Get the top element. */
        public int top() {
            return queue.peek();
        }

        /** Returns whether the stack is empty. */
        public boolean empty() {
            return queue.isEmpty();
        }
}

展开

作者回复: 赞！

 1



小小的太阳

2019-01-28

这种对于(abc)就没法检测了吧





Geek_a80be3

2019-01-19

老师，请问能讲下链表的递归吗



