本篇带来【剑指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，以上便是本篇分享~
