数据结构：栈与队列的实现与 OJ 题解析

知识点速览

栈

何为栈？栈是一种线性结构，只允许在一端进行插入和删除元素的数据结构。

压栈（入栈）：插入元素 出栈：删除元素 栈顶：进行插入和删除元素的一端 栈底：固定的，不允许进行插入和删除元素

存储特点：先进后出、后入先出。想象成一个一端开口的容器！

栈的存储结构分析

栈可以用两种结构来实现，一种是顺序栈（数组实现），另一种是链式栈（链表实现）。综合考虑，优先选择顺序栈。

顺序栈： 顺序栈出栈、入栈都很方便，栈顶指针也方便指向，有一个小缺点：扩容可能导致空间浪费。

链式栈： 链式栈虽然扩容很方便，无浪费情况，但是出栈时，不好控制栈顶指针，设置稍微复杂一点。比如单链表，需要将链表倒置过来，否则栈的存储特性就与其不符，出栈时需要知道倒数第二个链表节点。还有双链表结构，虽然不用去找倒数第二个节点，但是写起来没有那么的简单、快捷。

栈的基本操作

初始化栈、判断栈空、入栈、读取栈元素、出栈、销毁栈。

结构体定义

顺序栈只需要一个栈顶指针、一个空间指针即可。在初始化时给空间指针开辟空间，这里建议可以额外设置一个空间上限，方便以后扩容。

typedef struct Stack {
    int top;        // 栈顶指针
    int* data;      // 存储空间指针
    int max;        // 存储上限
}Stack;

初始化栈

栈的初始状态应该是栈顶指针在栈底的位置，再给栈开辟空间。

// 初始化栈
void Init(Stack* stack) {
    // 初始化栈顶指针、空间上限
    stack->max = MAX;
    stack->top = 0;
    // 开辟存储空间
    stack->data = (int*)malloc(sizeof(int) * MAX);
    // 判断空间有效性
    if (stack->data == NULL) {
        printf("开辟失败\n");
        return;
    }
    printf();
}