这篇博客为大家带来的是 栈的概念简述、栈的概念选择题、栈的结构选择、C语言实现栈以及栈的一道OJ题。内容相对比较简单。话不多说，我们这就开始。
1. 栈的概念
栈 是一个特殊的 线性表。
栈只允许在固定的一段进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，不进行操作的一端称为栈底。
栈中的元素遵守 后进先出 (LIFO - Last In First Out) 的原则。也就是先进的后出，后进的先出，就像手枪的弹匣一样。后被装入的子弹，也就是弹匣顶端的子弹先被枪打出。
栈对于数据的管理主要有两种操作：
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈，从栈顶进行压栈。
出栈：栈的删除操作叫做 出栈，从栈顶进行出栈。
栈的操作流程：
栈的概念选择题：
一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出
栈的顺序是（ ）。
A. 12345ABCDE
B. EDCBA54321
C. ABCDE12345
D. 54321EDCBA
答案：B
首先明确栈的原则：后进先出。
将以上元素依次入栈，那么最入栈的最晚出栈，那么1应该最后一个出栈，直接选出结果：EDCBA54321
若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A. 1,4,3,2
B. 2,3,4,1
C. 3,1,4,2
D. 3,4,2,1
答案：C
做对这道题目，我们需要知道，栈不是所有数据入栈后才能出栈的，栈可以入栈部分元素，然后出栈，再入栈其他元素。
下面对每个选项进行分析：
A：1 先入栈，然后出栈，栈空；随后 2, 3, 4 依次入栈。然后将元素全部出栈，栈空。得到结果为：1, 4, 3, 2
B：1, 2 先入栈；然后出栈 2，栈中余1；再入栈 3，出栈 3，栈中余1；再入栈 4，出栈 4，栈中余1；最后出栈 1，栈空。得到结果为：2, 3, 4, 1
C：这种序列答案是绝对不可能的。通过 A、B两个选项和这道题的进栈序列我们也可以找出规律：某个元素的两个相邻元素必定有一个相邻元素与该元素差值为1。否则的话就不符合栈的结构。因为如果第一个元素为3的话，那么就是先入栈 1，2，3，然后出栈。那么无论怎么出栈，第二个元素都不可能为1。2, 4 都有可能，如果还不明白可以画图再想想。
D：1，2，3，先入栈；然后出栈3，栈中余2，1；再入栈 4，然后出栈 4，栈中余2，1；然后将栈中元素全部出栈。得到结果为：3, 4, 2, 1
2. 栈的结构
栈一般可以使用 数组或链表 实现。让我们分析一下使用这两种方法实现，栈的结构分别是什么样的。
在分析之前，我们要明确的一点是，栈只对 栈顶 的元素进行操作。
数组：
对于数组(顺序表)而言，最方便的就是尾插和尾删，所以我们将 顺序表的尾部 当做 栈顶。顺序表的头部 则当做 栈底，因为对于顺序表，头部的删除需要挪动大量数据。
链表：
对于链表而言，尤其是 单链表，尾部的插入删除是很麻烦的。但是 单链表 的头插和头删就很方便，所以可以把 单链表的头部 作为栈顶，单链表的尾部 作为 栈底。
如果对于双向链表而言，那么就是随便选了，毕竟双向链表无论哪头插入删除数据都很方便。
抉择：
那么对于 顺序栈 和 链式栈 ，那个更加好呢？那必定是 顺序栈，因为使用顺序栈的 尾插尾删非常方便， 且 cpu缓存利用率也更高。而且对于顺序栈实现起来相对简单，所以我们接下来就实现 顺序栈 。
3. 栈的实现
3.1 结构设计
我们既然是实现 顺序栈，那么它的结构肯定就和 顺序表 差不多：
typedef struct Stack { STDatatype* a; // 指向动态开辟的数组 int capacity; // 栈的容量 int top; // 标识 栈顶的下一个位置的下标 或 栈顶的下标 }ST;
这里的 top 我们需要好好理解一下。当top的初始值不同时，top可以表示 栈顶的下一个位置的下标 或 栈顶下标。
- 当
top = 0，top表示栈顶的下一个位置的下标： 
top 初始值为 0，那么第一次 压栈 就是在0下标插入元素。压栈后，top++。那么当 最后一次压栈后，元素被压在栈顶，那么top 最后的位置就是栈顶的下一个元素的下标处。此时，top就是栈中元素的个数。
- 当
top = -1，top表示栈顶的下标：
top 初始值为 -1，那么需要先 ++top，再压栈。否则会越界。当 最后一次压栈时，为先 ++top 再压栈，top最后的位置就是栈顶的下标处。
这个需要理清楚，否则实现判空、计算大小等接口函数的时候会引起错误。
3.2 接口总览
由于 栈的结构 和 操作规则，栈的接口相对来说比较少，且比较简单：
void StackInit(ST* ps); // 初始化 void StackDestroy(ST* ps); // 销毁 void StackPush(ST* ps, STDatatype x); // 压栈 void StackPop(ST* ps); // 出栈 STDatatype StackTop(ST* ps); // 取栈顶元素 bool StackEmpty(ST* ps); // 判空 int StackSize(ST* ps); // 计算栈的大小
3.3 初始化
我们实现的是顺序栈，那么就和顺序表一样，需要创建结构体变量，传结构体的地址，进行初始化。
在初始化的时候就给栈开上四个单位的空间，并且将起始容量设定为4。
注意了我们这里设定的 top = 0，那么表示 top 为栈顶的下一个位置的下标。
void StackInit(ST* ps) { // 结构体一定不为空，所以需要断言 assert(ps); ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4); if (ps->a == NULL) { perror("malloc fail"); exit(-1); } ps->capacity = 4; ps->top = 0; }
3.4 销毁
对于栈的销毁，那么我们就只需要释放动态开辟的空间，将指针置空。并将 capacity 和 top 两个变量置 0即可。
void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
3.5 判断栈是否为空
我们起初设定 top = 0，所以判断栈是否为空，那么只需要看 top 是否为0就可以了。如果为0，返回真 ；不为0，返回假。
bool StackEmpty(ST* ps) { assert(ps); // 如果 ps->top == 0，返回真 // 如果 ps->top !=0，返回假 return ps->top == 0; }
3.6 压栈
在压栈之前，需要保证空间足够，所以需要先检查容量，如果 不够，需要扩容，扩容成功后在考虑压栈的步骤。
我们设定 top 的初始值为 0。那么说明我们入栈的步骤为，先将元素放入，再让 top++。
void StackPush(ST* ps, STDatatype x) { assert(ps); // 检查容量 if (ps->top == ps->capacity) { STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } // 插入元素 // top 为栈顶的下一个元素 // 先插入再 ++ ps->a[ps->top++] = x; }
3.7 出栈
如果栈中没有元素则不能出栈。所以我们需要调用 StackEmpty 判断是否为空，如果栈空(!StackEmpty(ps)为假)，则断言报错。
出栈的操作和顺序表的尾删操作步骤相似，直接将top--即可。
void StackPop(ST* ps) { assert(ps); // 如果栈空，则不能删除 assert(!StackEmpty(ps)); ps->top--; }
3.8 取栈顶元素
由于我们 top 初值设定为 0，top为栈顶的下一个位置的下标，那么 top - 1 就是栈顶的下标，直接返回即可。
但是请注意：当栈为空时，无法取元素，所以需要判断一下。
STDatatype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }
3.9 计算栈的大小
如果一开始top = 0，那么栈的大小就直接是最后 top 的值。也非常简单~
int StackSize(ST* ps) { assert(ps); return ps->top; }
4. 完整代码
Stack.h
#pragma once #include <stdbool.h> #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int STDatatype; typedef struct Stack { STDatatype* a; int capacity; int top; // 初始为0，表示栈顶位置下一个位置下标 // 初始为-1，表示栈顶位置的下标 }ST; void StackInit(ST* ps); void StackDestroy(ST* ps); void StackPush(ST* ps, STDatatype x); void StackPop(ST* ps); STDatatype StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps);
Stack.c
这里我将 top = 0 和 top = -1 的方案都写了一遍，注释部分为 top = 0，未注释部分为 top = -1：
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" // top 为栈顶的下一个元素 //void StackInit(ST* ps) //{ // // 结构体一定不为空 // assert(ps); // // ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4); // if (ps->a == NULL) // { // perror("malloc fail"); // exit(-1); // } // ps->capacity = 4; // ps->top = 0; //} // //void StackDestroy(ST* ps) //{ // assert(ps); // // free(ps->a); // ps->a = NULL; // ps->capacity = ps->top = 0; //} // //void StackPush(ST* ps, STDatatype x) //{ // assert(ps); // // // 检查容量 // if (ps->top == ps->capacity) // { // STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2); // if (tmp == NULL) // { // perror("realloc fail"); // exit(-1); // } // ps->a = tmp; // ps->capacity *= 2; // } // // 插入元素 // // top 为栈顶的下一个元素 // // 先插入再 ++ // ps->a[ps->top++] = x; //} // //void StackPop(ST* ps) //{ // assert(ps); // // // 如果栈空，则不能删除 // assert(!StackEmpty(ps)); // ps->top--; //} // //STDatatype StackTop(ST* ps) //{ // assert(ps); // // assert(!StackEmpty(ps)); // // return ps->a[ps->top - 1]; //} // //bool StackEmpty(ST* ps) //{ // assert(ps); // // return ps->top == 0; //} // //int StackSize(ST* ps) //{ // assert(ps); // // return ps->top; //} // top 为栈顶 初识值为 -1 void StackInit(ST* ps) { // 结构体一定不为空 assert(ps); ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4); if (ps->a == NULL) { perror("malloc fail"); exit(-1); } ps->capacity = 4; ps->top = -1; } void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDatatype x) { assert(ps); // 检查容量 // 此时 top 一开始为 -1，不能表示栈中元素的数目 // top + 1 才是正确的 if (ps->top + 1 == ps->capacity) { STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } // 插入元素 // top 为栈顶元素 // 先 ++ 再插入 ps->a[++ps->top] = x; } void StackPop(ST* ps) { assert(ps); // 如果栈空，则不能删除 assert(!StackEmpty(ps)); ps->top--; } STDatatype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == -1; } int StackSize(ST* ps) { assert(ps); return ps->top + 1; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" void TestST1() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); StackPop(&st); StackPop(&st); StackPop(&st); StackPop(&st); printf("%d\n", StackTop(&st)); } int main() { TestST1(); }
5. OJ题 —— 有效的括号
由于我们刚刚学习了栈，而栈实现也比较简单，那么我们就趁热打铁做上一道OJ吧！
链接：20. 有效的括号
描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例1：
输入：s = “()”
输出：true
示例2：
输入：s = “()[]{}”
输出：true
示例3：
输入：s = “(]”
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
思路：
既然这道题目出现在这篇博客中，那么一定是用 栈 来解决，而且这道题目的解题思路是十分符合 栈 的。
首先，我们先要实现一个栈，并创建变量和初始化。
题目要求 左括号 需要以正确的顺序闭合，且左右括号成对，那么我们可以遍历字符串 s。
遍历过程中让 左括号入栈，一旦遇到 右括号 便 取栈顶元素 和右括号匹配，并 出栈元素。
一旦匹配失败，便返回 false。如果匹配成功，则让 s++ 往后走。
当字符串遍历结束时，判断栈是否为空，如果栈空，则说明为有效的括号；如果栈非空，则说明有左括号没有匹配，那么返回假。(这里只需要返回栈是否为空的值即可)
但是也有一些 易错情况，比如字符串遍历结束，栈中仍有元素：
只有右括号，无左括号，栈空，取元素时越界访问：
注：只有右括号时为提前返回状况。提前返回需要注意栈的销毁，否则会内存泄漏 ！！！
代码：
typedef int STDatatype; typedef struct Stack { STDatatype* a; int capacity; int top; // 初始为0，表示栈顶位置下一个位置下标 }ST; void StackInit(ST* ps); void StackDestroy(ST* ps); void StackPush(ST* ps, STDatatype x); void StackPop(ST* ps); STDatatype StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps); void StackInit(ST* ps) { // 结构体一定不为空 assert(ps); ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4); if (ps->a == NULL) { perror("malloc fail"); exit(-1); } ps->capacity = 4; ps->top = 0; } void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDatatype x) { assert(ps); // 检查容量 if (ps->top == ps->capacity) { STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } // 插入元素 // top 为栈顶的下一个元素 // 先插入再 ++ ps->a[ps->top++] = x; } void StackPop(ST* ps) { assert(ps); // 如果栈空，则不能删除 assert(!StackEmpty(ps)); ps->top--; } STDatatype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool isValid(char * s) { ST st; StackInit(&st); while (*s) { // 左括号 if (*s == '(' || *s == '[' || *s == '{') { // 入栈 StackPush(&st, *s); s++; } else { // 右括号匹配，栈为空 if (StackEmpty(&st)) { // 防止内存泄漏 StackDestroy(&st); return false; } // 取栈顶元素，并出栈 STDatatype top = StackTop(&st); StackPop(&st); if ((*s == ')' && top != '(') || (*s == ']' && top != '[') || (*s == '}' && top != '{')) { return false; } else { s++; } } } // 判断遍历结束后，栈是否为空 bool ans = StackEmpty(&st); // 销毁栈 StackDestroy(&st); return ans; }
