使用队列堆栈

push:将元素插入队列的后面。

A版:

排队1

流行音乐:

出列并返回队列1的最后一项,然后切换队列1和队列2的名称

B版:

排队2 将队列2中队列1的所有项排队,然后切换队列1和队列2的名称

流行音乐:

从队列1中取出

使用一个队列实现堆栈的概念需要O(2n)或(与机器无关)O(n)空间复杂性。但是,当您为一个大的数组工作时,可能无法使用双倍大小的数组,如果您只尝试使用一个队列,那么时间复杂度也是O(n^2)或精确地是O(n*(n+1)/2)。

使用队列实现堆栈的以下操作。

推(x)--将元素x推到堆栈上。

pop()——删除堆栈顶部的元素。

top()--获取顶部元素。

empty()——返回堆栈是否为空。

class MyStack {

  Queue<Integer> q;
  /** Initialize your data structure here. */

  public MyStack() {
    q = new LinkedList<Integer>();
  }

  /** Push element x onto stack. */
  public void push(int x) {
    q.offer(x);

    for(int i = 1 ; i < q.size() ; i++) {
        q.offer(q.poll());
    }
  }

  /** Removes the element on top of the stack and returns that element. */
  public int pop() {
     return q.isEmpty() ? -1 : q.poll();
  }

  /** Get the top element. */
  public int top() {
    return q.isEmpty() ? -1 : q.peek();
  }

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