数据结构——栈

• 源码地址请点击此处

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

栈的基本结构

栈的基本结构如下所示：

栈的基本结构

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

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

栈的代码实现

下面是栈的代码实现，在 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 实现栈还是比较容易的。

完。