C语言_数据结构总结5：顺序栈

纯C语言代码，不涉及C++

想了解链式栈的实现，欢迎查看这篇文章：C语言_数据结构总结6：链式栈-CSDN博客

这里分享插入一下个人觉得很有用的习惯：

1. 就是遇到代码哪里不理解的，你就问豆包，C知道，Kimi等等AI工具，比如在这栈中你不能理解为什么有时候要传一级指针有时候又不用，你就询问AI“在进栈操作中是否可以不传入指针变量，而是直接传入结构体变量”；

2. 还有就是自己的代码报错了，又或是自己觉得自己的代码存在某种问题，而自己又不能解决时，你就直接复制自己的代码问AI，让AI对以下代码进行点评，并返回改善后的代码。

前言

栈：是只允许在一端进行插入或删除操作的线性表。
栈顶：允许进行插入或删除的那一端
栈底：固定的，不允许进行插入或删除的那一端
栈的特性：后进先出
存储方式：1. 顺序存储（顺序栈） 2. 链式存储（链式栈）

在顺序栈的基本操作中，决定是传入一级指针还是只传入栈的变量，主要取决于操作是否需要修改栈的内部状态。
   1. 需要传入一级指针的情况
   当操作需要修改栈的内部状态，比如改变栈顶指针 top 的值或者修改栈中存储的数据时，就需要传入一级指针。
   这是因为在 C 语言里，函数参数传递是值传递，若直接传入栈的变量，函数内部对该变量的修改不会影响到原变量。
   而通过传入指针，函数可以直接访问和修改原变量所指向的内存。

2. 只需要传入栈的变量的情况
当操作不需要修改栈的内部状态，仅仅是读取栈的信息时，就可以只传入栈的变量。

以下是顺序栈实现
它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针top指示当前的栈顶元素的位置

0. 结构单元

#define MaxSize 50
typedef int ElemType;
typedef struct SqStack {
ElemType data[MaxSize]; //存放栈中元素
int top; //栈顶指针
}SqStack;

！注意 ：栈顶指针top,它不是实际意义上的指针变量，进行存放指针变量。这里说它是指针，意思是说，它指示了当前栈顶元素的位置，在第pos个位置。

1. 初始化

void InitSeqStack(SqStack* s) {s->top = -1;  //初始化栈顶的位置
}

这里设置初始栈顶指针s.top = -1,
栈空条件是s.top = -1;栈满条件是s.top = MaxSize - 1
则进栈时指针s.top+1,再将元素加入栈顶；出栈时先取出栈顶元素，后指针s.top - 1

但如果设置初始栈顶指针s.top = 0,
栈空条件是s.top = 0;栈满条件是s.top = MaxSize
则进栈时将元素加入栈顶,再指针s.top+1；出栈时先指针s.top - 1，后取出栈顶元素

2. 判空

int SqStackEmpty(SqStack s) {return s.top == -1;
}

3. 判满

int SqStackFull(SqStack s) {return s.top == MaxSize - 1;
}

4. 入栈

即：将元素加入到栈顶

int push(SqStack* s, ElemType value) {// 1. 判满if (SqStackFull(*s)){printf("栈满，无法入栈!\n");return -2;}// 2. 指针top + 1，再将值加入到栈顶s->top++;s->data[s->top] = value;return 0;  //入栈成功
}

5. 出栈

int pop(SqStack* s, ElemType* value) {//1. 判空if (SqStackEmpty(*s)){printf("栈空，无法有元素出栈!\n");return -1;}//2. 先取出栈顶元素，再指针top - 1*value = s->data[s->top];s->top--;return 0;  //出栈成功
}

6. 获取栈顶元素

int getTop(SqStack s,ElemType *value) {//1. 判空if (SqStackEmpty(s)){printf("栈空，无法有元素出栈!\n");return -1;}//2. 获取栈顶元素*value = s.data[s.top];return 0;  
}

7. 打印栈中元素

