个性化阅读
专注于IT技术分析

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

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

JavaScript基本数据结构:栈(Stack)详解

以下几个基本的栈操作:

  1. push:添加一个数据到栈中,如果栈已满,则拒绝添加数组,提示溢出警告。
  2. pop:从栈顶删除一个数据,pop的数据顺序和push的顺序相反,如果栈为空,则不做任何操作。
  3. peek或top:返回栈顶数据。
  4. isEmpty:如果栈为空则返回true,否则返回false。
栈(stack)的基本结构

如何理解栈?

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

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

栈的应用

栈的应用有哪些?下面是一些例子:

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

栈的实现方式

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

  1. 使用数组实现栈。
  2. 使用链表实现栈。

先看第一种使用数组实现栈的代码,其中该实现方式中使用一个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);
赞(0) 打赏
未经允许不得转载:srcmini » JavaScript常用数据结构:栈(Stack)详解
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