栈结构概述

1 认识栈结构

我们都知道数组是一种线性结构，并且可以在任意位置插入和删除数据。但是有时为了实现某些功能，我们必须对这种任意性加以限制。而栈和队列就是常见的受限的线性结构。

栈是一种受限的线性表，后进先出。其限制是仅允许在表的一端进行插入和删除操作，这一端被称为栈顶，另一端称为栈底。LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间。向一个栈插入新元素又称为进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。从一个栈删除元素又称作出栈或退栈，它把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈结构示意图：

在生活中我们也可以见到类似于栈的现象，比如说放盘子。当我们洗好盘子之后，我们会将它们叠在一起，最先洗完的盘子会被放在最下方，然后洗完一个盘子叠一个盘子，依次类推，这时最上面的盘子是最新洗完的盘子。当我们再次取用这些盘子时，最上面的盘子是我们最先开始使用的，然后才会依次向下取盘子，也就是说最底下的盘子是最后被取用的。这就是“后进先出”，最先进去的元素是最后出去的，最后进去的元素是最先出去的。

2 通过实例理解栈

1、程序中使用栈
在程序中，函数与函数之间可以相互调用。比如说A调用B，B调用C，C调用D。在执行过程中首先会将A压入栈，但是由于A还要调用B，没有执行完，因此A不能出栈，这时会将B压入栈，B也不会出栈，因为还要调用C，这时会将C压入栈，在C中调用了D，因此D也会入栈。D并没有调用其他的函数，因此当D执行完后，D可以出栈，此时C执行完了出栈，紧接着是B，然后是A。

2、有6个元素6，5，4，3，2，1，按照该顺序进栈，下列哪一个不是合法的出栈顺序？
A、5 4 3 6 1 2       B、4 5 3 2 1 6       C、3 4 6 5 2 1       D、2 3 4 1 5 6

答案是C。
A：第一个出栈的是5，所以6进栈，5进栈然后出栈；第二个出栈的是4，因此4进栈然后出栈；第三个出栈的是3，因此3进栈然后出栈；第四个出栈的是6，因此6出栈；第五个出栈的是1，因此2进栈，1进栈后出栈；第六个出栈的是1，此时1出栈。
B、第一个出栈的是4，因此6进栈，5进栈，4进栈出栈；第二个出栈的是5，因此5出栈；第三个出栈的是3，因此3进栈出栈；第四个出栈的是2，因此2进栈出栈；第五个出栈的是1，因此1进栈出栈；第六个出栈的是6，6出栈。
C、第一个出栈的是3，因此6进栈，5进栈，4进栈，3进栈出栈；第二个出栈的是4，因此4出栈；第三个出栈的是6，但是此时6不是栈顶，5是栈顶，因此6不能出栈，故错误。
D、第一个出栈的是2，因此6进栈，5进栈，4进栈，3进栈，2进栈出栈；第二个出栈的是3，3出栈；第三个出栈的是4，4出栈；第四个出栈的是1，1进栈出栈；第五个出栈的是5，5出栈；第六个出栈的是6，6出栈。

3 实现栈结构

实现栈结构有两种比较常见的方式：数组和链表

栈常见的操作：

• push()：添加一个新元素到栈顶
• pop()：移除栈顶的元素，同时返回被移除的元素
• peek()：返回栈顶的元素，不对栈做任何修改
• isEmpty()：如果栈中没有任何元素就返回true，否则返回false
• size()：返回栈中的元素个数
• toString()：将栈结构的内容以字符形式返回

使用代码实现基于数组的栈：

// 封装栈类
function Stack() {
    this.items = []; // 栈的属性

    // 将元素压入栈
    Stack.prototype.push = function (element) {
        this.items.push(element);
    }
    
    // 从栈取出元素
    Stack.prototype.pop = function () {
        return this.items.pop();
    }
    
    // 查看栈顶元素
    Stack.prototype.peek = function () {
        return this.items[this.items.length - 1];
    }
    
    // 判断栈是否为空
    Stack.prototype.isEmpty = function () {
        return this.items.length == 0;
    }
    
    // 获取栈中元素的个数
    Stack.prototype.size = function () {
        return this.items.length;
    }
    
    // toString()
    Stack.prototype.toString = function () {
        // 按照元素+空格+元素将其转化为字符串
        let result = "";
        for (let i = 0; i < this.items.length; i++) {
            result += this.items[i] + " ";
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

示例：编写程序将十进制转化为二进制

【如何将十进制转化为二进制】要把十进制转化为二进制，我们需要将该十进制数字和2整除，直到结果是0为止。例如，将100转化为二进制，首先将100对2取余，余数是0，100/2=50；将50对2取余，余数是0，50/2=25；将25对2取余，余数是1，24/2=12；将12对2取余，余数是0，12/2=6；将6对2取余，余数是0，6/2=3；将3对2取余，余数是1，2/2=1；将1对2取余，余数是1。它的二进制从后往前读取，为：1100100。

代码如下：

// 函数：十进制转二进制
function fun(n) {
    // 定义栈对象
    var stack = new Stack();
    // 循环操作
    while (n > 0) {
        // 余数入栈
        stack.push(n % 2);
        // 获取整除结果，向下取整
        n = Math.floor(n / 2);
    }
    // 从栈中取出，并保存为字符串
    let s = "";
    while (!stack.isEmpty()) { // 直到栈空了停止
        s += stack.pop();
    }
    return s;
}
console.log(fun(100)); // 1100100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19