数据结构之栈
1.栈的概念
- 栈：仅在表尾进行插入和删除操作的线性表，栈的数据遵守后进先出LIFO(Last In Firist Out)原则.
- 栈顶：允许插入和删除的一端
- 栈底：另一端
- 栈的插入操作：叫做进栈，也称做压栈，入栈
- 栈的删除操作：叫做出栈
- 特殊点：限制了线性表的插入和删除位置，始终只在栈顶进行，栈底是固定的，最先进栈的只能在栈底
小思考：最先进栈的是不是只能最后出栈？
不一定
例：要求，1、2、3要按顺序进栈，那么会有几种出栈次序呢？
1.1进 1出，2进 2出，3进 3出 顺序 1 2 3
2.1进 1出， 2进 3进 3出 2出 1 3 2
3.1进 2进 2出 1出，3进 3出 2 1 3
4.1进 2进 2出 3进 3出 1出 2 3 1
5.1进 2进 3进 3出 2出 1出 3 2 1
那么可能是 3 1 2吗
不可能
why:既然3都进栈了，且其他两个数没有出栈，那么2一定在1之前出栈
2.顺序栈
与顺序表相似
//Test.c#pragma one#include\"Stack.h\"int main(){ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);while (!STEmpty(&st)){printf(\"%d \",STTop(&st));STPop(&st);}STDestroty(&st);return 0;}//Stack.h#include#include#include#includetypedef int STDataType;typedef struct Stack{int* a;int top;int capacity;}ST;void STInit(ST*ps); void STDestroty(ST* ps);void STPush(ST* ps,STDataType x);void STPop(ST* ps);int STSize(ST* ps);bool STEmpty(ST* ps);STDataType STTop(ST* ps);
//Stack.c#include\"Stack.h\"void STInit(ST* ps){assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror(\"malloc fail\");return;}ps->capacity = 4;ps->top = 0;//代表top是栈顶元素的下一个位置//ps->top = -1;//代表top是栈顶元素}void STDestroty(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;}void STPush(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\");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;}void STPop(ST* ps){assert(ps);assert(!STEmpty(ps));ps->top--;}int STSize(ST* ps){assert(ps);return ps->top;}bool STEmpty(ST* ps){assert(ps);return ps->top == 0;}STDataType STTop(ST* ps){assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];}小思考：既然有了用数组或者顺序表、链表直接来实现功能，为什么还要引入栈呢？
答：栈这一数据结构的引入，极大地简化了程序设计工作。它巧妙地划分出不同的关注层次，让开发者能够从复杂的问题情境中抽离出来，将思考范围精准聚焦于问题解决的核心部分，从而更高效地攻克难题。
本文部分内容总结自《大话数据结构》
