精选留言(19)

• 
  卷福

  2018-10-25

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

  

   6
• 
  侯金彪

  2018-10-13

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

  

   5
• 
  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
• 
  driver

  2018-10-19

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

  

   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
• 
  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

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

  

  
• 
  tonyBoy

  2018-12-20

  class MyQueue {
      
     Stack<Integer> Input,Output;
      /** Initialize your data structure here. */
      public MyQueue() {
          
      }
      
      /** Push element x to the back of queue. */
      public void push(int x) {
          if(Output.empty()){ Output.push(x);}
          else{
              while(!Output.empty()){
                  Input.push(Output.peek());
                  Output.pop();
              }
              Input.push(x);
              while(!Input.empty()){
                  Output.push(Input.peek());
                  Input.pop();
              }
          }
      }
      
      /** Removes the element from in front of queue and returns that element. */
      public int pop() {
         int temp=Output.peek();
          Output.pop();
          return temp;
      }
      
      /** Get the front element. */
      public int peek() {
          return Output.peek();
      }
      
      /** Returns whether the queue is empty. */
      public boolean empty() {
          return Output.empty();
      }
  
  }
  麻烦大家帮我看一下哪里有错，为什么提交不上去

  展开

  

  
• 
  Derek

  2018-12-12

  GO语言版实现：
  
  type MyQueue struct {
      inStack []int
      outStack []int
  }
  
  /** Initialize your data structure here. */
  func Constructor() MyQueue {
      return MyQueue{
          inStack: make([]int, 0),
          outStack: make([]int, 0),
      }
  }
  
  /** Push element x to the back of queue. */
  func (this *MyQueue) Push(x int) {
      this.inStack = append(this.inStack, x)
  }
  
  /** Removes the element from in front of queue and returns that element. */
  func (this *MyQueue) Pop() int {
      for _, v := range this.inStack {
          this.outStack = append(this.outStack, v)
      }
      this.inStack = make([]int, 0)
      v := this.outStack[0]
      this.outStack = this.outStack[1 : len(this.outStack)-1]
      return v
  }
  
  /** Get the front element. */
  func (this *MyQueue) Peek() int {
      for _, v := range this.inStack {
          this.outStack = append(this.outStack, v)
      }
      this.inStack = make([]int, 0)
      return this.outStack[0]
  }
  
  /** Returns whether the queue is empty. */
  func (this *MyQueue) Empty() bool {
      return len(this.inStack) != 0 || len(this.outStack) != 0
  }
  
  /**
   * Your MyQueue object will be instantiated and called as such:
   * obj := Constructor();
   * obj.Push(x);
   * param_2 := obj.Pop();
   * param_3 := obj.Peek();
   * param_4 := obj.Empty();
   */

  展开

  作者回复: 👍🏻👍🏻

  

  
• 
  竞帆

  2018-10-13

  好久没学算法，贴出来的代码一下子不好理解，需要补课了

  

  