读完本文，你能够去力扣拿下如下题目：

232.用栈实现队列

225.用队列实现栈

-----------

队列是一种先进先出的数据结构，栈是一种先进后出的数据结构，形象一点就是这样：

这两种数据结构底层其实都是数组或者链表实现的，只是 API 限定了它们的个性，那么明天就来看看如何应用「栈」的个性来实现一个「队列」，如何用「队列」实现一个「栈」。

一、用栈实现队列

首先，队列的 API 如下：

class MyQueue {        /** 增加元素到队尾 */    public void push(int x);        /** 删除队头的元素并返回 */    public int pop();        /** 返回队头元素 */    public int peek();        /** 判断队列是否为空 */    public boolean empty();}

咱们应用两个栈 s1, s2 就能实现一个队列的性能（这样搁置栈可能更容易了解）：

class MyQueue {    private Stack<Integer> s1, s2;        public MyQueue() {        s1 = new Stack<>();        s2 = new Stack<>();    }    // ...}

当调用 push 让元素入队时，只有把元素压入 s1 即可，比如说 push 进 3 个元素别离是 1,2,3，那么底层构造就是这样：

/** 增加元素到队尾 */public void push(int x) {    s1.push(x);}

那么如果这时候应用 peek 查看队头的元素怎么办呢？按情理队头元素应该是 1，然而在 s1 中 1 被压在栈底，当初就要轮到 s2 起到一个直达的作用了：当 s2 为空时，能够把 s1 的所有元素取出再增加进 s2，这时候 s2 中元素就是先进先出程序了。

PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全副公布在 labuladong的算法小抄，继续更新。倡议珍藏，依照我的文章程序刷题，把握各种算法套路后投再入题海就蛟龙得水了。

/** 返回队头元素 */public int peek() {    if (s2.isEmpty())        // 把 s1 元素压入 s2        while (!s1.isEmpty())            s2.push(s1.pop());    return s2.peek();}

同理，对于 pop 操作，只有操作 s2 就能够了。

/** 删除队头的元素并返回 */public int pop() {    // 先调用 peek 保障 s2 非空    peek();    return s2.pop();}

最初，如何判断队列是否为空呢？如果两个栈都为空的话，就阐明队列为空：

/** 判断队列是否为空 */public boolean empty() {    return s1.isEmpty() && s2.isEmpty();}

至此，就用栈构造实现了一个队列，核心思想是利用两个栈互相配合。

值得一提的是，这几个操作的工夫复杂度是多少呢？有点意思的是 peek 操作，调用它时可能触发 while 循环，这样的话工夫复杂度是 O(N)，然而大部分状况下 while 循环不会被触发，工夫复杂度是 O(1)。因为 pop 操作调用了 peek，它的工夫复杂度和 peek 雷同。

像这种状况，能够说它们的最坏工夫复杂度是 O(N)，因为蕴含 while 循环，可能须要从 s1 往 s2 搬移元素。

然而它们的均摊工夫复杂度是 O(1)，这个要这么了解：对于一个元素，最多只可能被搬运一次，也就是说 peek 操作均匀到每个元素的工夫复杂度是 O(1)。

二、用队列实现栈

如果说双栈实现队列比拟奇妙，那么用队列实现栈就比较简单粗犷了，只须要一个队列作为底层数据结构。首先看下栈的 API：

class MyStack {        /** 增加元素到栈顶 */    public void push(int x);        /** 删除栈顶的元素并返回 */    public int pop();        /** 返回栈顶元素 */    public int top();        /** 判断栈是否为空 */    public boolean empty();}

先说 push API，间接将元素退出队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要 top 查看栈顶元素的话能够间接返回：

class MyStack {    Queue<Integer> q = new LinkedList<>();    int top_elem = 0;    /** 增加元素到栈顶 */    public void push(int x) {        // x 是队列的队尾，是栈的栈顶        q.offer(x);        top_elem = x;    }        /** 返回栈顶元素 */    public int top() {        return top_elem;    }}

咱们的底层数据结构是先进先出的队列，每次 pop 只能从队头取元素；然而栈是后进先出，也就是说 pop API 要从队尾取元素。

解决办法简略粗犷，把队列后面的都取出来再退出队尾，让之前的队尾元素排到队头，这样就能够取出了：

/** 删除栈顶的元素并返回 */public int pop() {    int size = q.size();    while (size > 1) {        q.offer(q.poll());        size--;    }    // 之前的队尾元素曾经到了队头    return q.poll();}

这样实现还有一点小问题就是，原来的队尾元素被提到队头并删除了，然而 top_elem 变量没有更新，咱们还须要一点小批改：

/** 删除栈顶的元素并返回 */public int pop() {    int size = q.size();    // 留下队尾 2 个元素    while (size > 2) {        q.offer(q.poll());        size--;    }    // 记录新的队尾元素    top_elem = q.peek();    q.offer(q.poll());    // 删除之前的队尾元素    return q.poll();}

最初，API empty 就很容易实现了，只有看底层的队列是否为空即可：

/** 判断栈是否为空 */public boolean empty() {    return q.isEmpty();}

很显著，用队列实现栈的话，pop 操作工夫复杂度是 O(N)，其余操作都是 O(1)。

集体认为，用队列实现栈是没啥亮点的问题，然而用双栈实现队列是值得学习的。

从栈 s1 搬运元素到 s2 之后，元素在 s2 中就变成了队列的先进先出程序，这个个性有点相似「负负得正」，的确不太容易想到。

心愿本文对你有帮忙。