乐趣区

关于java:算法图解如何用两个栈实现一个队列

jiezi

本文已收录至 https://github.com/vipstone/algorithm《算法图解》系列。

队列和栈是计算机中两个十分重要的数据结构，通过后面的学习（《队列》、《栈》）咱们晓得了它们各自的特点，队列是先进先出（FIFO）的，而栈是先进后出（FILO）的，那如何用栈来实现队列呢？这可是一道经典的面试题，所以本文咱们就来实现一下。

在正式开始之前，咱们先来回顾一下栈和队列的罕用办法。

栈（Stack）的罕用办法蕴含以下这些：

  • push()：入栈办法，向栈顶增加元素；
  • pop()：出栈办法，将栈顶的元素移除并返回元素；
  • peek()：查问栈顶元素，并不会移除元素。

队列（Queue）的罕用办法蕴含以下这些：

  • offer()：入队办法，向队尾增加元素；
  • poll()：出队办法，从队头移除并返回元素；
  • peek()：查问队头元素，并不会移除元素。


有了这些前置常识，接下来咱们来看明天的题目。

题目形容

用两个栈实现一个队列。队列的申明如下，请实现它的两个函数 appendTail 和 deleteHead，别离实现在队列尾部插入整数和在队列头部删除整数的性能，若队列中没有元素，deleteHead 操作返回 -1。

示例 1：

输出：

[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]

[[],[3],[],[]]

输入：[null,null,3,-1]

示例 2：

输出：

[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]

[[],[],[5],[2],[],[]]

输入：[null,-1,null,null,5,2]

提醒：

1 <= values <= 10000

最多会对 appendTail、deleteHead 进行 10000 次调用

leetcode：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

解题思路

这道题目的意思其实很好了解，就是要将先进后出的栈改为先进先出的队列，其实问题中也给出了一些提醒，“用两个栈来实现一个队列”。 这道题实现的核心思想就是「负负得正」，咱们先用一个栈来存入元素（这时最先进入的元素在栈底），而后再将第一个栈中的元素挪动到新栈中，此时最先进入的元素就在栈顶了，而后在用第二个栈出栈时，整个执行的程序就变成了先进先出。

接下来，咱们用图解的形式来实现一下整个流程。

步骤一

先将元素入栈到第一个栈中，如下图所示：

步骤二

将第一个栈中的元素都挪动到第二个栈中，如下图所示：

步骤三

所有元素从第二个栈中出栈，如下图所示：

小结

从上述图片能够看出，元素增加程序是 1、2、3，最终通过两个栈之后的出栈程序也是 1、2、3，这样咱们就通过两个栈实现了队列（先进先出）。

实现代码

接下来咱们就用代码来实现一下以上思路：

class CQueue {Stack<Integer> inputStack; // 入栈的容器（增加时操作)
    Stack<Integer> outputStack; // 出栈和查问的栈容器

    public CQueue() {inputStack = new Stack();
        outputStack = new Stack();}

    // 增加操作
    public void appendTail(int value) {inputStack.push(value);
    }

    // 删除操作
    public int deleteHead() {if (!outputStack.isEmpty()) {
            // 出栈容器不为空
            return outputStack.pop();} else if (!inputStack.isEmpty()) {
            // 入栈 stack 全副转移到出栈 stack
            while (!inputStack.isEmpty()) {outputStack.push(inputStack.pop());
            }
        }
        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}

咱们在 LeetCode 中提交以上测试代码，执行后果如下：

注意事项

在整个实现过程中有两个小细节须要特地留神一下：

  1. 第 1 个栈只负责入栈（暂存数据），第 2 个栈只负责出栈（最终的队列执行程序）；
  2. 每次栈 2 出栈时都要把所有的元素都出完之后，能力从栈 1 中追加（增加）新数据，当栈 2 的数据没有全副出栈实现时，不能将栈 1 的元素入栈到栈 2，这样会导致元素的执行程序凌乱。

总结

本文咱们通过两个先进后出的栈，通过“负负得正”的思路实现了队列先进先出的个性，但须要特地留神的是当第 2 个栈也就是出栈容器，在非空（栈）时不能将第 1 个栈中的元素增加到第 2 个栈中，免得造成程序执行程序凌乱。

文末福利：搜寻公众号「Java 中文社群」发送“面试”，支付最新的面试材料。

退出移动版