栈

栈（Stack）

栈，又名堆栈，是一种运算受限的线性数据结构，栈只能在表尾进行插入和删除操作。

栈中的元素只能先进后出（FILO, First In Last Out）。最早进入栈的元素所存放的位置叫作栈底（bottom），最后进入栈的元素存放的位置叫作栈顶（top）。

栈这种数据结构既可以用数组来实现，也可以用链表来实现。

顺序栈

使用数组方式实现的栈称为静态栈。可以根据下标来表示栈顶在数组中的位置，对于空栈，栈顶为 -1。

进行入栈操作时，栈顶指针 +1；出栈时，栈顶指针 -1。

对满栈进行入栈和对空栈进行出栈操作都会产生数组的越界并引起程序崩溃，称为上溢和下溢。因此使用顺序栈前需要提前声明一个数组的大小，如果数组大小不够则可能发生数组越界，如果数组太大则会浪费一定的空间。

使用数组实现的栈的执行效率会比用链表来实现的高，入栈和出栈不需要移动大量元素，只需要移动栈顶指针即可。

链式栈

使用链表方式实现的栈称为动态栈。通过在表头插入一个元素来实现入栈，通过删除表头元素来实现出栈。

动态栈有链表的部分特性，元素与元素之间在物理存储上可以不连续，但是功能有些受限制，动态栈只能在栈顶处进行插入和删除操作，不能在栈尾或栈中间进行插入和删除操作。

动态栈的元素内存是动态分配的，避免了静态栈可能会浪费空间的问题，但是对申请和释放空间的调用开销会比较大。

入栈（Push）

入栈操作就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。最初，栈为空，栈顶的初始值为 -1。每当向栈中添加元素时，栈顶指针 +1。

入栈只影响最后一个元素，不涉及元素的整体移动，所以固定容量顺序栈和链式栈的时间复杂度都是 $O(1)$。

以下动态数组示例的入栈是均摊 $O(1)$，需要扩容时单次为 $O(n)$。

stack_t *stack_push(stack_t *stack, T elem) {
    if (stack == NULL) {
        return NULL;
    }
    array_add(stack->data, elem);
    return stack;
}

出栈（Pop）

出栈操作就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。从栈中移出元素，栈顶指针 -1。数组中元素的删除并非真正意义上把元素从内存中清除，出栈只需对栈顶 -1 即可，后期向栈中添加元素时，新元素会将旧元素覆盖。

出栈只影响最后一个元素，不涉及元素的整体移动，所以无论是以数组还是链表实现，时间复杂度都是 $O(1)$。

T stack_pop(stack_t *stack) {
    if (stack == NULL) {
        exit(1);
    }
    return array_remove(stack->data, stack_size(stack) - 1);
}