=========================================================================
相關(guān)代碼gitee自取：
C語言學習日記: 加油努力 (gitee.com)
?=========================================================================
接上期：
【數(shù)據(jù)結(jié)構(gòu)初階】四、線性表里的鏈表（帶頭+雙向+循環(huán) 鏈表 -- C語言實現(xiàn)）_高高的胖子的博客-CSDN博客
?=========================================================================
? ? ? ? ? ? ? ? ? ? ?
1 . 棧（Stack）
棧的概念和結(jié)構(gòu)：
棧的概念
- 一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作
? ? ? ? ? ? ? ? ? ?- 進行數(shù)據(jù)插入和刪除操作的一端 稱為棧頂，另一端稱為棧底
? ? ? ? ? ? ? ??- 棧中的數(shù)據(jù)元素遵守
后進先出（LIFO -- Last In First Out）的原則 -- 后進入的元素會先出來? ? ? ? ? ? ? ?
壓棧和出棧
- 棧的插入操作叫做進棧/壓棧/入棧 -- Push
入數(shù)據(jù)在棧頂
? ? ? ? ? ? ? ?- 棧的刪除操作叫做出棧 -- Pop
出數(shù)據(jù)也在棧頂? ? ? ? ? ? ? ? ? ??
棧的結(jié)構(gòu)
? ? ? ? ?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
? ? ? ? ? ? ?
2 . 棧的實現(xiàn)
? ? ? ? ? ? ? ? ? ?
使用 順序表(數(shù)組) 或 鏈表(鏈式結(jié)構(gòu)) 都可以實現(xiàn)棧，
使用鏈表的話，可以使用 尾插(頭插)?和 尾刪(頭刪)?實現(xiàn) 棧的“后進先出”，
（ 尾插 -- 壓棧? ? ? ? ；? ? ??尾刪 -- 出棧 ）
使用順序表同樣可以使用 尾插 和 尾刪 實現(xiàn)，
但順序表的尾插和尾刪操作效率較高，處理數(shù)據(jù)時的緩存利用率也較高，
所以下面用順序表(數(shù)組)實現(xiàn)棧：
? ? ? ? ? ? ? ?
（詳細解釋在圖片的注釋中，代碼分文件放下一標題處）
? ? ? ? ? ? ? ?
實現(xiàn)具體功能前的準備工作
- 包含之后會用到的頭函數(shù)
? ? ? ? ? ? ? ? ? ? ? ? ? ?- 創(chuàng)建棧數(shù)據(jù)類型?--?棧中存儲數(shù)據(jù)的類型
? ? ? ? ? ? ?- 創(chuàng)建棧結(jié)構(gòu)體(類型) -- 類型中應有控制棧內(nèi)元素指針、棧頂值、棧大小
圖示
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------文章來源：http://www.zghlxwxcb.cn/news/detail-717285.html
? ? ? ? ? ??
STInit函數(shù) --?對棧類型進行初始化
- assert斷言棧類型指針不為空
? ? ? ? ? ?- 將棧內(nèi)元素控制指針置為空，
將棧容量（大?。?/span>置為0，
將棧頂值定義為0圖示
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
STDestroy函數(shù) --?銷毀棧類型
- assert斷言棧類型指針不為空
? ? ? ? ? ?- 釋放棧內(nèi)元素控制指針并置空，
棧容量置為0，
棧頂值置為0圖示
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
STPush函數(shù) --?進行壓棧
- assert斷言棧類型指針不為空
? ? ? ? ? ?- 為棧開辟動態(tài)空間并進行檢查
? ? ? ? ? ? ?- 開辟成功后，棧內(nèi)元素控制指針指向開辟的空間，
重新設(shè)置capacity棧容量
? ? ? ? ? ? ? ?- 將壓棧的值（x）放入棧
? ? ? ? ? ? ?- 調(diào)整棧頂值“下標”top的位置
圖示
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
STPop函數(shù) --?進行出棧
- assert斷言棧類型指針不為空，
assert斷言棧不為空
? ? ? ? ? ?- 把棧頂向下移動一個單位即可實現(xiàn)“刪除”（出棧）
圖示
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
STTop函數(shù) --?獲取棧頂元素
- assert斷言棧類型指針不為空，
assert斷言棧不為空
? ? ? ? ? ?- 返回棧頂元素
圖示
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
STSize函數(shù) --?計算棧中元素個數(shù)
- assert斷言棧類型指針不為空
? ? ? ? ? ?- 返回top，即棧中元素個數(shù)
圖示
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
STEmpty函數(shù) --?判斷棧是否為空
- assert斷言棧類型指針不為空
? ? ? ? ? ?- 判斷top棧頂值是否為空，
是則返回true，否則返回false圖示
? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ??
總體測試：
? ? ? ? ?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
? ? ? ? ? ? ?
3 . 對應代碼
Stack.h?-- 棧頭文件
#pragma once //包含之后需要的頭文件： #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //動態(tài)順序表： //定義棧的棧頂數(shù)據(jù)元素： typedef int STDataType; //定義棧類型： typedef struct Stack { //為棧開辟動態(tài)空間時的頭指針： //控制棧內(nèi)元素的指針 STDataType* a; //棧頂值(用于定義棧頂)： int top; //類似于數(shù)組下標 //棧存放數(shù)據(jù)容量（棧的大小）： int capacity; }ST; //重命名為ST //靜態(tài)順序表： //define N 10 //struct Stack //{ // int a[N]; // int top; //}; //初始化棧函數(shù) -- 對棧類型進行初始化 //接收棧類型指針 void STInit(ST* ps); //銷毀棧函數(shù) -- 銷毀棧類型 //接收棧類型指針 void STDestroy(ST* ps); //因為只有壓棧和出棧操作 //只操作棧頂元素，所以沒有 //頭插（尾插）頭刪（頭刪）等其他操作 //壓棧函數(shù) -- 進行壓棧 //接收棧類型指針（ps）、進行壓棧的值（x） void STPush(ST* ps, STDataType x); //出棧函數(shù) -- 進行出棧 //接收棧類型指針 void STPop(ST* ps); //棧頂元素函數(shù) -- 獲取棧頂元素 //接收棧類型指針 STDataType STTop(ST* ps); //棧中元素函數(shù) --計算棧中元素個數(shù) //接收棧類型指針 int STSize(ST* ps); //判空函數(shù) -- 判斷棧是否為空 //接收棧類型指針 bool STEmpty(ST* ps);? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ? ? ??文章來源地址http://www.zghlxwxcb.cn/news/detail-717285.html
Stack.c -- 棧函數(shù)實現(xiàn)文件
#define _CRT_SECURE_NO_WARNINGS 1 //包含棧頭文件： #include "Stack.h" //初始化棧函數(shù) -- 對棧類型進行初始化 //接收棧類型指針 void STInit(ST* ps) { //assert斷言棧類型指針不為空： assert(ps != NULL); //將棧內(nèi)元素控制指針置為空： ps->a = NULL; //將棧容量（大?。┲脼?： ps->capacity = 0; //將棧頂值定義為0： ps->top = 0; } //銷毀棧函數(shù) -- 銷毀棧類型 //接收棧類型指針 void STDestroy(ST* ps) { //assert斷言棧類型指針不為空： assert(ps != NULL); //釋放棧內(nèi)元素控制指針： free(ps->a); //并將其置為空： ps->a = NULL; //棧容量置為0： ps->capacity = 0; //棧頂值置為0： ps->top = 0; } //壓棧函數(shù) -- 進行壓棧 //接收棧類型指針（ps）、進行壓棧的值（x） void STPush(ST* ps, STDataType x) { //assert斷言棧類型指針不為空： assert(ps != NULL); //為棧開辟動態(tài)空間： if (ps->top == ps->capacity) //棧頂值 等于 棧大小 //說明空間不夠，需要擴容 { //只有壓棧時容量會增大可能需要擴容 //只有這個函數(shù)會進行擴容操作， //所以沒必要單獨寫一個擴容函數(shù) //進行擴容: int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //因為棧容量capacity初始化為0， //所以可以使用三目操作符進行增容： //ps->capacity == 0 ? 4 : ps->capacity * 2 //如果為0則直接增容到4，不為0則增容2倍 //開辟動態(tài)空間： STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newCapacity); //這里直接使用realloc進行動態(tài)空間開辟 //如果realloc函數(shù)接收頭指針（第一個參數(shù)）為空， //那么它的作用相當于malloc函數(shù) //對開辟空間進行檢查： if (tmp == NULL) //返回空指針，開辟失?。? { //打印錯誤信息： perror("realloc fail"); //終止程序： exit(-1); } //開辟成功后， //棧內(nèi)元素控制指針指向開辟空間： ps->a = tmp; //重新設(shè)置capacity棧容量： ps->capacity = newCapacity; } //將壓棧的值（x）放入棧： ps->a[ps->top] = x; //上面以a為頭開辟連續(xù)的空間， //所以a可以看作一個數(shù)組名使用（？） //通過數(shù)組下標放入值 //再調(diào)整棧頂值“下標”位置： ps->top++; } //出棧函數(shù) -- 進行出棧 //接收棧類型指針 void STPop(ST* ps) { //assert斷言棧類型指針不為空： assert(ps != NULL); //assert斷言棧頂top到了棧底就不能繼續(xù)出棧了 assert(ps->top > 0); //棧不為空 //出棧只要棧頂top-- //把棧頂向下移動一個單位即可實現(xiàn)”刪除“（出棧）： --ps->top; } //棧頂元素函數(shù) -- 獲取棧頂元素 //接收棧類型指針 STDataType STTop(ST* ps) { //assert斷言棧類型指針不為空： assert(ps != NULL); //assert斷言棧為空的話就不能找棧頂元素了 assert(ps->top > 0); //返回棧頂元素： return ps->a[ps->top - 1]; //top即棧中元素個數(shù)： //top從0開始，壓棧后top++，先賦值再++ //top永遠在棧頂元素的下一個位置 //所以要獲得棧頂元素就要top-1到棧頂元素位置 } //棧中元素函數(shù) --計算棧中元素個數(shù) //接收棧類型指針 int STSize(ST* ps) { //assert斷言棧類型指針不為空： assert(ps != NULL); //top即棧中元素個數(shù)： //top從0開始，壓棧后top++，先賦值再++ //top永遠在棧頂元素的下一個位置 return ps->top; } //判空函數(shù) -- 判斷棧是否為空 //接收棧類型指針 bool STEmpty(ST* ps) { //assert斷言棧類型指針不為空： assert(ps != NULL); //如果top為0 //說明棧中沒有元素 return ps->top == 0; //top為0 -> 棧為空 -> 返回true //top不為0 -> 棧不為空 -> 返回false }? ? ? ? ? ??
? ? ? ? ? ??
---------------------------------------------------------------------------------------------
? ? ? ? ? ? ? ??
Test.c -- 棧測試文件
#define _CRT_SECURE_NO_WARNINGS 1 //包含棧頭文件： #include "Stack.h" //測試函數(shù)： void TestStack() { //創(chuàng)建一個棧類型： ST st; //對其進行初始化： STInit(&st); //使用壓棧往棧中增加元素： STPush(&st, 1); STPush(&st, 2); STPush(&st, 3); STPush(&st, 4); STPush(&st, 5); //元素大于4個再次進行擴容 //打印當前棧中元素個數(shù)： printf("目前棧內(nèi)元素個數(shù)為：%d\n", STSize(&st)); //換行： printf("\n"); //使用while循環(huán)： //打印棧頂元素再出棧，循環(huán)此操作： //證明棧的后進先出原則 while (!STEmpty(&st)) //鏈表不為空就繼續(xù)操作： { //打印當前棧頂元素： printf("出棧前棧頂元素：%d\n", STTop(&st)); //進行出棧： STPop(&st); } //換行： printf("\n"); //打印當前棧中元素個數(shù)： printf("目前棧內(nèi)元素個數(shù)為：%d", STSize(&st)); //進行銷毀： STDestroy(&st); } //主函數(shù) int main() { TestStack(); return 0; }
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)初階】五、線性表中的棧（C語言 -- 順序表實現(xiàn)棧）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
