关于栈和队列的一些算法_千叶风行的专栏文章_微信文章

要介绍栈和队列的算法,我们就得先知道:啥是栈和队列啊?

栈和队列的定义

栈 :它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底
队列: 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
OK , 介绍完基本知识 , 来实战一下呗

包含min函数的栈(剑指offer 21题)

题目:定义栈的数据结构 , 请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中, 调用 min , push 及 pop 的时间复杂度都是 O(1)
一看到这个问题 , 一眼看上去 , 最难就是怎么在 O(1)的时间复杂度内实现取最小值的操作呢 ?
我们想到在栈里添加一个成员变量存放最小的元素, 每次压入一个新元素进栈的时候, 如果该元素比当前最小的元素还小 , 则更新最下元素。当我们想到这样的思路的时候,仔细想想就会发现 , 如果当前最小的元素被弹出栈了 , 这样我怎么知道下一个最小的元素是什么呢?
分析到这里我们发现仅仅添加一个成员变量存放最小是不够的, 也就是说当最小元素被弹出栈的时候 , 我们希望能够得到次小元素。因此在压入这个最小元素之前 , 我们要把次小元素保存起来。
OK , 我们这里引入辅助栈, 这里我们为了好理解
举个栗子 两个栈
stack = []
help = []
从栈中入栈一个元素 , stack.push(1) => [1]
因为只有一个元素 , 最小值就是那个元素 , 所以
help.push(1) => [1] , 再入一个元素 , stack.push(-1) => [1,-1] , 这时我们发现 , 我刚刚入的数 -1 , 小于 help 的栈顶元素 , 我们也入 help.push(-1) => [1- ,-1],总结起来就是这样的

stack进行push , 如果发现要存的数字小于 help的栈顶元素 , 就存入help , 否则只存入 stack
这题虽然不难,但还挺不好描述的(累死我了)。
OK, show me code

js版的
class MinStack {
 constructor () {
     this.stack = [] ;
     // 辅助栈
     this.help = [] ;
 }
 //入栈
 push (element) {
     // 如果辅助栈为空 或者 加入元素小于辅助栈顶元素 , 则辅助栈进行入栈操作
     if(!this.help.length || element <= this.help[this.help.length -1]) {
         this.help.push(element)
     }
     this.stack.push(element)
 }
 // 出栈
 pop () {
     if(this.stack.pop() === this.help[this.help.length - 1]) {
         this.help.pop()
     }
 }
 // 返回最小值
 getMin() {
     //返回辅助栈顶元素 
    return this.help[this.help.length - 1]
 }
}
复制代码

再来看看python版的

python版的
class MinStack(object):
def __init__(self , *args):
    '''
    initialize your data structure here
    '''
    self.stack = [] # 存放所有元素
    self.minStack = [] #存放每一次压入数据时 , 栈中的最小值
def push(self ,x):
    '''
    :type x :int 
    :rtype : void
    '''
    self.stack.append(x)
    if not self.minStack or self.minStack[-1] >= x:
        self.minStack.append(x)
def pop(self):
    '''
    rtype: void
    '''
    if self.minStack[-1] == self.stack[-1]:
        del self.minStack[-1]
    self.stack.pop()
def top(self):
    '''
    :rtype:int
    '''
    return self.stack[-1]
def getMin(self):
    '''
    :rtype: int
    '''
    return self.minStack[-1]
复制代码

用两个栈实现队列

题目:用两个栈实现一个队列。队列的声明如下:请实现它的两个函数
appendTail 在队列尾部插入节点
deleteHead 在队头删除节点