C語言實(shí)現(xiàn)棧的示例詳解
前言
前一段時間，我們試著用C語言實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的順序表，單鏈表，雙向循環(huán)鏈表。今天我們再用C語言來實(shí)現(xiàn)另一種特殊的線性結(jié)構(gòu)：棧
一. 什么是棧
棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。限定僅在表尾進(jìn)行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
類似于步槍的子彈夾，后進(jìn)去的子彈先發(fā)射出來以后，前面的子彈才可以發(fā)射。
二. 使用什么來實(shí)現(xiàn)棧
前一段時間，我們學(xué)習(xí)了兩種線性表，一種是順序表，一種是鏈表，那么對于棧我們該用哪一個來實(shí)現(xiàn)比較好呢
首先我們來對比一下線性表和鏈表
| 不同點(diǎn) | 順序表 | 鏈表 |
|---|---|---|
| 存儲空間上 | 物理上一定連續(xù) | 邏輯上連續(xù)，但物理上不一定連續(xù) |
| 隨機(jī)訪問 | 可以直接訪問任何元素 | 必須從頭節(jié)點(diǎn)開始往后尋找 |
| 任意位置插入或刪除元素 | 要搬移其他的元素，效率低。 | 只需要修改節(jié)點(diǎn)的指針指向，效率高 |
| 插入 | 動態(tài)順序表，當(dāng)空間不夠時需要擴(kuò)容 | 無容量概念，需要就申請，不用就釋放 |
| 應(yīng)用場景 | 元素高效存儲，并且需要頻繁訪問 | 需要在任意位置插入或者刪除頻繁 |
綜合以上來看，我認(rèn)為實(shí)現(xiàn)一個棧，使用順序表比較好。
1.棧是先進(jìn)后出，使用順序表，在元素出棧后更容易找到新的棧頂。
2.順序表CPU高速緩存命中率高，可以減少CPU去內(nèi)存拿數(shù)據(jù)的次數(shù)，速度快，效率高。
三. 棧的實(shí)現(xiàn)
3.1 頭文件
1.包含的標(biāo)準(zhǔn)庫
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //C語言中的bool類型需要這個頭文件 #include <assert.h>
2.定義結(jié)構(gòu)體
typedef int STDateType;//棧中元素的數(shù)據(jù)類型
typedef struct Stack
{
STDateType* a; //順序表
int top; //棧頂
int capacity; //棧的容量
}Stack;
3.函數(shù)的聲明
void StackInti(Stack* ps); // 棧的初始化 void StackDestory(Stack* ps); // 棧的銷毀 void StackPush(Stack* ps, STDateType x); // 入棧 void StackPop(Stack* ps); // 出棧 bool StackEmpty(Stack* ps); // 判斷棧是否為空 STDateType StackTop(Stack* ps); // 取棧頂元素
3.2 函數(shù)實(shí)現(xiàn)
1. 棧的初始化
我們用assert（斷言），防止ps為空指針。
void StackInti(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
2. 棧的銷毀
釋放順序表。
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
3.入棧
void StackPush(Stack* ps, STDateType x)
{
assert(ps);
if (ps->top == ps->capacity) //判斷容量是否足夠
{
int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
if (ps->a == NULL)
{
printf("ralloc error");
exit(-1);
}
ps->capacity = newCapcity;
}
ps->a[ps->top] = x;
ps->top++;
}
4. 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0); //空棧不能被刪除
ps->top--;
}
5. 判斷棧是否為空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0; // 如果為空則返回true，否則返回false
}
6. 取棧頂元素
STDateType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//空棧不能被刪除
return ps->a[ps->top - 1];
}
這樣我們就實(shí)現(xiàn)了一個簡單的棧
3.3 完整代碼
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDateType;
typedef struct Stack
{
STDateType* a;
int top;
int capacity;
}Stack;
void StackInti(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
void StackPush(Stack* ps, STDateType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
if (ps->a == NULL)
{
printf("ralloc error");
exit(-1);
}
ps->capacity = newCapcity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
STDateType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
四. 棧的用處
我們好不容易實(shí)現(xiàn)了一個棧，接下來我們來做個題看看棧有什么用吧。
題目描述
給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
基礎(chǔ)框架
C語言的基礎(chǔ)框架如下
bool isValid(char * s){
???????}
解題思路
左括號一定要和右括號對齊，非常滿足棧的特性
我們可以將所有的左括號存入一個棧中。
然后遇到右括號，就出棧，判斷是否匹配。
直到棧為空且字符串中的括號也遍歷完了，那么所有括號就正確的匹配了。
代碼詳解
// 1.因?yàn)镃語言并沒有現(xiàn)成的棧，所以我們需要自己造輪子，先寫個棧再說
typedef char STDateType; // 更改數(shù)據(jù)類型為char
typedef struct Stack
{
STDateType* a;
int top;
int capacity;
}Stack;
void StackInti(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
void StackPush(Stack* ps, STDateType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (int*)realloc(ps->a, sizeof(int) * newCapcity);
if (ps->a == NULL)
{
printf("ralloc error");
exit(-1);
}
ps->capacity = newCapcity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
STDateType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
bool isValid(char * s){
Stack a;
StackInti(&a);
while(*s)
{
if (*s == '(' || *s == '[' || *s == '{') //入棧
{
StackPush(&a, *s);
}
else //出棧
{
if(StackEmpty(&a)) //右括號多一個的情況
{
return false;
}
char tmp = StackTop(&a);
StackPop(&a);
if ((*s == ')' && tmp != '(')
||(*s == ']' && tmp != '[')
||(*s == '}' && tmp != '{') )
{
return false;
}
}
s++;
}
return StackEmpty(&a); //防止出現(xiàn)多一個左括號的情況
}
到此這篇關(guān)于C語言實(shí)現(xiàn)棧的示例詳解的文章就介紹到這了,更多相關(guān)C語言 棧內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言實(shí)現(xiàn)點(diǎn)餐系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)點(diǎn)餐系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-11-11
C++中的static和const的關(guān)鍵字用法詳解
這篇文章主要介紹了C++中的static和const的關(guān)鍵字用法詳解,這是一道經(jīng)常在面試中被問到的知識，本文給大家詳細(xì)介紹下，需要的朋友可以參考下2023-06-06
本文主要介紹了JsonCpp中double的問題解決，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
C語言函數(shù)指針與回調(diào)函數(shù)的實(shí)現(xiàn)
本文主要介紹了C語言函數(shù)指針與回調(diào)函數(shù)的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05
C++中strcpy函數(shù)的實(shí)現(xiàn)
strncpy這個可以指定拷貝字符的長度，指定源地址，目標(biāo)地址，還有需要拷貝的字符的長度； strcpy只能傳入兩個參數(shù)，只指定拷貝的起始地址跟目標(biāo)地址，然后整體拷貝；2015-10-10
本文主要介紹了淺談C++不同繼承之間的關(guān)系，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)控制臺版的掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
c語言的cps實(shí)現(xiàn)求fibonacci數(shù)列示例
這篇文章主要介紹了c語言的cps實(shí)現(xiàn)求fibonacci數(shù)列示例,需要的朋友可以參考下2014-03-03
這篇文章主要介紹了C 語言二叉樹幾種遍歷方法詳解及實(shí)例的相關(guān)資料,二叉樹在數(shù)據(jù)結(jié)構(gòu)當(dāng)中是非常重要的知識要點(diǎn)，這里對二叉樹進(jìn)行了總結(jié)，需要的朋友可以參考下2017-01-01
C++?STL實(shí)現(xiàn)非變易查找算法的示例代碼
C++?STL?中的非變易算法（Non-modifying?Algorithms）是指那些不會修改容器內(nèi)容的算法,是C++提供的一組模板函數(shù),下面我們就來看看這一算法的應(yīng)用吧2023-08-08