栈 | sanbeiicecream

栈是一种遵从后进先出（LIFO => Last In First Out）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

只是知道这个数据结构的特性是不够的，还需要使用代码来模拟这些特性，将抽象定义具体化

需要的方法

push(element(s))：添加一个（或几个）新元素到栈顶。
pop()：移除栈顶的元素，同时返回被移除的元素。
peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它
isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。
clear()：移除栈里的所有元素。
size()：返回栈里的元素个数。该方法和数组的 length 属性很类似

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Stack {
  constructor() {
    this.items = []
  }
  push(elements) {
    this.items.push(elements)
  }
  pop() {
    return this.items.pop()
  }
  peek() {
    return this.items[this.items.length - 1]
  }
  isEmpty() {
    return !this.items.length
  }
  clear() {
    this.items = []
  }
  size() {
    return this.items.length
  }
}

借用数组来实现一个栈可以说是很容易，但是需要思考一下，用数组来模拟栈的性能如何
在使用数组时，大部分方法的时间复杂度是 O(n)
数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间
具体内容 => 深入V8 - js数组的内存是如何分配的
数组内存分配动态扩展会影响速度，而且数组本来也有一些特性，所以使用更为简单的对象来模拟更合适

 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


class StackWithObj {
  constructor() {
    this.items = {}
    this.count = 0
  }
  push(elements) {
    this.items[this.count] = elements
    this.count++
  }
  pop() {
    if (this.count > 0) {
      this.count -= 1
      const result = this.items[this.count]
      delete this.items[this.count]
      return result
    }
  }
  peek() {
    return this.items[this.count - 1]
  }
  isEmpty() {
    return !this.count
  }
  clear() {
    this.count = 0
  }
  size() {
    return this.count
  }
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

栈的模拟实现是比较简单的，想要熟练掌握算法与数据结构，没有捷径，唯有刷题！！！

需要的方法#

相关题目#

需要的方法

相关题目