数据结构——栈

源码地址请点击此处

栈是线性表的一种衍生结构，是一种操作受限的线性表。在使用普通的线性表时，可以在任意位置进行操作，比如插入元素、删除元素、查找元素等。而栈只能在一端进行操作，并且不具备插入和查找的功能。

栈的基本结构

栈的基本结构如下所示：

栈的基本结构

栈是一种先进后出（FILO，First In Last Out）的数据结构，因此，如果将元素添加到栈中的顺序为 a1，a2，...，an，那么将元素从栈中移除的顺序就是 an，...，a2，a1。
栈有以下几个基本概念：

入栈
将元素添加到栈中，也称为进栈、压栈。
出栈
将元素从栈中移除，也成为退栈、弹栈。
栈顶
入栈和出栈只能在栈的一端进行，叫做栈顶。
栈底
相对于栈顶，栈的另外一端被称为栈底。

栈的代码实现

下面是栈的代码实现，在 JavaScript 中实现栈数据结构需要借助数组，其中进栈和出栈操作需要分别借助于数组的 push() 方法和 pop() 方法。

接口定义

interface IStack<T>{
    // 获取栈的长度
    size():number;
    // 压栈操作
    push(ele:T):T;
    // 出栈操作
    pop():T;
    // 获取栈顶的元素
    peek():T;
    // 清除栈中的元素
    clear():void;
    // 判断栈是否为空
    isEmpety():boolean;
    // 获取栈中的元素信息
    toString():T[];
}

接口实现

class Stack<T> implements IStack<T>{
    private _size:number = 0;
    private dataStore:T[] = [];
    size():number{
        // 获取栈的长度
        return this._size;
    }
    push(ele:T):T{
        // 向栈中插入元素，借助数组的 push 方法
        this.dataStore.push(ele);
        this._size++;
        return ele;
    }
    pop():T{
        // 从栈中移除元素，借助数组的 pop 方法
        const ele = this.dataStore.pop();
        this._size--;
        return ele;
    }
    peek():T{
        // 获取栈顶的元素
        const index = this._size ? (this._size - 1) : this._size;
        return this.dataStore[index];
    }
    clear():void{
        // 清除栈中的元素
        this.dataStore = [];
        this._size = 0;
    }
    isEmpety():boolean{
        // 判断栈是否为空
        return !this._size;
    }
    toString():T[]{
        // 返回栈中的元素信息
        return this.dataStore;
    }
}

可见，栈的实现比普通线性表（List）要简单许多，使用 JavaScript 实现栈还是比较容易的。

完。

最后编辑于：2018.02.16 11:22:52