理解“栈”

“栈”的基本结构

后进者先出，先进者后出，就是典型的“栈”结构。

1570433001763

从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

从功能上来说，数组或链表可以替代栈，但特定的数据结构是对特定场景的抽象，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

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

实现一个“栈”

栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

java数组实现：

// 基于数组实现的顺序栈public class ArrayStack {  private String[] items;  // 数组  private int count;       // 栈中元素个数  private int n;           // 栈的大小  // 初始化数组，申请一个大小为 n 的数组空间  public ArrayStack(int n) {    this.items = new String[n];    this.n = n;    this.count = 0;  }  // 入栈操作  public boolean push(String item) {    // 数组空间不够了，直接返回 false，入栈失败。    if (count == n) return false;    // 将 item 放到下标为 count 的位置，并且 count 加一    items[count] = item;    ++count;    return true;  }  // 出栈操作  public String pop() {    // 栈为空，则直接返回 null    if (count == 0) return null;    // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一    String tmp = items[count-1];    --count;    return tmp;  }}

python数组实现：

class ArrayStack():
    """基于数组实现的顺序栈"""    def __init__(self, n: int):
        self.items = [None] * n  # 数组        self.count = 0  # 栈中元素的个数        self.n = n  # 栈的大小    def push(self, item) -> bool:
        # 数组空间不够了，直接返回 false，入栈失败。        if self.count == self.n:
            return False        # 将item放到下标为count的位置，并且count加1        self.items[self.count] = item
        self.count += 1        return True    def pop(self):
        # 栈为空，则直接返回 None        if self.count == 0:
            return None        # 返回下标为count-1的数组元素，并且栈中元素个数count减1        tmp = self.items[self.count - 1]
        self.count -= 1        return tmp
    def __str__(self):
        return str(self.items[:self.count])

python的栈实现：

class ListNode:
    def __init__(self, data: int, next=None):
        self._data = data
        self._next = nextclass LinkedStack:
    """基于单链表实现的栈    """    def __init__(self):
        self._top: ListNode = None    def push(self, value):
        # 添加元素        new_top = ListNode(value)
        new_top._next = self._top
        self._top = new_top
        return True    def pop(self):
        # 删除并返回栈顶元素        value = self._top._data
        self._top = self._top._next
        return value
    def __str__(self) -> str:
        vals = []
        p: ListNode = self._top
        while p:
            vals.append(str(p._data))
            p = p._next
        return '->'.join(vals)

不管是顺序栈还是链式栈，存储数据只需要一个大小为 n 的存储空间。

在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

空间复杂度是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。