image.png

定义

  1. 后进者先出，先进者后出，简称 后进先出（LIFO），这就是典型的栈结构。
  2. 新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。
  3. 在栈里，新元素都靠近栈顶，旧元素都接近栈底。
  4. 从栈的操作特性来看，是一种 操作受限的线性表，只允许在一端插入和删除数据。
  5. 不包含任何元素的栈称为空栈。

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

实现

栈的方法：

  • push(element)：添加一个（或几个）新元素到栈顶。
  • pop()：移除栈顶的元素，同时返回被移除的元素。
  • peek()：返回栈顶的元素，不对栈做任何修改。
  • isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。
  • clear()：移除栈里的所有元素。
  • size()：返回栈里的元素个数。
  1. // Stack类
  2. function Stack() {
  3.   this.items = [];
  5.   // 添加新元素到栈顶
  6.   this.push = function(element) {
  7.     this.items.push(element);
  8.   };
  9.   // 移除栈顶元素，同时返回被移除的元素
  10.   this.pop = function() {
  11.     return this.items.pop();
  12.   };
  13.   // 查看栈顶元素
  14.   this.peek = function() {
  15.     return this.items[this.items.length - 1];
  16.   };
  17.   // 判断是否为空栈
  18.   this.isEmpty = function() {
  19.     return this.items.length === 0;
  20.   };
  21.   // 清空栈
  22.   this.clear = function() {
  23.     this.items = [];
  24.   };
  25.   // 查询栈的长度
  26.   this.size = function() {
  27.     return this.items.length;
  28.   };
  29.   // 打印栈里的元素
  30.   this.print = function() {
  31.     console.log(this.items.toString());
  32.   };
  33. }