JavaScript常用数据结构：栈(Stack)详解

栈是一种相当有用而又非常简单的数据结构，它的基本特点是先进后出或后进先出，也就是先入栈的数据，最后才出栈，最后入栈的数据先出栈。

以下几个基本的栈操作：

push：添加一个数据到栈中，如果栈已满，则拒绝添加数组，提示溢出警告。
pop：从栈顶删除一个数据，pop的数据顺序和push的顺序相反，如果栈为空，则不做任何操作。
peek或top：返回栈顶数据。
isEmpty：如果栈为空则返回true，否则返回false。

如何理解栈？

栈的实际应用非常多，可以说开发中几乎无处不在，连计算机提供给软件运行的方式也是使用栈的形式。如何理解栈呢？假设你有10本相同的书，将它们都整齐叠起来，这就是栈，然后只能从顶部取一本书。底部的书最先叠的，它是在最后才能取到，最后叠的一本书在顶部，这本书会被最先取出，这就是先进后出或后进先出。

栈操作的时间复杂度：push()，pop()，peek()，isEmpty()的时间复杂度均为O(1)。

栈的应用

栈的应用有哪些？下面是一些例子：

表达式的语法检查，例如数学表达式中的括号都是成对出现的，可以将所有的类似的符号入栈，发现有匹配则出栈，处理完成后如果发现栈不为空，则表达式语法错误。
表达式中缀到后缀/前缀的转换。
在编辑器，如Photoshop等很多地方都有的撤销功能。
Web浏览器的前进和后退功能。
其它很多高级算法中都有使用到栈，特别是使用栈实现DFS遍历，例如汉诺塔，树遍历，股票跨度问题，直方图问题。
其它应用例如：回溯算法，骑士旅行问题，迷宫问题，N皇后问题和数独问题等。
在图论算法中，栈用到的地方有拓扑排序和强连通分量。

栈的实现方式

栈可以使用两种方式实现：

使用数组实现栈。
使用链表实现栈。

先看第一种使用数组实现栈的代码，其中该实现方式中使用一个top索引指示栈顶，top的初始值为-1，push一个数组，top为1，以后再push则top继续增加。执行pop的时候只需要将top-1即可。

使用数组实现的优点是：实现简单，不需要使用额外的内存保存指针，缺点是：它不是动态的，也就是说数组的大小是固定的，只适用于知道数据量上界的情况。

使用数组实现栈的代码如下：

// 使用数组实现栈
function ArrayStack(capacity){
    if(capacity < 3){
        console.log("capacity is too small.");
        return null;
    }
    this.capacity = capacity;
    this.array = new Array(capacity);
    this.top = -1;
}

// 检查栈是否已空
ArrayStack.prototype.isEmpty = function(){
    return this.top == -1;
}

// 往栈添加一个数据
ArrayStack.prototype.push = function(value){
    if(this.top == this.capacity - 1){
        console.log("overflow: could not push data.");
        return;
    }
    this.array[++this.top] = value;
}

// 从栈顶取出一个数据
ArrayStack.prototype.pop = function(){
    if(this.top == -1)
        return null;
    return this.array[this.top--];
}

// 查看栈顶元素
ArrayStack.prototype.peek = function(){
    if(this.top == -1)
        return null;
    return this.array[this.top];
}

// 调用实例
var stack = new ArrayStack(10);
for(var i = 0;i < 10;i++){
    stack.push(i * i + 99);
}
var str = "";
while(!stack.isEmpty()){
    var value = stack.peek();
    str += value + " ";
    stack.pop();
}
console.log(str);

第二种实现栈的方式是使用链表，使用链表的好处是不需要预先申请内存，可以在运行时决定，缺点是需要额外的内存储存指针。在数据量上界不知道的时候，应首选栈的方式，其实现代码如下：

// 使用链表实现栈

// 结点
function Node(value){
    this.value = value;
    this.next = null;
}

// 栈
function LinkedStack(){
    this.size = 0;
    this.top = null;
}

// 检查栈是否已空
LinkedStack.prototype.isEmpty = function(){
    return this.size == 0;
}

// push操作
LinkedStack.prototype.push = function(value){
    var node = new Node(value);
    node.next = this.top;
    this.top = node;
    this.size++;
}

// pop操作
LinkedStack.prototype.pop = function(){
    if(this.size == 0)
        return;
    var top = this.top;
    var value = top.value;
    this.top = top.next;
    top = null;
    this.size--;
    return value;
}

// peek操作
LinkedStack.prototype.peek = function(){
    if(this.size == 0)
        return null;
    return this.top.value;
}

// 使用实例
var stack = new LinkedStack();
for(var i = 0;i < 10;i++)
    stack.push(i * i * i + 2);
var str = "";
while(!stack.isEmpty()){
    str += stack.peek() + " ";
    stack.pop();
}
console.log(str);

如何理解栈？

栈的应用

栈的实现方式

猜你喜欢