Yanniyanni

栈

上次更新时间：4/6/2021, 6:10:35 PM 0

栈（Stack）是限定在表尾进行插入和删除操作的线性表。栈又称为后进先出（Last In First Out）的线性表，简称 LIFO 结构。

# 存储结构

栈也可以有两种存储结构：

  • 顺序存储结构：可用 （一维数组）。

    顺序存储结构还可以使用两栈共享空间的方式，但仅适用于一些一个栈增加，另一个栈减少的场景。（如定量的股票买卖）

  • 链式存储结构：简称为链栈。

存储结构 操作 时间复杂度 应用场景
顺序存储结构 进栈与出栈 O(1) 栈的大小可预测，使用顺序存储好些
链式存储结构 进栈与出栈 O(1) 栈内元素变化莫测，栈大小可能很大，可能很小，则使用链栈好些

# 栈的实现

JavaScript 中没有栈的数据结构，但是可以用数组实现栈的所有功能。

# 抽象数据类型定义

  • ADT 栈（Stack）
    • Data
      • 同线性表，相邻元素具有前驱和后继关系
    • Operation
      • InitStack(*S): 初始化操作，建立一个空栈 S。
      • DestroyStack(*S): 若栈存在，则销毁它。
      • Clear(*S): 清空栈。
      • Peek(S, *e): 若栈存在且非空，用 e 返回 S 的栈顶元素。
      • Push(*S, e): 若栈 S 存在，插入新元素 e 到栈 S 中并成为栈底元素。
      • Pop(*S, *e): 删除栈 S 中栈顶元素，并用 e 返回其值。
      • length(S): 返回栈 S 的元素个数。
  • endADT
function Stack() { 
    this.dataStore = [];  // 初始化一个空数组来保存 
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.clear = clear;
    this.length = length; 
}
function push(element) { 
    this.dataStore[this.top++] = element; 
}
function peek() { 
    return this.dataStore[this.top-1];
}
function pop() { 
    return this.dataStore[--this.top]; 
}
function clear() {
    this.top = 0; 
}
function length() { 
    return this.top; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 栈的应用

符合后进先出的场景都可以使用栈来解决。

上次更新时间: 4/6/2021, 6:10:35 PM

← 队列 →