|
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和
删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈
插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之
成为新的栈顶元素
目录 前言 栈的概念 栈的结构 栈的实现 创建栈结构 初始化栈 销毁栈 入栈 出栈 获取栈顶元素 获取栈中有效元素个数 检测栈是否为空 总代码 Stack.h 文件 Stack.c 文件 Test.c 文件
前言
栈的概念 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行
数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后
进先出LIFO（Last In First Out）的原则。有点类似于**弹夹，后压进去的
子弹总是最先打出，除非枪坏了。 压栈：栈的插入操作叫做进栈/压栈/入栈。（入数据在栈顶） 出栈：栈的删除操作叫做出栈。（出数据也在栈顶） 注意：
1、函数调用也有栈，这两个栈有区别吗？
当然有区别。函数调用会调用栈帧，内存里头也有一个栈，程序运行起来时要执
行函数，函数里头的局部变量、参数、返回值等等都要存在函数栈帧里头。
这两个栈没有任何关联，一个是数据结构中的栈。另一个是操作系统中内存划分
的一个区域，叫做栈，用来函数调用时，建立栈帧。虽然本质上没有任何关联，
但都符合后进先出的规则。
2、假设入栈顺序为：1 2 3 4，那么出栈顺序一定为：4 3 2 1 吗？
当然不是。虽说规则上明确后进先出，可这是相对而言的，如果说它每进一个再
出一个，然后再继续压栈，那不同样符合后进先出的规则吗。就如同上例，你说
它出栈顺序为1 2 3 4 都不足为奇，每进一个出一个再进，同样符合规则。类似
的入栈两个再出再进再出也是可以的，好比如2 1 4 3。
栈的结构
栈的实现
创建栈结构 Stack.h 文件：
//创建栈结构 typedef int STDataType; typedef struct Stack { STDataType* a; //存储数据 int top; //栈顶的位置 int capacity; //容量 }ST;
初始化栈 思想：
初始化还是相对比较简单的，学了之前的顺序表，初始化栈就很轻松了
Stack.h 文件：
//初始化栈 void StackInit(ST* ps); Stack.c 文件：
//初始化栈 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } 注意：
这里初始化的时候将top置为0是有意图的。首先，由上文创建栈结构时已经标注
了，top是用来记录栈顶的位置，既然是栈顶的位置，那当top初始化为0时，我
们可以直接将数据放入栈中，随后top++，但是当top初始化为-1时，top首先要
++才能放入数据，因为数据不可能在负数不属于栈的位置上放入。下图演示过程
：
本文以 top = 0 示例
销毁栈 思想：
动态开辟的内存空间一定要释放，free置空即可，并把其余数据置0。
Stack.h 文件：
//销毁栈 void StackDestory(ST* ps); Stack.c 文件：
//销毁栈 void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; }
入栈 思路：
前文已经强调了top初始化为0，那么理应直接压入数据，并把top++，不过在这
之前，得判断空间是否够，当top=capacity的时候，栈就满了，那么就需要
realloc扩容。
Stack.h 文件：
//压栈 void StackPush(ST* ps, STDataType x); Stack.c 文件：
//压栈 void StackPush(ST* ps, STDataType x) { assert(ps); //如果栈满了，考虑扩容 if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //
检测容量 ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof
(STDataType)); if (ps->a == NULL) { printf("realloc fail\n"); exit(-1); } ps->capacity = newcapacity; //更新容量 } ps->a[ps->top] = x;//将数据压进去 ps->top++;//栈顶上移 }
出栈 思路：
在你出栈之前，要确保top不为空，而top不为空的条件就是top>0，所以还要断
言top>0，随后，直接将栈顶位置下移--即可。跟顺序表的思想大同小异。
Stack.h 文件：
//出栈 void StackPop(ST* ps); Stack.c 文件：
//出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; }
获取栈顶元素 思路：
首先要搞清楚谁才是栈顶元素，是top位置还是top-1位置？很显然是top-1的位
置才是栈顶元素，因为在前文初始化的时候已经明确指出top为0，当时压栈时直
接放入数据的，此时第一个数据下标为0，随后++top再压入其它数据，由此可见
，栈顶元素即下标top-1的位置。
Stack.h 文件：
//访问栈顶数据 STDataType StackTop(ST* ps); Stack.c 文件：
//访问栈顶数据 STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素 }
获取栈中有效元素个数 思想：
上文讲到下标top-1才是栈顶元素，那么是不是说总共就是top-1个元素呢？当然
不是，这里跟数组下标一样的思想，元素个数应该就是top个，直接返回即可。
Stack.h 文件：
//有效元素个数 int StackSize(ST* ps); Stack.c 文件：
//有效元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; }
检测栈是否为空 思路：
当top的值为0时即为空，return直接返回即可
Stack.h 文件：
//判空 bool StackEmpty(ST* ps); Stack.c 文件：
//判空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; //如果top为0，那么就为真，即返回 } Test.c 文件：
void TestStack() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); StackDestory(&st); } 效果如下：
总代码
Stack.h 文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h>
//创建栈结构 typedef int STDataType; typedef struct Stack { STDataType* a; //存储数据 int top; //栈顶的位置 int capacity; //容量 }ST;
//初始化栈 void StackInit(ST* ps);
//销毁栈 void StackDestory(ST* ps);
//压栈 void StackPush(ST* ps, STDataType x);
//出栈 void StackPop(ST* ps);
//判空 bool StackEmpty(ST* ps);
//访问栈顶数据 STDataType StackTop(ST* ps);
//有效元素个数 int StackSize(ST* ps);
Stack.c 文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" //初始化栈 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
//销毁栈 void StackDestory(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) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //
检测容量 ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof
(STDataType)); if (ps->a == NULL) { printf("realloc fail\n"); exit(-1); } ps->capacity = newcapacity; //更新容量 } ps->a[ps->top] = x;//将数据压进去 ps->top++;//栈顶上移 } //出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; }
//判空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; //如果top为0，那么就为真，即返回 }
//访问栈顶数据 STDataType StackTop(ST* ps) { assert(ps); return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素 }
//有效元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; }
Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" void TestStack() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n"); StackDestory(&st); } int main() { TestStack(); return 0; }
| 
楼主
