前端学习笔记

栈

概念

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作，遵循后进先出规则

栈常用的存储结构

  • 顺序存储，使用数组
  • 链式存储，使用链表

栈的设计: 顺序存储

主要有两个操作：将元素压入栈，push方法；将栈顶元素出栈，pop方法。

除此外，还定义查看栈顶元素值的peek方法，返回栈顶元素值，但不删除它；定义清空当前栈内的所有元素的clear方法；返回当前栈内元素总数length方法

Stack类

定义栈的属性和方法

function Stack () {
  this.dataStore = [];    //保存栈内元素，初始化为空数组
  this.top = 0;           //记录栈顶位置
  this.pop = pop;         //出栈
  this.push = push;       //入栈
  this.peek = peek;       //查看栈顶元素
  this.length = length;   //查看栈内元素总数
  this.display = display; //查看打印栈内元素
  this.clear = clear;     //清空栈
}
1
2
3
4
5
6
7
8
9
10

push方法：向栈内压入一个元素

// 出栈
function push (element) {
  this.dataStore[this.top++] = element;
}
1
2
3
4

pop方法：取出栈顶元素

// 入栈
function pop () {
  return this.dataStore[--this.top]; // 返回栈顶元素，并将 top 的值减 1
}
1
2
3
4

peek方法：查看栈顶元素

// 查看栈顶元素
function peek () {
  if (this.top > 0) {
    return this.dataStore[this.top - 1]; // 返回栈顶元素
  } else {
    return 'empty';
  }
}
1
2
3
4
5
6
7
8

length方法: 返回栈内元素总数

// 返回栈内元素总数
function length() {
  return this.top;
}
1
2
3
4

display方法: 查看所有栈内元素

// 查看所有栈内元素
function display() {
  return this.dataStore;
}
1
2
3
4

clear方法: 清空栈内元素

// 清空栈内元素
function clear() {
  this.dataStore = [];
  this.top = 0;
}
1
2
3
4
5

示例

function Stack () {
  this.dataStore = [];    //保存栈内元素，初始化为空数组
  this.top = 0;           //记录栈顶位置
  this.pop = pop;         //出栈
  this.push = push;       //入栈
  this.peek = peek;       //查看栈顶元素
  this.length = length;   //查看栈内元素总数
  this.display = display; //查看打印栈内元素
  this.clear = clear;     //清空栈
}

// 出栈
function push (element) {
  this.dataStore[this.top++] = element;
}

// 入栈
function pop () {
  return this.dataStore[--this.top]; // 返回栈顶元素，并将 top 的值减 1
}

// 查看栈顶元素
function peek () {
  if (this.top > 0) {
    return this.dataStore[this.top - 1]; // 返回栈顶元素
  } else {
    return 'empty';
  }
}

// 返回栈内元素总数
function length() {
  return this.top;
}

// 查看所有栈内元素
function display() {
  return this.dataStore;
}

// 清空栈内元素
function clear() {
  this.dataStore = [];
  this.top = 0;
}

// 示例
var fruits = new Stack()
fruits.push('香蕉')
fruits.push('橘子')
fruits.display() // ["香蕉", "橘子"]
fruits.length() // 2
fruits.peek() // "橘子"
fruits.pop() // "橘子"
fruits.peek() // "香蕉"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

栈的设计: 链式存储

TODO

待补充

←