JS 里的数据结构 - 栈

学习笔记 本文总阅读量次

开篇语

未来将会结合《学习 JavaScript 数据结构和算法》这本书写一系列的算法笔记。

之所以想要深入学习算法的原因，是前段时间阿里的校招让我打击很大，自信心受到了强烈的冲击。但好在我是一个从来不怕低谷的人，也十分庆幸在很早的时间点里受到迟早该受到的挫折。

逝者如斯，故不舍昼夜。

栈

栈数据结构

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

JavaScript 里的 Stack 类

创建一个 Stack 类的构造函数

1
2
3
function Stack(){
  // 各种属性和方法的声明
}

需要一种数据结构来保存栈里的元素

1
2
3
4
function Stack(){
  let items = [];
  // 各种属性和方法的声明
}

向栈里添加元素

添加一个 push 方法

1
2
3
4
5
6
function Stack(){
  let items = [];
  this.push = function(item){
    items.push(item);
  }
}

从栈里删除元素

添加一个 pop 方法

1
2
3
4
5
6
7
8
9
function Stack(){
  let items = [];
  this.push = function(item){
    items.push(item);
  }
  this.pop = function(item){
    items.pop(item);
  }
}

查看栈顶元素

添加一个 peek 方法

1
2
3
4
5
6
7
8
9
10
11
12
function Stack(){
  let items = [];
  this.push = function(item){
    items.push(item);
  }
  this.pop = function(item){
    items.pop(item);
  }
  this.peek = function(){
    return items[items.length - 1];
  }
}

检查栈是否为空

添加一个 isEmpty 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Stack(){
  let items = [];
  this.push = function(item){
    items.push(item);
  }
  this.pop = function(item){
    items.pop(item);
  }
  this.peek = function(){
    return items[items.length - 1];
  }
  this.isEmpty = function(){
    return items.length == 0;
  }
}

清空栈的内容

添加一个 clear 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function Stack(){
  let items = [];
  this.push = function(item){
    items.push(item);
  }
  this.pop = function(item){
    items.pop(item);
  }
  this.peek = function(){
    return items[items.length - 1];
  }
  this.isEmpty = function(){
    return items.length == 0;
  }
  this.clear = function(){
    items = []; 
  }
}

打印栈的内容

添加一个 print 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function Stack(){
  let items = [];
  this.push = function(item){
    items.push(item);
  }
  this.pop = function(item){
    items.pop(item);
  }
  this.peek = function(){
    return items[items.length - 1];
  }
  this.isEmpty = function(){
    return items.length == 0;
  }
  this.clear = function(){
    items = []; 
  }
  this.print = function(){
    console.log(items.toString());
  }
}

输出栈的元素数量

添加一个 size 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function Stack(){
  let items = [];
  this.push = function(item){
    items.push(item);
  }
  this.pop = function(item){
    items.pop(item);
  }
  this.peek = function(){
    return items[items.length - 1];
  }
  this.isEmpty = function(){
    return items.length == 0;
  }
  this.clear = function(){
    items = []; 
  }
  this.print = function(){
    console.log(items.toString());
  }
  this.size = function(){
    console.log(items.length);
  }
}

使用 Stack 类

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
function Stack(){
  let items = [];
  this.push = function(item){
    items.push(item);
  }
  this.pop = function(item){
    items.pop(item);
  }
  this.peek = function(){
    return items[items.length - 1];
  }
  this.isEmpty = function(){
    return items.length == 0;
  }
  this.clear = function(){
    items = []; 
  }
  this.print = function(){
    console.log(items.toString());
  }
  this.size = function(){
    console.log(items.length);
  }
}

let stack = new Stack();
stack.push('one');
stack.print(); // one
stack.size(); // 1
console.log(stack.peek()); // one
学习笔记