用两个栈实现队列

2022 年 8 月 25 日
广东
本文字数：1329 字
阅读完需：约 4 分钟

本篇带来【剑指 offer】的两道初级算法题：冲~~

用两个栈实现队列

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

var CQueue = function() {    this.stackA = [];    this.stackB = [];};
/** * @param {number} value * @return {void} */
CQueue.prototype.appendTail = function(value) {    this.stackA.push(value);};
/** * @return {number} */
CQueue.prototype.deleteHead = function() {    if (this.stackB.length) {        return this.stackB.pop();    } else {        while (this.stackA.length) {            this.stackB.push(this.stackA.pop());        }        if (!this.stackB.length) {            return -1;        } else {            return this.stackB.pop();        }    }};

复制代码

包含 min 函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:
MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min();   --> 返回 -3.minStack.pop();minStack.top();      --> 返回 0.minStack.min();   --> 返回 -2.

复制代码

解题思路：

审题：

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
像常规 apipush 和 pop 这些操作，对栈进行了操作，直接输出 null；
top 和 min 需要我们自己按照题目要求来排序栈，并输出元素

JavaScript 实现 如下：

/** * initialize your data structure here. */var MinStack = function() {    this.stack = []};
/**  * @param {number} x * @return {void} */MinStack.prototype.push = function(x) {    this.stack.push(x)};
/** * @return {void} */MinStack.prototype.pop = function() {  return  this.stack.pop()};
/** * @return {number} */MinStack.prototype.top = function() {  return  this.stack[this.stack.length - 1]};
/** * @return {number} */MinStack.prototype.min = function() {    let array = JSON.parse(JSON.stringify(this.stack))     array =  array.sort((a,b)=>a - b)    // console.log("array:", array,',stack:', this.stack)
    return array[0]};

复制代码

OK，以上便是本篇分享~

我是掘金安东尼，输出暴露输入，技术洞见生活，再会~~

发布于: 刚刚阅读数: 3

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

掘金安东尼

关注

安东尼陪你度过漫长编程岁月~ 2022.07.14 加入

社会我瓜哥，人狠话不多😎 微信 anthony1453，加我交个朋友😎 正联合【机械工业出版社】出版《程序员成长手册》，敬请期待😎 真正的大师，永远怀着一颗学徒的心（易）😎

发布

暂无评论

创作场景

用两个栈实现队列

掘金安东尼

评论