C語(yǔ)言超詳細(xì)講解棧的實(shí)現(xiàn)及代碼
前言
棧的概念
- 棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。有點(diǎn)類(lèi)似于手槍彈夾，后壓進(jìn)去的子彈總是最先打出，除非槍壞了。
- 壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧。（入數(shù)據(jù)在棧頂）
- 出棧：棧的刪除操作叫做出棧。（出數(shù)據(jù)也在棧頂）
注意：
1、函數(shù)調(diào)用也有棧，這兩個(gè)棧有區(qū)別嗎？
當(dāng)然有區(qū)別。函數(shù)調(diào)用會(huì)調(diào)用棧幀，內(nèi)存里頭也有一個(gè)棧，程序運(yùn)行起來(lái)時(shí)要執(zhí)行函數(shù)，函數(shù)里頭的局部變量、參數(shù)、返回值等等都要存在函數(shù)棧幀里頭。
這兩個(gè)棧沒(méi)有任何關(guān)聯(lián)，一個(gè)是數(shù)據(jù)結(jié)構(gòu)中的棧。另一個(gè)是操作系統(tǒng)中內(nèi)存劃分的一個(gè)區(qū)域，叫做棧，用來(lái)函數(shù)調(diào)用時(shí)，建立棧幀。雖然本質(zhì)上沒(méi)有任何關(guān)聯(lián)，但都符合后進(jìn)先出的規(guī)則。
2、假設(shè)入棧順序?yàn)椋? 2 3 4，那么出棧順序一定為：4 3 2 1 嗎？
當(dāng)然不是。雖說(shuō)規(guī)則上明確后進(jìn)先出，可這是相對(duì)而言的，如果說(shuō)它每進(jìn)一個(gè)再出一個(gè)，然后再繼續(xù)壓棧，那不同樣符合后進(jìn)先出的規(guī)則嗎。就如同上例，你說(shuō)它出棧順序?yàn)? 2 3 4 都不足為奇，每進(jìn)一個(gè)出一個(gè)再進(jìn)，同樣符合規(guī)則。類(lèi)似的入棧兩個(gè)再出再進(jìn)再出也是可以的，好比如2 1 4 3。
棧的結(jié)構(gòu)
棧的實(shí)現(xiàn)
創(chuàng)建棧結(jié)構(gòu)
Stack.h 文件：
//創(chuàng)建棧結(jié)構(gòu)
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存儲(chǔ)數(shù)據(jù)
int top; //棧頂?shù)奈恢?
int capacity; //容量
}ST;初始化棧
思想：
初始化還是相對(duì)比較簡(jiǎn)單的，學(xué)了之前的順序表，初始化棧就很輕松了
Stack.h 文件：
//初始化棧 void StackInit(ST* ps);
Stack.c 文件：
//初始化棧
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}注意：
???這里初始化的時(shí)候?qū)op置為0是有意圖的。首先，由上文創(chuàng)建棧結(jié)構(gòu)時(shí)已經(jīng)標(biāo)注了，top是用來(lái)記錄棧頂?shù)奈恢?，既然是棧頂?shù)奈恢?，那?dāng)top初始化為0時(shí)，我們可以直接將數(shù)據(jù)放入棧中，隨后top++，但是當(dāng)top初始化為-1時(shí)，top首先要++才能放入數(shù)據(jù)，因?yàn)閿?shù)據(jù)不可能在負(fù)數(shù)不屬于棧的位置上放入。下圖演示過(guò)程：
本文以 top = 0 示例
銷(xiāo)毀棧
思想：
動(dòng)態(tài)開(kāi)辟的內(nèi)存空間一定要釋放，free置空即可，并把其余數(shù)據(jù)置0。
Stack.h 文件：
//銷(xiāo)毀棧 void StackDestory(ST* ps);
Stack.c 文件：
//銷(xiāo)毀棧
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}入棧
思路：
前文已經(jīng)強(qiáng)調(diào)了top初始化為0，那么理應(yīng)直接壓入數(shù)據(jù)，并把top++，不過(guò)在這之前，得判斷空間是否夠，當(dāng)top=capacity的時(shí)候，棧就滿了，那么就需要realloc擴(kuò)容。
Stack.h 文件：
//壓棧 void StackPush(ST* ps, STDataType x);
Stack.c 文件：
//壓棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果棧滿了，考慮擴(kuò)容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測(cè)容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//將數(shù)據(jù)壓進(jìn)去
ps->top++;//棧頂上移
}出棧
思路：
在你出棧之前，要確保top不為空，而top不為空的條件就是top>0，所以還要斷言top>0，隨后，直接將棧頂位置下移--即可。跟順序表的思想大同小異。
Stack.h 文件：
//出棧 void StackPop(ST* ps);
Stack.c 文件：
//出棧
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}獲取棧頂元素
思路：
首先要搞清楚誰(shuí)才是棧頂元素，是top位置還是top-1位置？很顯然是top-1的位置才是棧頂元素，因?yàn)樵谇拔某跏蓟臅r(shí)候已經(jīng)明確指出top為0，當(dāng)時(shí)壓棧時(shí)直接放入數(shù)據(jù)的，此時(shí)第一個(gè)數(shù)據(jù)下標(biāo)為0，隨后++top再壓入其它數(shù)據(jù)，由此可見(jiàn)，棧頂元素即下標(biāo)top-1的位置。
Stack.h 文件：
//訪問(wèn)棧頂數(shù)據(jù) STDataType StackTop(ST* ps);
Stack.c 文件：
//訪問(wèn)棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}獲取棧中有效元素個(gè)數(shù)
思想：
上文講到下標(biāo)top-1才是棧頂元素，那么是不是說(shuō)總共就是top-1個(gè)元素呢？當(dāng)然不是，這里跟數(shù)組下標(biāo)一樣的思想，元素個(gè)數(shù)應(yīng)該就是top個(gè)，直接返回即可。
Stack.h 文件：
//有效元素個(gè)數(shù) int StackSize(ST* ps);
Stack.c 文件：
//有效元素個(gè)數(shù)
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}檢測(cè)棧是否為空
思路：
當(dāng)top的值為0時(shí)即為空，return直接返回即可
Stack.h 文件：
//判空 bool StackEmpty(ST* ps);
Stack.c 文件：
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top為0，那么就為真，即返回
}Test.c 文件：
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
}效果如下：
總代碼
Stack.h 文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//創(chuàng)建棧結(jié)構(gòu)
typedef int STDataType;
typedef struct Stack
{
STDataType* a; //存儲(chǔ)數(shù)據(jù)
int top; //棧頂?shù)奈恢?
int capacity; //容量
}ST;
//初始化棧
void StackInit(ST* ps);
//銷(xiāo)毀棧
void StackDestory(ST* ps);
//壓棧
void StackPush(ST* ps, STDataType x);
//出棧
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//訪問(wèn)棧頂數(shù)據(jù)
STDataType StackTop(ST* ps);
//有效元素個(gè)數(shù)
int StackSize(ST* ps);Stack.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化棧
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
//銷(xiāo)毀棧
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//壓棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//如果棧滿了，考慮擴(kuò)容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測(cè)容量
ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//將數(shù)據(jù)壓進(jìn)去
ps->top++;//棧頂上移
}
//出棧
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0; //如果top為0，那么就為真，即返回
}
//訪問(wèn)棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{
assert(ps);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}
//有效元素個(gè)數(shù)
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
}
int main()
{
TestStack();
return 0;
}到此這篇關(guān)于C語(yǔ)言超詳細(xì)講解棧的實(shí)現(xiàn)及代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言 棧的實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文將利用Qt中的QLabel、QPushButton這兩個(gè)控件，為大家詳細(xì)介紹一下Qt控件點(diǎn)擊消息獲取的方法，文中的示例代碼講解詳細(xì)，感興趣的可以了解一下2022-06-06
Qt編寫(xiě)地圖遷徙圖的實(shí)現(xiàn)示例
本文主要介紹了Qt編寫(xiě)地圖遷徙圖的實(shí)現(xiàn)示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
Windows安裝Qt6.4.2及簡(jiǎn)單驗(yàn)證
本文主要介紹了Windows安裝Qt6.4.2及簡(jiǎn)單驗(yàn)證，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
C++分析構(gòu)造函數(shù)與析造函數(shù)的特點(diǎn)梳理
本文對(duì)類(lèi)的構(gòu)造函數(shù)和析構(gòu)函數(shù)進(jìn)行總結(jié)，主要包括了構(gòu)造函數(shù)的初始化、重載、使用參數(shù)和默認(rèn)參數(shù)，拷貝構(gòu)造函數(shù)和析構(gòu)函數(shù)，希望能幫助讀者在程序開(kāi)發(fā)中更好的理解類(lèi)，屬于C/C++基礎(chǔ)2022-05-05
C++中結(jié)構(gòu)體和Json字符串互轉(zhuǎn)的問(wèn)題詳解
這篇文章主要給大家介紹了關(guān)于C++中結(jié)構(gòu)體和Json字符串互轉(zhuǎn)問(wèn)題的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
FFRPC應(yīng)用 Client/Server使用及原理解析
這篇文章主要介紹了FFRPC應(yīng)用 Client/Server使用及原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-08-08
運(yùn)算符重載是一種形式的C++多態(tài)，重載運(yùn)算符可以使代碼看起來(lái)更加自然，下面通過(guò)例子介紹下C++ 運(yùn)算符重載知識(shí)，感興趣的朋友一起看看吧2021-11-11
本文分別給大家介紹了2個(gè)C++在Linux平臺(tái)和windows平臺(tái)下實(shí)現(xiàn)字符串模糊匹配的方法，基本的核心思想都是一樣的，均是使用fnmatch函數(shù)，有需要的小伙伴可以參考下。2016-04-04
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)歸并排序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-08-08
C++指針運(yùn)算符(&和*)的實(shí)現(xiàn)
C++ 提供了兩種指針運(yùn)算符,一種是取地址運(yùn)算符 &,一種是間接尋址運(yùn)算符 *,本文就詳細(xì)的介紹一下這兩種運(yùn)算符的使用,具有一定的參考價(jià)值,感興趣的可以了解一下2023-08-08