两个栈实现一个队列，两个队列实现一个栈

栈于队列是两种最常见的数据结构，在我们开发的过程中随处可见，每个开发者都应该有相对清晰的概念，这样才能理解并熟练掌握开发技巧。本篇文章讲述下如何用栈实现队列，以及如何用队列实现栈。

1.两个栈实现一个队列。

• 入队时，将元素压入stack1。
• 出队时，判断stack1是否为空，若不为空，则将stack1的元素逐个倒入stack2，然后把stack2的栈顶元素弹出并出队，最后判断
  stack2是否为空，若不为空，则将stack2的元素逐个倒回stack1。

ps：该文章讲述的只是一种方案，还有其他方案，有兴趣的可以深入探究。

stackToQueue.png

Java实现的代码：

public class StackToQueue<T> {
    Stack<T> stackOne = new Stack<T>();
    Stack<T> stackTwo = new Stack<T>();

    private void push(T data) {
        stackOne.push(data);
    }

    private T pop() {
        while (!stackOne.isEmpty()) {
            stackTwo.push(stackOne.pop());
        }
        T first = stackTwo.pop();
        while (!stackTwo.isEmpty()) {
            stackOne.push(stackTwo.pop());
        }
        return first;

    }

}

2.两个队列实现一个栈。

基本思想如下图所示：

QueueToStack.png

入栈操作，我们固定把元素压入queue1

出栈操作，如果队列1不为空，就把队列1中q1.size()-1个元素poll出来，添加到队列2中，再把队列中那个最后的元素poll出来

这两个队列中始终有一个是空的。另一个非空。push添加元素到非空队列中，pop把非空队列中前面的元素都转移到另一个队列中，只剩最后一个元素，再把最后一个元素pop出来。这样这一个队列是空的，另一个队列又非空了。

Java实现的代码：

public class QueueToStack<T> {
    private ArrayDeque<T> queueOne = new ArrayDeque<>();
    private ArrayDeque<T> queueTwo = new ArrayDeque<>();

    private void push(T t) {
        queueOne.offer(t);
    }

    private T pop() {
        if (!queueOne.isEmpty() || !queueTwo.isEmpty()) {
            if (!queueOne.isEmpty()) {
                while (queueOne.size() > 1) {
                    queueTwo.offer(queueOne.poll());
                }
                return queueOne.poll();
            } else if (!queueTwo.isEmpty()) {
                while (queueTwo.size() > 1) {
                    queueOne.offer(queueTwo.poll());
                }
                return queueTwo.poll();
            }

        }
        return null;
    }

    private T top() {
        T top = null;
        if (!isEmpty()) {
            if (!queueOne.isEmpty()) {
                while (queueOne.size() > 1) {
                    queueTwo.offer(queueOne.poll());
                }
                top = queueOne.peek();
                queueTwo.offer(queueOne.poll());
            } else if (!queueTwo.isEmpty()) {
                while (queueTwo.size() > 1) {
                    queueOne.offer(queueTwo.poll());
                }
                top = queueTwo.peek();
                queueOne.offer(queueTwo.poll());
            }
            return top;

        }
        return null;
    }

    private boolean isEmpty() {
        return queueOne.isEmpty() && queueTwo.isEmpty();
    }

}