🎧 fe tutorial

Appearance

Return to top
On this page

栈

什么是栈

栈就像一摞叠在一起的盘子，放盘子的时候，从上往下一个一个放；取的时候，也是从上往下一个一个取，不能任意从中间取出。后进先出，先进后出，这就是“栈”结构。

stack

这么一看的话，栈是一种操作受限的线性表，它只允许在一端插入和删除数据。相比于数组和链表，栈看起来没有任何优势，那为什么还要用栈呢？

特定的数据结构是特定场景的抽象。数组和链表功能上是可以替换栈的，但是它们暴露了太多的接口，操作时灵活的同时也更加不可控，自然也比较容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足先进后出，后进先出的特性，我们就应该首选“栈”这种数据结构。

怎么实现一个栈？

从栈的定义中我们知道，栈主要包含两个操作，入栈和出栈。也就是在栈顶插入一个数据或者从栈顶删除一个数据。栈即可以用数组来实现，也可以使用链表来实现。用数组实现的栈叫作顺序栈。用链表实现的栈叫作链式栈。

实现一个顺序栈

js
class ArrayStack {
  constructor() {
    this.items = [];
  }

  push(item) {
    this.items.push(item);
  }

  pop() {
    return this.items.pop();
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
    return true;
  }

  display() {
    this.items.forEach(item => console.log(item));
  }
}

实现一个链式栈

js
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;
  }

  push(value) {
    const node = new Node(value);
    if (this.top = null) {
      this.top = node;
    } else {
      node.next = this.top;
      this.top = node;
    }
  }

  pop() {
    if (this.top === null) {
      return;
    } else {
      const value = this.top.element;
      this.top = this.top.next;
      return value;
    }
  }

  clear() {
    this.top = null;
  }

  size() {
    let count = 0;
    if (this.top !== null) {
      let temp = this.top;
      while (temp !== null) {
        ++count;
        temp = temp.next;
      }
    }
    return count;
  }

  display() {
    if (this.top !== null) {
      let temp = this.top;
      while (temp !== null) {
        console.log(temp.element);
        temp = temp.next;
      }
    }
  }
}

复杂度

不管是顺序栈还是链式栈，存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈的时候，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

空间复杂度是指算法运行需要的额外的存储空间，不包括原本的数据存储空间，所以这里并不是 O(n)。

而时间复杂度，不管是顺序栈还是链式栈，入栈、出栈都只涉及个别数据的操作，所以时间复杂度是 O(1)。

Edit this page on GitHub