数据结构——顺序栈及函数实现（C语言）

一、什么是顺序栈1.栈1栈是限定仅在表尾进行插入或删除操作的线性表。也就是说栈只能在一段进行插入和删除操作。2特点先进后出3对栈来说插入和删除的一端表尾端称为栈顶相应地另一端表头端成为栈底。不含元素的空表称为空栈。4栈的插入操作一般称为入栈/压栈/进栈栈的删除操作一般称为出栈/弹栈。2.顺序栈顺序栈即栈的顺序存储结构。是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素同时附设栈顶指针top指示栈顶元素在顺序栈中的位置。其思路与顺序表类似数据结构——线性表的顺序存储结构及函数实现C语言https://blog.csdn.net/wy_05136/article/details/159045575?spm1001.2014.3001.5501二、顺序栈结构体设计及函数实现C语言一顺序栈的结构体设计1.一组地址连续的存储单元通常用数组依次存放自栈底到栈顶的数据元素2.栈顶指针top指示栈顶元素的下一个存储位置也能表示当前有效元素的个数3.栈当前可使用的最大容量stacksize#include cassert #include corecrt_malloc.h #include cstdlib #include stdio.h #define STACK_INIT_SIZE 10 //顺序表实现的栈 的初始大小 typedef int ElemType; //顺序栈的结构体设计 typedef struct SeqStack { //1.指针类型用来接收malloc的返回值 ElemType* base; //2.栈顶指针用来指向栈顶元素的下一个存储位置其实也能表示当前有效元素的个数 int top; //栈顶指针并不一定要用指针类型能起到相同作用即可 //3.当前总的空间大小用来扩容的 int stacksize; }SeqStack;二顺序栈的C语言函数实现1.初始化void Init_SeqStack(SeqStack* psq) { //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.动态分配栈的底层数组内存 psq-base (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (psq-base NULL) exit(EXIT_FAILURE); //内存分配失败 //2.栈顶指针为0表示栈为空 psq-top 0; //3.初始空间大小 psq-stacksize STACK_INIT_SIZE; }2.判满bool Full(SeqStack* psq) { //bool Full(const SeqStack* psq); 更合适 //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.若栈顶指针(有效元素个数) 空间大小说明栈已满返回true; // 否则返回false return psq-top psq-stacksize; }因为此函数无需对栈进行修改故而参数前加const更合适此处为了与其它函数统一所以未加。3.判空bool Empty(SeqStack* psq) { //bool Empty(const SeqStack* psq); 更合适 //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.若栈顶指针(有效元素个数) 0说明栈为空返回true; // 否则返回false return psq-top 0; }因为此函数无需对栈进行修改故而参数前加const更合适此处为了与其它函数统一所以未加。4.扩容void Increase(SeqStack* psq) { //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.将空间大小扩大为原来的2倍 ElemType* tmp (ElemType*)realloc(psq-base, psq-stacksize * sizeof(ElemType) * 2); //2.若扩容成功则更新指针和空间大小 if (tmp ! NULL) { psq-base tmp; psq-stacksize * 2; } }5.入栈bool Push(SeqStack* psq, ElemType val) { //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.判满如果满了就扩容 if (Full(psq)) Increase(psq); //2.直接给top下标的格子插入val值 psq-base[psq-top] val; //3.更新栈顶指针 psq-top; return true; }6.出栈bool Pop(SeqStack* psq) { //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.判空 assert(!Empty(psq)); //2.直接将top指针往前走一下 psq-top--; return true; }7.获取栈顶元素值ElemType Top(SeqStack* psq) { //ElemType Top(const SeqStack* psq); 更合适 //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.判断栈是否为空若为空则不存在栈顶元素 assert(!Empty(psq)); //2.直接返回栈顶元素的值 return psq-base[psq-top - 1]; }因为此函数无需对栈进行修改故而参数前加const更合适此处为了与其它函数统一所以未加。8.清空void Clear(SeqStack* psq) { //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.直接将栈顶指针设为0 psq-top 0; }9.销毁void Destroy(SeqStack* psq) { //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.释放内存 free(psq-base); psq-base NULL; //避免野指针 //2.重置状态 psq-top 0; psq-stacksize 0; }10.打印void Show(SeqStack* psq) { //void Show(const SeqStack* psq); 更合适 //0.断言:检查传入的指针是否为空 assert(psq ! NULL); //1.从栈底开始依次打印 for (int i 0; i psq-top; i) printf(%d , psq-base[i]); printf(\n); }因为此函数无需对栈进行修改故而参数前加const更合适此处为了与其它函数统一所以未加。11.主函数测试int main() { SeqStack stack; //初始化 Init_SeqStack(stack); //入栈判满 printf(入栈(栈不满的情况下):\n); Push(stack, 1); Push(stack, 2); Push(stack, 3); Show(stack); if (Full(stack)) printf(栈已满\n\n); else printf(栈未满\n\n); Push(stack, 4); Push(stack, 5); Push(stack, 6); Push(stack, 7); Push(stack, 8); Push(stack, 9); Push(stack, 10); Show(stack); if (Full(stack)) printf(栈已满\n\n); else printf(栈未满\n\n); printf(入栈(栈满的情况下):\n); Push(stack, 11); //函数中包含扩容函数 Show(stack); printf(\n); //出栈 printf(出栈:\n); Pop(stack); Show(stack); printf(\n); //获取栈顶元素值 printf(栈顶元素值为 %d\n, Top(stack)); printf(\n); //清空判空 Show(stack); if (Empty(stack)) printf(栈已空\n\n); else printf(栈未空\n\n); Clear(stack); if (Empty(stack)) printf(栈已空\n\n); else printf(栈未空\n\n); //销毁 Destroy(stack); return 0; }