一、栈（stack）
栈的概念：
① 栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。
② 进行数据插入的删除和操作的一端，称为栈顶 。另一端则称为 栈底 。
③ 栈中的元素遵守后进先出的原则，即 LIFO原则（Last In First Out）。
压栈：栈的插入操作叫做 进栈 / 压栈 / 入栈 ，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
两道栈的选择题：
1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E 依次入栈，
然后再依次出栈，则元素出栈的顺序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ）。
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
答案:
1.A
2.c
栈的结构：
数组栈和链式栈
实现栈无非就两种结构：数组结构 和 链式结构，两种结构都可以实现。
数组栈和链式栈哪种结构更好？
相对而言数组的结构实现更优，尾插尾删的效率高，缓存利用率高，它的唯一缺点只是增容，
但是增容1次扩2倍对栈来说本身就比较合理，是无伤大雅的。而链式栈虽然不会空间浪费，
用一个 malloc 申请一个，但是链式栈存在一个致命的缺点：单链表不好出数据，
必须要实现双向链表，否则尾上删除数据将会异常麻烦。
如果硬要使用链式栈：
① 如果用尾做栈顶，尾插尾删，要设计成双向链表，否则删数据效率低。
② 如果用头做栈顶，头插头删，就可以设计成单链表。
本章栈的实现将采用数组结构
二、栈的定义
（数组栈和顺序表定义差不多）
静态栈
简单介绍下静态栈：
typedef char StackDataType; #define N 10 typedef struct Stack { StackDataType array[N]; //数组 int top; //栈顶 } Stack;
解读：N 给多了浪费给少了又不够用，所以静态栈在实际中是不实用的。静态栈满了就不能扩大了，
而动态栈是 malloc 出来的，不够了可以 realloc 扩容。虽然不实用，但是我们也得认识它，
知道有这么一个东西。
动态栈
本章将采用动态栈实现
typedef int StackDataType; typedef struct Stack { StackDataType* array; //数组 int top; //栈顶 int capacity; //容量 } Stack;
三、栈的实现（完整代码）
实现了顺序表和链表，栈的实现很简单，直接放完整代码了
Stack.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int StackDataType; typedef struct Stack { StackDataType* array; //数组 int top; //栈顶 int capacity; //容量 } Stack; void StackInit(Stack* ps);//初始化 void StackDestroy(Stack* ps);//销毁 void StackPush(Stack* ps, StackDataType x);//进栈 bool StackEmpty(Stack* ps);//判断栈是否为空 void StackPop(Stack* ps);// 出栈 StackDataType StackTop(Stack* ps);//返回栈顶数据 int StackSize(Stack* ps);//返回栈的大小
Stack.c
#include "Stack.h" void StackInit(Stack* ps)//初始化 { assert(ps); ps->array = NULL; ps->top = 0; // ps->top = -1 ps->capacity = 0; } void StackDestroy(Stack* ps)//销毁 { assert(ps); free(ps->array); ps->array = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps, StackDataType x)//进栈 { assert(ps); if (ps->top == ps->capacity) { int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2; StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity); if (tmp_arr == NULL) { printf("realloc failed!\n"); exit(-1); } // 更新 ps->array = tmp_arr; ps->capacity = new_capacity; } ps->array[ps->top] = x;// 填入数据 ps->top++; } bool StackEmpty(Stack* ps)//判断栈是否为空 { assert(ps); return ps->top == 0; //等于0就是空，就是真 } void StackPop(Stack* ps)// 出栈 { assert(ps); //assert(ps->top > 0); //防止top为空 assert(!StackEmpty(ps)); ps->top--;//--不让访问数组最后一个元素就行 } StackDataType StackTop(Stack* ps)//返回栈顶数据 { assert(ps); //assert(ps->top > 0); //防止top为空 assert(!StackEmpty(ps)); return ps->array[ps->top - 1]; } int StackSize(Stack* ps) //计算栈的大小 { assert(ps); return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size }
Test.c
#include "Stack.h" void TestStack1() { Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 4); StackPop(&st); StackPop(&st); StackPop(&st); StackPop(&st); //StackPop(&st); printf("%d", StackTop(&st)); StackDestroy(&st); } void TestStack2() { // 入栈：1 2 3 4 Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); // 出栈：4 3 2 1 while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } StackDestroy(&st); } void TestStack3() { // 入栈：1 2 3 4 Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); // 提前出栈：4 3 printf("%d ", StackTop(&st)); StackPop(&st); printf("%d ", StackTop(&st)); StackPop(&st); // 入栈：5 6 StackPush(&st, 5); StackPush(&st, 6); // 出栈：6 5 2 1 while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } StackDestroy(&st); } int main() { //TestStack1(); //TestStack2(); TestStack3(); return 0; }
四、一道栈的OJ题：
力扣链接：20. 有效的括号
难度简单
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
- 1 <= s.length <= 104
- s 仅由括号 '()[]{}' 组成
bool isValid(char * s){ }
解析代码：
这道题用C++写就很简单，用C语言写就需要创建一个栈。（可以用数组什么的，但不好）
我们刚写了一个栈，直接把Stack.h和Stack.c复制粘贴过去,把头文件删掉，
再把typedef int StackDataType; 改成typedef char StackDataType;
typedef char StackDataType; typedef struct Stack { StackDataType* array; //数组 int top; //栈顶 int capacity; //容量 } Stack; void StackInit(Stack* ps); void StackDestroy(Stack* ps); void StackPush(Stack* ps, StackDataType x); bool StackEmpty(Stack* ps); void StackPop(Stack* ps); StackDataType StackTop(Stack* ps); int StackSize(Stack* ps); void StackInit(Stack* ps)//初始化 { assert(ps); ps->array = NULL; ps->top = 0; // ps->top = -1 ps->capacity = 0; } void StackDestroy(Stack* ps)//销毁 { assert(ps); free(ps->array); ps->array = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps, StackDataType x)//进栈 { assert(ps); if (ps->top == ps->capacity) { int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2; StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity); if (tmp_arr == NULL) { printf("realloc failed!\n"); exit(-1); } // 更新 ps->array = tmp_arr; ps->capacity = new_capacity; } ps->array[ps->top] = x;// 填入数据 ps->top++; } bool StackEmpty(Stack* ps)//判断栈是否为空 { assert(ps); return ps->top == 0; //等于0就是空，就是真 } void StackPop(Stack* ps)// 出栈 { assert(ps); //assert(ps->top > 0); //防止top为空 assert(!StackEmpty(ps)); ps->top--; } StackDataType StackTop(Stack* ps)//返回栈顶数据 { assert(ps); //assert(ps->top > 0); //防止top为空 assert(!StackEmpty(ps)); return ps->array[ps->top - 1]; } int StackSize(Stack* ps) //计算栈的大小 { assert(ps); return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size } bool isValid(char* s) { Stack st; StackInit(&st); while (*s) { if ((*s == '(') || (*s == '[') || (*s == '{')) { StackPush(&st, *s); } else { //栈是空，且遇到右括号了，栈里面没有左括号 if (StackEmpty(&st)) { StackDestroy(&st); return false; } StackDataType top = StackTop(&st); StackPop(&st); if ((top == '(' && *s != ')') || (top == '[' && *s != ']') || (top == '{' && *s != '}')) { StackDestroy(&st); return false; } } s++; } //如果栈不是空，说明还有左括号没出完，不合题意 //此时StackEmpty返回false，相反，栈是空，返回true bool ret = StackEmpty(&st); StackDestroy(&st); return ret; }
本篇完。
下一篇：队列
