👉栈的概念及结构👈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出 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.答案：B；解析：因为栈结构符合后进先出的原则，且1、2、3、4、5、A、B、C、D、E依次入栈，所以出栈顺序为E、D、C、B、A、5、4、3、2、1。
2.答案：C；解析：A 选项元素 1 入栈后出栈，元素 2、3、4 依次入栈后依次出栈；B 选项元素 1 入栈，元素 2 入栈后出栈，元素 3 入栈后出栈，元素 4 入栈后出栈，最后元素 1 出栈；D 选项元素 1、2、3 依次入栈，元素 3 出栈，元素 4 入栈后出栈，最后元素 2 、1 依次出栈。
👉栈的实现👈
栈的实现一般可以使用顺序表或者链表实现，相对而言顺序表的结构实现更优一些。因为顺序表在尾上插入数据的代价比较小。如果是链栈，一般需要进行头插或者头删操作，而顺序栈一般进行尾插和尾删操作，链表的操作比顺序表复杂，顺序表的尾插和尾删不需要搬移元素效率非常高，因此使用顺序结构实现栈更简单.。
注意：本篇博客所讲述的栈是数据结构里的栈，而不是操作系统里内存的栈区（大约8M）。这两者是有区别的，但它们都符合后进先出的原则。
栈可以用数组或者链表来实现，在这里博主采用数组的形式来实现。大家也可以尝试采用链表的形式来实现栈。
Stack.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> // ̬静态栈 //#define N 100 //typedef int STDataType; //struct Stack //{ // STDataType a[N]; // int top; //}; typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }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
#include "Stack.h" void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; } void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); // 扩容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } 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; }
初始化栈
1.对
ps进行断言2.
ps->a = NULL不指向任何空间3.
ps->top = ps->capacity = 04.注意：
ps->top = 0表示top为栈顶元素位置的下一个位置，其大小也表示栈中元素的个数；ps->top = -1表示top为栈顶元素的位置。
void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; }
销毁栈
1.释放a指向的空间free(ps->a)，并将a置为空ps->a = NULL
2.ps->top = ps->capacity = 0
void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
数据入栈
1.判断是否需要扩容。扩容分两种情况：1.容量为 0 时，先给四个空间；2.容量不为 0 时，容量扩大到两倍
2.数据入栈
ps->a[ps->top] = x，元素个数加一ps->top++
void StackPush(ST* ps, STDataType x) { assert(ps); // 扩容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; }
数据出栈
1.调用
StackEmpty函数判断栈是否为空2.数据出栈
--ps->top
void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; }
返回栈顶元素
1.调用
StackEmpty函数判断栈是否为空2.返回栈顶元素
return ps->a[ps->top - 1]
STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }
判断栈是否为空
因为
ps->top表示栈中元素的个数，所以返回ps->top == 0就能判断栈是否为空了
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
栈中元素的个数
直接返回元素个数
return ps->top
int StackSize(ST* ps) { assert(ps); return ps->top; }
Test.c
以下为栈函数接口的测试代码，大家可以参考一下。因为函数接口比较简单，所以就没有弄出多个函数来一一测试它们的功能。虽然栈的函数接口都很简单，但是我们也要通过函数接口来操作栈，而不能通过下图的方式。还要值得注意的是：打印栈中的数据是通过打印栈顶数据、Pop掉栈顶数据的方式来实现的。
原因就是我们并不知道人家的函数接口时怎么实现的。比如：栈的初始化有两种方式 top = 0 和 top = -1。
#include "Stack.h" // 解耦 -- 低耦合 高内聚 // 数据结构建议不要直接访问结构数据，一定要通过函数接口访问 void StackTest() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); printf("%d ", StackTop(&st)); StackPop(&st); printf("%d ", StackTop(&st)); StackPop(&st); StackPush(&st, 4); StackPush(&st, 5); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); StackDestroy(&st); } int main() { StackTest(); return 0; }
👉有效的括号👈
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 10^4
s 仅由括号 ‘()[]{}’ 组成
思路：这道题目可以使用上面实现的栈来解决。利用while循环变量字符串s，当遇到左括号，那么左括号入栈；如果遇到右括号，那么左括号出栈匹配。如果左括号和右括号不匹配或者栈里没有左括号了，就直接返回false。循环结束时，如果栈不为空，那么就说明说明栈中还有左括号没有和右括号匹配上。没有匹配上，就返回false。
typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }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 = NULL; ps->top = ps->capacity = 0; } void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); // 扩容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } 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); } else { // 遇到右括号了，但是栈为空，说明 // 没有左括号和右括号匹配了，返回false if(StackEmpty(&st)) { StackDestroy(&st); return false; } char top = StackTop(&st); StackPop(&st); // 左括号和右括号匹配不上 if((top == '(' && *s != ')') ||(top == '{' && *s != '}') ||(top == '[' && *s != ']')) { StackDestroy(&st); return false; } } s++; } // 如果栈不是空，说明栈中还有左括号没有和右括号匹配上 // 没有匹配，返回的是false bool flag = StackEmpty(&st); StackDestroy(&st); return flag; }
