C語言?棧與數(shù)組的實現(xiàn)詳解
棧的實現(xiàn)
首先我們思考一個問題，什么是棧？
棧是數(shù)據(jù)結構的一種，棧在我們?nèi)粘＞幋a中遇到的非常多，很多人對棧的接觸可能僅僅局限在 遞歸使用的是棧 和 StackOverflowException，棧是一種后進先出的數(shù)據(jù)結構(可以想象生化金字塔的牢房和生化角斗場的狗洞)。
棧的定義
棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素
棧的應用廣泛，比如你的程序執(zhí)行查看調(diào)用堆棧、計算機四則加減運算、算法的非遞歸形式、括號匹配問題等等。所以棧也是必須掌握的一門數(shù)據(jù)結構。最簡單大家都經(jīng)歷過，你拿一本書上下疊在一起，就是一個后進先出的過程，你可以把它看成一個棧。下面我們介紹數(shù)組實現(xiàn)的棧兩種形式。
數(shù)組實現(xiàn)
靜態(tài)棧
一般不推薦使用這種方法，因為當空間不夠用時，增容會有點麻煩，不實用。
typedef struct Stack
{
STDataType _a[]; //STDataType 為int宏定義，當然你也可以將它定義為其他類型，宏定義是為了換棧類型的時候方便一點
int _top; // 棧頂
int _capacity; // 容量
}Stack;動態(tài)棧
相比靜態(tài)棧，動態(tài)?？臻g不夠時可以直接時用realloc動態(tài)擴容，但是動態(tài)擴會有一定程度的消耗，我們會直接擴容一倍，當使用不完時會造成一定程度的空間浪費。
typedef struct Stack
{
STDataType* _a;//指向一塊開辟出來的連續(xù)空間的指針
int _top; // 棧頂
int _capacity; // 容量
}Stack;棧要實現(xiàn)的操作
// 初始化棧 void StackInit(Stack* ps); // 入棧 void StackPush(Stack* ps, STDataType data); // 出棧 void StackPop(Stack* ps); // 獲取棧頂元素 STDataType StackTop(Stack* ps); // 獲取棧中有效元素個數(shù) int StackSize(Stack* ps); // 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0 bool StackEmpty(Stack* ps); // 銷毀棧 void StackDestroy(Stack* ps);
棧的初始化
void StackInit(Stack* ps)
{
ps->_a = NULL; //初始化時將指針指向空,此時沒有開辟空間
//這里可以將top賦值為0，也可以賦值為-1。
ps->_top = -1; //賦值為0時表示top為棧頂元素的下一個位置的下標，賦值為-1時top為棧頂元素的下標
ps->_capacity = 0; //棧的容量
}入棧
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//考慮要不要增容
//當top為0時判斷條件為
//if(ps->top==ps->_capacity)
if (ps->_top+1 == ps->_capacity)//當棧滿時進入
{
//判斷當前棧的容量是否為0，為0的話開辟4個空間，不為0時擴容一倍
int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = realloc(ps->_a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newcapacity;
}
//擴容完成，或者不用擴容，開始插入
ps->_top++;
ps->_a[ps->_top] = data;
//當top為0時插入操作
//ps->_a[ps->_top] = data;
//ps->_top++;
}出棧
void StackPop(Stack* ps)
{
assert(ps);
//判斷是否為空
assert(!StackEmpty(ps));//暴力判斷
//if (top==-1)//溫柔判斷
//{
// printf("棧已經(jīng)空了！\n");
// exit(-1); //甩出異常
//}
ps->_top--;
}取棧頂元素
STDataType StackTop(Stack* ps)
{
assert(ps);
//判斷是否為空,為空甩出異常。
assert(!StackEmpty(ps));
//if (!StackEmpty(ps)) {
// printf("棧為空！\n");
// exit(-1);
//}
return ps->_a[ps->_top]; //返回棧頂元素
}判斷棧中有幾個有效數(shù)據(jù)
//取出棧里有效元素個數(shù)。
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top+1;
}判斷棧是否為空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == -1; //ps->_top為-1返回true,否則返回false.
?
}銷毀棧
銷毀棧是必不可少的的一步，如果沒有銷毀的話會造成內(nèi)存泄露
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_top = -1;
ps->_capacity = 0;
}
鏈棧
最后介紹一下鏈棧，這里就不實現(xiàn)了有興趣的話可以自己實現(xiàn)一下。
鏈棧和鏈表一樣的，也是通指針將各個數(shù)據(jù)塊鏈接起來的
設計鏈棧是最好設計為雙向鏈表，否則當你設計為用尾作棧頂是出棧效率低。
用頭做棧頂時，頭插頭刪，可以設計為單鏈表。
到此這篇關于C語言 棧與數(shù)組的實現(xiàn)詳解的文章就介紹到這了,更多相關C語言 棧與數(shù)組內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了EasyX實現(xiàn)自由落體小球，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要為大家詳細介紹了C++貪心算法實現(xiàn)馬踏棋盤，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要為大家詳細介紹了STL中vector的使用，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了解析C++編程中的選擇結構和switch語句的用法,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了C語言實現(xiàn)abs和fabs絕對值，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
本文通過實例代碼給大家介紹了基于Qt實現(xiàn)視頻播放器功能，代碼簡單易懂，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-09-09
這個也算是企業(yè)招工里面比較常見的一道筆試面試題了，非常簡單。個人覺得考的主要是對指針使用的熟練程度，還有對字符串類內(nèi)部原理的掌握程度2013-12-12
c++ 盡量不要使用#define 而是用const、enum、inline替換。
為什么這么說呢？或許很多程序員已經(jīng)習慣在文件開始使用大量的#define語句2013-01-01
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)摳圖工具，文中示例代碼介紹的非常詳細，具有一定為大家詳細的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要為大家詳細介紹了iOS鎖屏音頻播放控制及音頻信息設置，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12