【刷题第 15 天】剑指 Offer 09. 用两个栈实现队列

2022 年 5 月 21 日
本文字数：1007 字
阅读完需：约 3 分钟

一、题目描述：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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]

复制代码

二、思路分析：

这也是计算机数据结构与算法的经典题目，做这个题目之前，我们首先要区分栈和队列分别都是什么？

栈

栈一块连续的数据空间，有一个栈顶一个栈底，只能在栈顶出进行数据的压入和弹出，符合先进后出规则，也就是说先进入栈的元素需要等待上面所有的元素弹出后才能弹出。

在 JavaScript 中我们可以通过数组进行模拟，数组提供了 .length 属性可以获取栈的长度，pop、push 方法分别用来出栈和入栈

队列

队列同样也是连续的数据空间，有一个队头一个队尾，只能在队头压入数据，队尾弹出数据，符合先进先出规则，生活中比较明显的栗子就是排队，先来的排队者先接受服务。

在 JavaScript 中同样使用数组模拟，unshift、shift 方法分别用来入队和出队。

算法思想

题目给我们提供了两个栈，因此我们将一个栈用作输入栈，用于接收 appendTail 的数据；另外一个栈当作输出栈，用于进行 deleteHead 功能。

当执行 deleteHead 方法时，若输出栈是空的，我们需要将输入栈的元素全部压入输出栈中，然后从栈顶依次弹出元素即可。

这样就成功的模拟了队列操作

三、AC 代码：

var CQueue = function() {    // 两个栈分别用于输出和输入    this.stack2In = [];    this.stack2Out = [];};
CQueue.prototype.appendTail = function(value) {    // 接收入栈    this.stack2In.push(value);};
CQueue.prototype.deleteHead = function() {    // 处理出栈    if (!this.stack2Out.length) {        if (!this.stack2In.length) {            // 执行顺序错误            return -1;        }        this.in2out();    }    return this.stack2Out.pop();};
CQueue.prototype.in2out = function() {    while (this.stack2In.length) {        // 将输入栈的数据压入输出栈        this.stack2Out.push(this.stack2In.pop());    }};复制代码

复制代码

四、总结：

这个题目相对简单，就不多做赘述了

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/c8ac8087e83008867fc022591】。文章转载请联系作者。

白日梦

关注

还未添加个人签名 2022.03.10 加入

还未添加个人简介

发布

暂无评论

创作场景

【刷题第 15 天】剑指 Offer 09. 用两个栈实现队列

一、题目描述：

示例 1：

示例 2:

二、思路分析：

栈

队列

算法思想

三、AC 代码：

四、总结：

白日梦

评论