一.了解项目功能
在本次项目中我们的目标是实现一个顺序栈:
该顺序栈使用动态内存分配空间,可以用来存储任意数量的同类型数据.
顺序栈结构体需要包含三个要素:存放数据的数组arr,栈顶元素下标top,栈容量capacity.
顺序栈程序提供的功能有:
- 顺序栈的初始化
- 顺序栈的销毁
- 顺序栈的入栈
- 顺序栈的出栈
- 顺序栈的长度
- 顺序栈判空
- 顺序栈取栈顶元素
二.项目功能演示
要编写一个顺序栈项目，首先要明确我们想要达到的效果是什么样，下面我将用vs2022编译器来为大家演示一下顺序栈程序运行时的样子：
三.逐步实现项目功能模块及其逻辑详解
通过第二部分对项目功能的介绍，我们已经对顺序栈的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！
！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。
1.实现顺序栈程序菜单
菜单部分的逻辑比较简单，就是利用C语言printf函数打印出这个菜单界面即可。但要注意菜单的标序要和后续switch...case语句的分支相应,以免导致后续执行语句错乱的问题.基础问题就不过多赘述了，代码如下：
该部分功能实现代码如下:
void STMenu() { printf("**********************************\n"); printf("******请选择要进行的操作 ******\n"); printf("******1.顺序栈入栈 ******\n"); printf("******2.顺序栈出栈 ******\n"); printf("******3.取栈顶元素 ******\n"); printf("******4.判断栈空 ******\n"); printf("******5.查询当前栈长 ******\n"); printf("******6.清空顺序栈 ******\n"); printf("******7.销毁顺序栈 ******\n"); printf("******0.退出顺序栈程序 ******\n"); printf("**********************************\n"); printf("请选择:>"); }
2.实现顺序栈程序功能可循环使用
由于我们要实现顺序栈的功能可以反复使用的逻辑，且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.
该部分功能实现代码如下:
int main() { ST st; STInit(&st); int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件 do //使用do...while实现 { STMenu(); scanf("%d", &swi); switch (swi) { case 0: STDestroy(&st); printf("您已退出程序:>\n"); // 释放链表内存 break; case 1: printf("请输入要入栈的数据:>"); STDataType pushback_data = 0; scanf("%d", &pushback_data); STPush(&st, pushback_data); printf("已成功入栈:>\n"); break; case 2: printf("栈顶元素%d已成功出栈\n", STTop(&st)); STPop(&st); break; case 3: printf("栈顶元素为:"); STDataType sttop = STTop(&st); printf("%d\n", sttop); break; case 4: if (!STEmpty(&st)) { printf("当前栈不为空\n"); } else { printf("当前栈为空栈\n"); } break; case 5: printf("当前栈长为:"); int stsize = STSize(&st); printf("%d\n", stsize); break; case 6: STDestroy(&st); STInit(&st); printf("顺序栈已清空:>\n"); break; case 7: STDestroy(&st); printf("顺序栈已销毁:>\n"); break; default: printf("输入错误,请重新输入\n"); break; } } while (swi); return 0; }
3.创建顺序栈
创建顺序栈成员的结构体应该包括:存放数据的数组arr,栈顶元素下标top,栈容量capacity.
因此我们创建Stack结构体类型时应由一个数组及两个整型组成.
这里的第9行使用的typedef类定义的作用是方便我们后续在使用顺序栈时对存储的数据类型做更改,比如后续我们不想存储int类型数据了,就可以很方便的在这里对数组类型做更改.比如改成char类型,或者double类型,甚至改成任意自己构造的结构类型.
综上,该部分代码如下:
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int STDataType; typedef struct Stack { int *arr; int top; int capacity; }ST;
4.初始化顺序栈
初始化顺序栈的逻辑和初始化顺序表一样,我们在初始化时为栈开辟4个数据类型的数组空间,然后将顺序栈的容量改为4,栈顶置为0即可.
该部分的功能实现代码如下:
void STInit(ST* ps) { assert(ps); ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->arr == NULL) { perror("malloc fail::\n"); return; } ps->capacity = 4; ps->top = 0; //top表示栈顶元素的下一个 //top指向栈顶元素的话,top给-1 }
5.顺序栈的入栈
顺序栈在入栈时,需要先判断一下栈内元素是否已满,如果满了则需要给栈扩容.(如下代码5-18行均是在执行顺序栈查满扩容逻辑)
如果没满则将新元素赋值给栈顶指针top,再将top++,使其始终指向栈顶的下一个元素位置.
该部分的功能实现代码如下:
void STPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity)//扩容 { STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail::\n"); return; } ps->arr = tmp; ps->capacity *= 2; } ps->arr[ps->top] = x; ps->top++; }
6.顺序栈的出栈
顺序栈的出栈就相当于顺序表的尾删,那么我们同顺序表一样移动栈顶下标位置即可.
顺序表尾删示意图:
该部分的功能实现代码如下:
void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; }
7.顺序栈取栈顶元素
根据我们之前的设定,栈为空时top=0:
那么当栈中进入一个元素时,top++后top=1,而栈顶元素a1的下标等于0,所以我们的top设计其实是指向栈顶元素的下一个位置的:
因此在取栈顶函数中,我们要返回的栈顶数组下标应该是top-1.
该部分的功能实现代码如下:
STDataType STTop(ST* ps) { assert(ps); assert(!STEmpty(ps)); return ps->arr[ps->top - 1]; }
8.顺序栈的长度
因为top指向的是栈顶元素的下一个位置,因此top的大小正好是栈的长度,所以求栈长函数我们对ps断言后可以直接返回top.
该部分的功能实现代码如下:
int STSize(ST* ps) { assert(ps); return ps->top; }
9.顺序栈的判空
顺序栈判空的逻辑是:如果栈为空返回true(真),否则返回false(假).
因此我们还是拿top来判断,如果top=0,会return true,意味着栈为空.
否则会return false,意味着栈不为空.
该部分的功能实现代码如下:
bool STEmpty(ST* ps)//判空,为空则真 { assert(ps); return ps->top==0; }
10.顺序栈的销毁
当我们使用完顺序栈想要退出程序时,就应该将之前动态开辟的内存释放掉,还给操作系统.即销毁顺序栈.
我们使用free()函数释放掉之前动态开辟的数组arr,然后将arr置为空指针,最后将top,capacity的值置为0即可.
该部分的功能实现代码如下:
void STDestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->top = 0; ps->capacity = 0; }
四.项目完整代码
我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:
test.c文件
#include"Stack.h" int main() { ST st; STInit(&st); int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件 do //使用do...while实现 { STMenu(); scanf("%d", &swi); switch (swi) { case 0: STDestroy(&st); printf("您已退出程序:>\n"); // 释放链表内存 break; case 1: printf("请输入要入栈的数据:>"); STDataType pushback_data = 0; scanf("%d", &pushback_data); STPush(&st, pushback_data); printf("已成功入栈:>\n"); break; case 2: printf("栈顶元素%d已成功出栈\n", STTop(&st)); STPop(&st); break; case 3: printf("栈顶元素为:"); STDataType sttop = STTop(&st); printf("%d\n", sttop); break; case 4: if (!STEmpty(&st)) { printf("当前栈不为空\n"); } else { printf("当前栈为空栈\n"); } break; case 5: printf("当前栈长为:"); int stsize = STSize(&st); printf("%d\n", stsize); break; case 6: STDestroy(&st); STInit(&st); printf("顺序栈已清空:>\n"); break; case 7: STDestroy(&st); printf("顺序栈已销毁:>\n"); break; default: printf("输入错误,请重新输入\n"); break; } } while (swi); return 0; }
Stack.c 文件
#include"Stack.h" void STInit(ST* ps) { assert(ps); ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->arr == NULL) { perror("malloc fail::\n"); return; } ps->capacity = 4; ps->top = 0; //top表示栈顶元素的下一个 //top指向栈顶元素的话,top给-1 } void STDestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = 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->arr,sizeof(STDataType)*ps->capacity*2); if (tmp == NULL) { perror("realloc fail::\n"); return; } ps->arr = tmp; ps->capacity *= 2; } ps->arr[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->arr[ps->top - 1]; } void STMenu() { printf("**********************************\n"); printf("******请选择要进行的操作 ******\n"); printf("******1.顺序栈入栈 ******\n"); printf("******2.顺序栈出栈 ******\n"); printf("******3.取栈顶元素 ******\n"); printf("******4.判断栈空 ******\n"); printf("******5.查询当前栈长 ******\n"); printf("******6.清空顺序栈 ******\n"); printf("******7.销毁顺序栈 ******\n"); printf("******0.退出顺序栈程序 ******\n"); printf("**********************************\n"); printf("请选择:>"); }
Stack.h文件
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int STDataType; typedef struct Stack { int *arr; int top; int capacity; }ST; void STInit(ST* ps); void STDestroy(ST* ps); void STPush(ST* ps, STDataType x); void STPop(ST* ps); int STSize(ST* ps); bool STEmpty(ST* ps);//判空,为空则真 STDataType STTop(ST* ps); void STMenu();
结语
希望这篇顺序栈的C语言实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
数据结构栈与队列篇思维导图:
