栈

栈,一种操作受限的线性表, 只允许在一端插入和删除数据

适用于,某个数据集合,只在一端插入和删除数据,且满足后进先出,先进后出的特性时

顺序栈:用数组实现的栈

链式栈:用链表实现的栈

入栈出栈及只涉及栈顶个别数据的操作,时间复杂度都是O(1)
储存大小为n的数组,不能说空间复杂度为O(n),因为n是必须的,无法省略的
空间复杂度,是指原本的数据储存空间外,算法运行还需要的额外储存空间

支持动态扩容的顺序栈

基于数组实现支持动态扩容的栈,只需要底层依赖一个支持动态扩容的数组就行

练习均摊时间复杂度:
假设栈空间不够时入栈需要申请一个原来两倍大小的空间,且只考虑入栈不考虑出栈

则假设栈空间为n,每经过n次入栈操作会产生一次扩容,
则需将栈内所有元素入栈到新地址(不考出栈)
则, 每次扩容会产生n次扩容入栈,每次扩容时间复杂度为O(n)
均摊到每次入栈操作后,相当于除以n,则每次入栈的均摊时间复杂度为O(1)

栈的应用

函数调用栈

表达式求值
两个栈,一个保存数字一个保存运算符;
如果遇到数字,直接压入操作数栈;
如果遇到运算符就与栈顶元素进行比较:
如果比运算符栈栈顶元素优先级高就将当前运算符压入栈;
如果比运算符栈栈顶元素优先级低就先放着当前运算符
从操作数栈取出栈顶2个操作数,
从运算符栈取出栈顶1个运算符,
进行计算,再把计算完的结果插入操作数栈顶,
然后当前运算符继续与运算符栈顶元素进行比较

括号匹配
用栈来保存未匹配的左括号,从左往右扫描字符,
当扫描到左括号时压入栈中
当扫描到右括号时从栈顶取出一个左括号进行比较,
如果匹配,继续扫描剩下的字符,如果不匹配,则说明为非法格式

浏览器的前进后退

/**
 * 基于链表实现的栈。
 *
 * Author: nameczz
 */

class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}

class StackBasedLinkedList {
    constructor() {
        this.top = null
    }
    push(value) {
        const node = new Node(value)
        if (this.top === null) {
            this.top = node
        } else {
            node.next = this.top
            this.top = node
        }
    }
    pop() {
        if (this.top === null) {
            return -1
        }
        const value = this.top.element
        this.top = this.top.next
        return value
    }
    // 为了实现浏览器前进后退
    clear() {
        this.top = null
    }
    display() {
        if (this.top !== null) {
            let temp = this.top
            while (temp !== null) {
                console.log(temp.element)
                temp = temp.next
            }
        }
    }
}
// Test
const newStack = new StackBasedLinkedList()
newStack.push(1)
newStack.push(2)
newStack.push(3)
// 获取元素
let res = 0
console.log('-------获取pop元素------')
while (res !== -1) {
    res = newStack.pop()
    console.log(res)
}

exports.CreatedStack = StackBasedLinkedList