阅读 104

数据结构(栈实现篇)

在数据结构与算法中,栈stack又名堆栈,栈是一种受限的线性储存结构,只允许在一端加入元素和删除元素。这一端称为栈顶,加入元素称作入栈、压栈、进栈;删除元素又称作出栈、退栈。被删除元素的相邻元素会重新称为栈顶元素。栈遵循先进后出FILO的规则。

栈结构示意图

stack

栈结构使用

在编程语言中很多时候使用到栈的数据结构。例如函数栈结构。A函数调用B函数,B函数调用了C函数。语言执行先会把A函数、B函数、C函数依次进栈;待C函数执行完成出栈,B函数出栈,最后A函数完成出栈。

functions
生活中具有比较多的类似于栈的结构,比如叠罗汉、子弹夹、文件叠在一起等等。理解栈结构原理对我们编程具有很大的帮助。下面会使用 JavaScript实现我们的栈结构。

实现栈结构的功能

  • push(element):push是进栈操作,其中element是需要进栈的元素,返回操作成功与否布尔值。
  • pop():pop移除栈顶元素操作,返回移除的栈顶元素。
  • size():获取栈中的栈元素数量,返回一个数字。
  • isEmpty():判断栈是否为空,返回一个布尔值。
  • peek():返回栈顶元素,但不移除栈顶元素。
  • bottom():返回栈底元素。
  • clear():清除所有栈元素,返回操作成功与否布尔值。

进栈与出栈流程

flow

ES6 栈结构代码

class Stack {
    constructor() {
        this.lists = [];
    }
    size() {
        return this.lists.length;
    }
    isEmpty() {
        return this.lists.length === 0;
    }
    peek() {
        const topIndex = this.size() - 1;
        return this.lists[topIndex];
    }
    bottom() {
        return this.lists[0];
    }
    push(element) {
        this.lists.push(element);
        return true;
    }
    pop() {
        return this.lists.pop();
    }
    clear() {
        this.lists = [];
        return true;
    }
    toString() {
        let result = "";
        this.lists.forEach(value => {
            result = result + "" + value;
        });
        return result;
    }
}
复制代码

ES5 栈结构代码

通过ES5把功能函数可以绑定在对象的实例上,也可以把功能函数加在函数的原型链上

    function Stack() {
        this.lists = [];
    }
    Stack.prototype.push = function (element) {
        this.lists.push(element);
        return true;
    }
    Stack.prototype.pop = function () {
        return this.lists.pop();
    }
    Stack.prototype.clear = function () {
        this.lists = [];
        return true;
    }
    Stack.prototype.peek = function () {
        var topIndex = this.size() - 1;
        return this.lists[topIndex];
    }
    Stack.prototype.size = function () {
        return this.lists.length;
    }
    Stack.prototype.isEmpty = function () {
        return this.lists.length === 0;
    }
    Stack.prototype.bottom = function () {
        return this.lists[0];
    }
    Stack.prototype.toString = function () {
        var result = "";
        for (var i = 0; i < this.lists.length; i++) {
            result = result + '' + this.lists[i];
        }
        return result;
    }
复制代码

ES5和ES6实现栈结构已经通过了测试可运行。上面是通过数组实现的栈结构,其实链表也可以实现栈结构。下面数据结构链表篇会使用链表实现栈的数据结构
github地址: github.com/Harhao

关注下面的标签,发现更多相似文章
评论