常见数据结构

发表于 | 更新于 | 阅读次数：

时间复杂度

通常使用最差的时间复杂度来衡量一个算法的好坏。
常数时间O(1)代表这个操作和数据量没有关系，是一个固定时间的操作，比如说四则运算。

对于一个算法来说，可能会计算出操作次数为 aN + 1，N代表数据量。那么该算法的时间复杂度就是O(N)。因为我们在计算时间复杂度的时候，数据量通常是非常大的，这时候低阶项和常数项可以忽略不计。

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

栈

概念

栈是一个线性结构，在计算机中是一个相当常见的数据结构。
栈的特点是只能在某一端添加或删除数据，遵循先进后出的原则。

实现

每种数据结构都可以用很多种方式来实现，其实可以把栈当做一个数组的子集，所以这里使用数组来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Stack {
  constructor() {
    this.stack = [];
  }
  push(item) {
    this.stack.push(item);
  }
  pop() {
    this.stack.pop();
  }
  getCount() {
    return this.stack.length;
  }
  peek() {
    return this.stack[this.getCount - 1];
  }
  isEmpty() {
    return this.getCount() === 0;
  }
}

应用

匹配括号，可以通过栈的特性来完成

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
var isValid = function(s) {
  let map = {
    '(': -1,
    ')': 1,
    '[': -2,
    ']': 2,
    '{': -3,
    '}': 3,
  };
  let stack = [];

  for (let i of s) {
    if (map[i] < 0) {
      stack.push(i);
    } else {
      let last = stack.pop();
      if (map[last] + map[i] !== 0) {
        return false;
      }
    }
  }

  if (stack.length > 0) {
    return false;
  }

  return true;
}

队列

概念

队列是一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。

实现

单链队列和循环队列

单链队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Queue {
  constructor() {
    this.queue = [];
  }
  enQueue(item) {
    this.queue.push(item);
  }
  deQueue() {
    return this.queue.shift();
  }
  getHeader() {
    return this.queue[0];
  }
  getLength() {
    return this.queue.length;
  }
  isEmpty() {
    return this.queue.length === 0;
  }
}

循环队列

链表