数据结构之栈(Stack)

栈数据结构

栈是一种遵循后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称为栈顶。另一端叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

在现实生活中，也存在很多栈的例子，比如我们摆放的一摞书，或者堆放的盘子。

栈示例

栈也被用在编程语言的编译器和内存中保存变量、方法调用等。

创建栈

我们将创建一个类来表示栈。在这里我会使用ES6的class特性，如果你还不了解什么是ES6的class，请看这里。

class Stack {
  constructor() {
    this.items = [];
  }
  push() {} //添加元素入栈
  pop() {} //移除栈顶元素，返回被移除的元素
  peek() {} //返回栈顶的元素
  isEmpty() {} //判断栈是否为空，return Boolean
  clear() {} //清空栈
  print() {}  //输出栈元素
  size() {} //返回栈的元素个数
}

向栈添加元素

我们首先实现push方法，这个方法负责往栈中添加新元素，并且只添加到栈顶。

push(element) {
    this.items.push(element);
 }

从栈移除元素

因为栈遵循后进先出(LIFO)原则，所以我们使用数组的pop方法。

pop(element){
  this.items.pop(element)
}

查看栈顶元素

现在，为我们的类实现一些额外的辅助方法。如果想知道栈里最后添加的元素是什么，可以用peek方法。这个方法将返回栈顶的元素

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

检查栈是否为空

下面实现isEmpty方法，如果栈为空的话返回true，否则返回false。

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

清空栈元素

我们来实现清空栈元素方法，采取最简单的方法。

clear() {
  this.items = []
}

输出栈元素

现在我们实现这个辅助方法，输出栈元素。

print() {
  console.log(this.items.toString())
}

返回栈内元素个数

最后实现size方法，这个方法返回栈内的元素个数

size() {
  return this.items.length
}