[数据结构与算法]栈-跟着JavaScript学习数据结构 一

栈-跟着JavaScript学习数据结构 一

栈数据机构

栈是一种遵从后进先出原则的有序集合。新添加或者待删除的元素都保存在栈的同一端，称为栈顶，另一端就叫栈底，在栈里，新元素的都靠近栈顶，旧元素都靠近栈底，比如一摞书，一堆碟子

创建一个基于数组的栈

我们通过创建一个类来表示栈

    class Stack{
        constructor(){
            this.items=[]
        }
    }

我们需要一种数据结构来保存栈里的元素，可以选择数组，数组允许我们在任意位置添加或者删除元素，由于栈遵循LIFO原则，需要对元素的插入和删除功能进行限制，规定一些方法

• push 添加一个（或几个）到栈顶
• pop 删除栈顶的元素，同时返回被移除的元素
• peek 返回栈顶的元素，不对栈做任何的修改
• isEmpty 如果栈里没有任何元素就返回true，否则返回false
• clear 移除栈的所有元素
• size 返回栈中的元素个数

向栈中添加元素

function Stack() {
    //1.各种属性和方法的声明
        var items = [] [];//1.1需要一种数据结构来保存栈里的元素。可以选择数组
        // 1.2接下来，要为我们的栈声明一些方法
        this.push = function(element){
            items.push(element);
            console.log(items);
        };
    }
    //测试类
    var s =new Stack();
    s.push("aa");
    s.push("bb");

向栈中删除元素

     this.pop = function(){
            return items.pop();
        };

查看栈顶元素

为我们的类实现一些额外的辅助方法。如果想知道栈里最后添加的元素是什么，可以用 peek 方法。这个方法将返回栈顶的元素：
因为类内部是用数组保存元素的，所以访问数组的最后一个元素可以用 length - 1

 this.peek = function(){
            return items[items.length-1];
        };

判断栈是否为空

如果栈为空的话将返回 true ，否则就返回 false ：
使用 isEmpty 方法，我们能简单地判断内部数组的长度是否为0

 this.isEmpty = function(){
            return items.length == 0;
        };

返回栈的长度

类似与数组的length属性

 this.size = function(){
        return items.length
 }

清空栈

数组的清空的最简单的方法就是将length置为0

  this.clear = function(){
      items.length = 0
  }

打印栈元素

    this.print = function(){
           console.log(items.toString());
        }

使用stack类

function Stack() {
        var items = [];
        // 判断栈是否为空
        this.isEmpty = function(){
            return items.length == 0;
        };
        // 往栈里添加的元素
        this.push = function(element){
            items.push(element);
            console.log(items)
        };
        // 往栈里添加的最后一个元素
        this.peek = function(){
            return items[items.length-1];
        };
        // 栈里有多少个元素
        this.size = function(){
            return items.length;
        };
        // 移除
        this.pop = function(){
            return items.pop();
        };
        // 打印栈现在的元素有哪些
        this.print = function(){
           console.log(items.toString());
        };
    }
    var stack =new Stack();//
    console.log(stack.isEmpty());//true
    stack.push(5);
    stack.push(8);
    console.log(stack.peek());//输出8.因为它是往栈里添加的最后一个元素
    stack.push(11);
    console.log(stack.size());//3
    console.log(stack.isEmpty()); //输出false
    stack.pop();
    console.log(stack.size()); //输出2
    stack.print();//5,8