日拱算法：用两个栈实现队列&包含min函数的栈

本篇带来【剑指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.

解题思路：

审题：

1. push(x) —— 将元素 x 推入栈中。

2. pop() —— 删除栈顶的元素。

3. top() —— 获取栈顶元素。

4. getMin() —— 检索栈中的最小元素。

5. 像常规apipush和pop这些操作，对栈进行了操作，直接输出null；

6. 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，以上便是本篇分享~

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