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

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(); */

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

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

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

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

老师，我刚刚又优化了下速度，因为刚刚在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)

public class MyQueue { Stack<int> _inputStack; Stack<int> _outputStack; /** Initialize your data structure here. */ public MyQueue() { _inputStack = new Stack<int>(); _outputStack = new Stack<int>(); } /** Push element x to the back of queue. */ public void Push(int x) { _inputStack.Push(x); } /** Removes the element from in front of queue and returns that element. */ public int Pop() { MoveInputToOutput(); return _outputStack.Pop(); } /** Get the front element. */ public int Peek() { MoveInputToOutput(); return _outputStack.Peek(); } /** Returns whether the queue is empty. */ public bool Empty() { return _inputStack.Count == 0 && _outputStack.Count == 0; } private void MoveInputToOutput() { if (_outputStack.Count == 0) { while (_inputStack.Count != 0) { _outputStack.Push(_inputStack.Pop()); } } } }

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

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