本题其实我解出来了,但是不是最优解。
本题,要跟面试官确认,是push操作更多,还是pop/top操作更多
- 如果是
push操作更多,我之前的方法没有任何问题,用两个Queue<Integer> - 如果是
pop/top操作更多,那下面这个方法就更好,也更简洁- 只用一个
Queue<Integer> - 每次插入的时候,都将
Queue<Integer>rotate,这样就变成了一个Stack<Integer> - 时间复杂度
push:top/pop:
- 只用一个
代码如下:
class MyStack {private Queue<Integer> queue;/** Initialize your data structure here. */public MyStack() {queue = new LinkedList<>();}/** Push element x onto stack. */public void push(int x) {queue.offer(x);for (int i = 1; i < queue.size(); ++i) {queue.offer(queue.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();}}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/
