本文共 1436 字，大约阅读时间需要 4 分钟。

前言

在上一遍中，我们已经学会了如何用队列实现栈，本文我们稍微转变一下思路，看一下第二种优化解法。

解题思路

当然还是需要两个队列来实现，与第一种解法不同的是，这次我们是在每次要添加元素时来交换队列中的元素，还是假设现在有两个队列分别为：A和B，当每次要弹出元素时都从A队列中弹出，而当要添加元素时，则先把当前要添加的元素添加到队列B中，再把A队列中的元素依次弹出并添加到B队列中，再交换A、B队列的角色。

图解分析

1、假设现在要添加一个元素1，先把1添加到队列B中。

2、1被添加到队列B中后，由于队列A中没有元素，所以接着队列A、B互相交换角色，原来的队列A变为队列B，原来的队列B变为队列A。

4、再把队列A的元素依次弹出并添加到队列B中。

5、队列A、B互相交换角色。

6、需要取出元素时，直接从队列A中取即可。

代码实现

import java.util.LinkedList;import java.util.Queue;class MyStack_02 {
       Queue
   
     queue_one = new LinkedList<>();    Queue
    
      queue_two = new LinkedList<>();    /**     * Initialize your data structure here.     */    public MyStack_02() {
       }    /**     * Push element x onto stack.     */    public void push(int x) {
           queue_two.offer(x);        while (!queue_one.isEmpty()) {
               queue_two.offer(queue_one.poll());        }        Queue
     
       temp = queue_one;        queue_one = queue_two;        queue_two = temp;    }    /**     * Removes the element on top of the stack and returns that element.     */    public int pop() {
           return queue_one.poll();    }    /**     * Get the top element.     */    public int top() {
           return queue_one.peek();    }    /**     * Returns whether the stack is empty.     */    public boolean empty() {
           return queue_one.isEmpty();    }}
     
    
   

可以看出这次的方式在获取top时，直接通过peek就得到了结果，相比上一遍文章每次都需要遍历到最后一个元素，在时间复杂度上直接从O(n)降到了O(1)。

转载地址：http://bqlrb.baihongyu.com/