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;
}