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

一、什么是顺序栈

1.栈

（1）栈是限定仅在表尾进行插入或删除操作的线性表。也就是说，栈只能在一段进行插入和删除操作。

（2）特点：先进后出

（3）对栈来说，插入和删除的一端（表尾端）称为栈顶；相应地，另一端（表头端）成为栈底。不含元素的空表称为空栈。

（4）栈的插入操作，一般称为入栈/压栈/进栈；栈的删除操作，一般称为出栈/弹栈。

2.顺序栈

顺序栈，即栈的顺序存储结构。是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设栈顶指针top指示栈顶元素在顺序栈中的位置。

其思路与顺序表类似：

数据结构——线性表的顺序存储结构及函数实现（C语言）https://blog.csdn.net/wy_05136/article/details/159045575?spm=1001.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; }