void printSqStack(SqStack s) {if (SqStackEmpty(s)){printf("栈空!\n");return;  //提前结束该函数}printf("栈中的元素（从栈底到栈顶）为: ");for (int i = 0; i <= s.top; i++) {printf("%d ", s.data[i]);}printf("\n");
}

8. 销毁

void destroySqStack(SqStack* s) {// 由于顺序栈使用的是静态数组，不需要显式释放内存// 只需要将栈顶指针置为 -1 表示栈为空s->top = -1;
}

9. 测试

int main() {SqStack s;InitSeqStack(&s);// 测试入栈操作push(&s, 11);push(&s, 22);push(&s, 33);printSqStack(s);  // 栈中的元素（从栈底到栈顶）为: 11 22 33// 获取栈顶元素ElemType value;if (getTop(s,&value) == 0){printf("当前栈顶元素为：%d\n", value); // 当前栈顶元素为：33}//测试出栈操作if (pop(&s,&value) == 0){printf("出栈的元素为：%d\n", value);  // 出栈的元素为：33}printSqStack(s);  // 栈中的元素（从栈底到栈顶）为: 11 22//销毁栈destroySqStack(&s);printSqStack(s);  // 栈空!return 0;
}

10. 完整代码

#include<stdio.h>
#include<stdlib.h>
/*栈：是只允许在一端进行插入或删除操作的线性表。栈顶：允许进行插入或删除的那一端栈底：固定的，不允许进行插入或删除的那一端栈的特性：后进先出存储方式：1. 顺序存储（顺序栈）  2. 链式存储（链式栈）
*//*在顺序栈的基本操作中，决定是传入一级指针还是只传入栈的变量，主要取决于操作是否需要修改栈的内部状态。1. 需要传入一级指针的情况当操作需要修改栈的内部状态，比如改变栈顶指针 top 的值或者修改栈中存储的数据时，就需要传入一级指针。这是因为在 C 语言里，函数参数传递是值传递，若直接传入栈的变量，函数内部对该变量的修改不会影响到原变量。而通过传入指针，函数可以直接访问和修改原变量所指向的内存。2. 只需要传入栈的变量的情况当操作不需要修改栈的内部状态，仅仅是读取栈的信息时，就可以只传入栈的变量。*//*以下是顺序栈实现它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针top指示当前的栈顶元素的位置
*/#define MaxSize 50
typedef int ElemType;
typedef struct SqStack {ElemType data[MaxSize];  //存放栈中元素int top;  //栈顶指针（注意，它不是实际意义上的指针变量，进行存放指针变量。这里说它是指针，意思是说，它指示了当前栈顶元素的位置，在第pos个位置。
}SqStack;// 操作1——初始化
void InitSeqStack(SqStack* s) {s->top = -1;  //初始化栈顶的位置
}/*这里设置初始栈顶指针s.top = -1,栈空条件是s.top = -1;栈满条件是s.top = MaxSize - 1则进栈时指针s.top+1,再将元素加入栈顶；出栈时先取出栈顶元素，后指针s.top - 1但如果设置初始栈顶指针s.top = 0,栈空条件是s.top = 0;栈满条件是s.top = MaxSize则进栈时将元素加入栈顶,再指针s.top+1；出栈时先指针s.top - 1，后取出栈顶元素	
*/// 操作2——判空
int SqStackEmpty(SqStack s) {return s.top == -1;
}// 操作3——判满
int SqStackFull(SqStack s) {return s.top == MaxSize - 1;
}// 操作4——入栈,将元素加到栈顶
int push(SqStack* s, ElemType value) {// 1. 判满if (SqStackFull(*s)){printf("栈满，无法入栈!\n");return -2;}// 2. 指针top + 1，再将值加入到栈顶s->top++;s->data[s->top] = value;return 0;  //入栈成功
}// 操作5——出栈
int pop(SqStack* s, ElemType* value) {//1. 判空if (SqStackEmpty(*s)){printf("栈空，无法有元素出栈!\n");return -1;}//2. 先取出栈顶元素，再指针top - 1*value = s->data[s->top];s->top--;return 0;  //出栈成功
}// 操作6——获取栈顶元素
int getTop(SqStack s,ElemType *value) {//1. 判空if (SqStackEmpty(s)){printf("栈空，无法有元素出栈!\n");return -1;}//2. 获取栈顶元素*value = s.data[s.top];return 0;  
}// 操作7——打印栈中元素
void printSqStack(SqStack s) {if (SqStackEmpty(s)){printf("栈空!\n");return;  //提前结束该函数}printf("栈中的元素（从栈底到栈顶）为: ");for (int i = 0; i <= s.top; i++) {printf("%d ", s.data[i]);}printf("\n");
}// 操作8——销毁栈
void destroySqStack(SqStack* s) {// 由于顺序栈使用的是静态数组，不需要显式释放内存// 只需要将栈顶指针置为 -1 表示栈为空s->top = -1;
}int main() {SqStack s;InitSeqStack(&s);// 测试入栈操作push(&s, 11);push(&s, 22);push(&s, 33);printSqStack(s);  // 栈中的元素（从栈底到栈顶）为: 11 22 33// 获取栈顶元素ElemType value;if (getTop(s,&value) == 0){printf("当前栈顶元素为：%d\n", value); // 当前栈顶元素为：33}//测试出栈操作if (pop(&s,&value) == 0){printf("出栈的元素为：%d\n", value);  // 出栈的元素为：33}printSqStack(s);  // 栈中的元素（从栈底到栈顶）为: 11 22//销毁栈destroySqStack(&s);printSqStack(s);  // 栈空!return 0;
}