数据结构与算法的重温之旅（六）——栈

上一篇文章讲到了链表，接下来讲的是数据结构里面最经典的一个结构：栈。

栈从定义上来讲，是一个操作受限的线性表。栈只支持从一端存入数据和删除数据，即先进后出。先进后出是典型的栈的结构特点，很多实例都有应用到栈的特点来实现，比如浏览器的前进后退功能。栈对比前面所讲的数组和链表，功能上受限了很多，只支持在一段存入数据和删除数据，但是也比他们容易维护，由于只是在一端存入和删除数据，所以数据不会容易出错。

栈从实现上可以用数组和链表来实现，数组实现叫顺序栈，链表实现叫链式栈。下面的这组代码实现了这两种方式的栈声明：

class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}
class linkedList {
    constructor() {
        this.head = null
    }
    pushData (item) {
        let curr = this.head
        let newNode = new Node(item)
        if (curr == null) {
            this.head = newNode
            curr = this.head
        }
        else {
            while (curr) {
                if (curr.next) {
                    curr = curr.next
                }
                else {
                    curr.next = newNode
                    break
                }
            }
        }
    }
    popData () {
        let curr = this.head
        if (curr == null) {
            return false
        }
        else if (this.head.next == null) {
            let temp = this.head
            this.head = null
            return temp
        }
        else {
            while (curr) {
                if (curr.next && curr.next.next) {
                    curr = curr.next
                }
                else if (curr.next && curr.next.next == null) {
                    let temp = curr.next
                    curr.next = null
                    return temp
                }
            }
        }
    }
}复制代码

class ArrayLisk {
    constructor () {
        this.stack = new Array()
    }
    pushData (item) {
        this.stack.push(item)
    }
    popData () {
        return this.stack.pop()
    }
}复制代码

可以看出用数组来实现栈的话比链表实现要简单很多，这里是用了JavaScript里的数组的一些语法糖，所以看起来比较简单实现。栈的时间复杂度和空间复杂度都是O(1)。因为在空间上只需用几个临时变量来存储值，在时间上只涉及插入和删除操作，不涉及遍历，所以时间和空间上的复杂度都是O(1)。

正常来说，栈是有容量的，当栈的容量满的时候，需要给栈扩容。普通的做法就是给栈一个两倍容量的容器，将原来的值都存入到新的栈中。整体的时间复杂度是O(1)。

栈作为一个比较基础的数据结构，应用场景还是蛮多的。其中，比较经典的一个应用场景就是函数调用栈。我们知道，操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。为了让你更好地理解，我们一块来看下这段代码的执行过程。

function first () {
    var b = 2
}
function second () {
    first()
    var a = 1
}
second()复制代码

在这里，second函数调用了first函数，所以在栈里先出的是var b = 2这条语句，然后到var a = 1这条语句。

除了这个应用外，栈在表达式求值中也有实例可以应用。如1+2*3/4这条算术表达式中，先进行的肯定是2*3，然后是除以4，最后才加1。那如果用代码的话他的设计思路是如何的呢？实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。下面用代码来实现一下：

class ArrayLisk {
    constructor () {
        this.stack = new Array()
    }
    pushData (item) {
        this.stack.push(item)
    }
    popData () {
        return this.stack.pop()
    }
}
function numberOperation(operation, num1, num2) {
    num1 = Number(num1)
    num2 = Number(num2)
    if (operation === '*') return num1 * num2
    else if (operation === '/') return num1 / num2
    else if (operation === '+') return num1 + num2
    else if (operation === '-') return num1 - num2
}
let stringPattern = '1+5*4/2-2'
let numberStack = new ArrayLisk()
let operationStack = new ArrayLisk()
for (let a = 0; a < stringPattern.length; a++) {
    let operaNum1 = 0
    let operaNum2 = 0
    if (!isNaN(+stringPattern[a])) {
        numberStack.pushData(stringPattern[a])
    }
    else {
        if (stringPattern[a] === '*' || stringPattern[a] === '/') {
            operaNum1 = numberStack.popData()
            operaNum2 = stringPattern[a+1]
            numberStack.pushData(numberOperation(stringPattern[a], operaNum1, operaNum2))
            ++a
        }
        else {
            let temp = operationStack.popData()
            if (temp) {
                operaNum1 = numberStack.popData()
                operaNum2 = stringPattern[a+1]
                let detail = numberOperation(stringPattern[a], operaNum1, operaNum2)
                numberStack.pushData(detail)
                operationStack.pushData(temp)
                ++a
            }
            else {
                operationStack.pushData(stringPattern[a])
            }
        }
    }
    if (a === stringPattern.length - 1) {
        operaNum1 = numberStack.popData()
        operaNum2 = numberStack.popData()
        console.log(numberOperation(operationStack.popData(), operaNum2, operaNum1))
    }
}复制代码

目前这个只能进行个位数的加减乘除，超过个位数由于判断的问题会出现判断不准的情况。其实如果想要全数字可以的话则要对当前字符串下标后面的值进行判断，看是否是数字，如果是的话则继续拼接字符串，直到后面不是数字为止。

除了这个应用外，在做acm或者leetCode的过程中，也有一道十分经典的题，就是括号匹配问题。判断字符串是否是合法的括号，如{[()]}这个字符串肯定是合法的，而}[()]{肯定是非法的。那如何解决这种问题了，我们可以通过栈来解决。先按从左往右的顺序把字符压入栈中，如果刚好栈顶的字符能够跟它下一个字符相匹配则出栈，然后当前栈顶的继续匹配看是否连续，当当前栈顶与当前遍历到的字符串不匹配的时候则说明当前字符串的括号不完全匹配，反之则完全匹配。代码如下：

class ArrayLisk {
    constructor () {
        this.stack = new Array()
    }
    pushData (item) {
        this.stack.push(item)
    }
    popData () {
        return this.stack.pop()
    }
}
let pattern = '{[()]}{{{}}}[[[]]]((()))'
let myStack = new ArrayLisk()
let tempLeft = ['{', '[', '(']
let state = true
for (let a = 0; a < pattern.length; a++) {
    if (tempLeft.includes(pattern[a])) {
        myStack.pushData(pattern[a])
    }
    else {
        let temp = myStack.popData()
        if (temp === '{' && pattern[a] === '}') {}
        else if (temp === '[' && pattern[a] === ']') {}
        else if (temp === '(' && pattern[a] === ')') {}
        else {
            state = false
            break
        }
    }
}
if (myStack.stack.length) {
    state = false
}复制代码

最后一种与栈相关的应用就是浏览器页面的后退和前进功能。当用户点击一个新的页面的时候浏览器都会将页面的url压入栈中，当点击后退的时候则栈顶出栈，并且将出栈的元素压入另一个栈中存储起来。当点击前进的时候将另一个栈的栈顶出栈，压回之前的栈中。就这样就可以实现一个浏览器的前进后退功能。

最后说一下内存中的堆栈跟数据结构中的堆栈有什么区别。内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。

代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。

静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。

栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。

堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。

上一篇文章： 数据结构与算法的重温之旅（五）——如何运用链表 ​​​​​​​