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 = http://www.srcmini.com/stack.peek(); str += value +" "; stack.pop(); } console.log(str);

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

// 使用链表实现栈// 结点 function Node(value){ this.value = http://www.srcmini.com/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);