C語言?棧與數(shù)組的實現(xiàn)詳解
棧的實現(xiàn)
首先我們思考一個問題，什么是棧？
棧是數(shù)據結構的一種，棧在我們日常編碼中遇到的非常多，很多人對棧的接觸可能僅僅局限在 遞歸使用的是棧 和 StackOverflowException，棧是一種后進先出的數(shù)據結構(可以想象生化金字塔的牢房和生化角斗場的狗洞)。
棧的定義
棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素
棧的應用廣泛，比如你的程序執(zhí)行查看調用堆棧、計算機四則加減運算、算法的非遞歸形式、括號匹配問題等等。所以棧也是必須掌握的一門數(shù)據結構。最簡單大家都經歷過，你拿一本書上下疊在一起，就是一個后進先出的過程，你可以把它看成一個棧。下面我們介紹數(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)棧空間不夠時可以直接時用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("棧已經空了！\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ù)據
//取出棧里有效元素個數(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.
?
}銷毀棧
銷毀棧是必不可少的的一步，如果沒有銷毀的話會造成內存泄露
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_top = -1;
ps->_capacity = 0;
}
鏈棧
最后介紹一下鏈棧，這里就不實現(xiàn)了有興趣的話可以自己實現(xiàn)一下。
鏈棧和鏈表一樣的，也是通指針將各個數(shù)據塊鏈接起來的
設計鏈棧是最好設計為雙向鏈表，否則當你設計為用尾作棧頂是出棧效率低。
用頭做棧頂時，頭插頭刪，可以設計為單鏈表。
到此這篇關于C語言 棧與數(shù)組的實現(xiàn)詳解的文章就介紹到這了,更多相關C語言 棧與數(shù)組內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++ 字符串去重排序實例代碼的相關資料,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了如何使用Qt框架實現(xiàn)一個簡單的計算器應用,我們將使用C++編程語言和Qt的圖形用戶界面庫來開發(fā)這個應用,并展示如何實現(xiàn)基本的算術操作,希望對大家有所幫助2023-11-11
這篇文章主要為大家詳細介紹了C++實現(xiàn)兩個有序數(shù)組的合并，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了C++實現(xiàn)編碼轉換的示例代碼，幫助大家快捷的實現(xiàn)編碼轉換，感興趣的朋友可以了解下2020-08-08
C++使用new和delete進行動態(tài)內存分配與數(shù)組封裝
這篇文章主要介紹了C++使用new和delete進行動態(tài)內存分配與數(shù)組封裝，運行期間才能確定所需內存大小，此時應該使用new申請內存，下面我們就進入文章學習具體的操作方法，需要的小伙伴可以參考一下2022-03-03
這篇文章主要介紹了C++實現(xiàn)單鏈表按k值重新排序的方法,結合實例形式分析了C++單鏈表中按照給定值進行判斷與排序的相關操作技巧,需要的朋友可以參考下2017-05-05
下面小編就為大家?guī)硪黄肅語言編輯畫圖程序的實現(xiàn)方法(推薦)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
最近在做項目時經常需要獲得文件的大小操作，雖然在網絡上已經有許多篇博客介紹了，但是還是想總結出自己一篇，記錄一下自己在項目中是怎么獲得文件大小的2022-10-10
Windows注冊表（Registry）是Windows操作系統(tǒng)中用于存儲系統(tǒng)配置信息、用戶設置和應用程序數(shù)據的一個集中式數(shù)據庫,本文主要為大家介紹了C++對注冊表的基本操作,感興趣的小伙伴可以了解下2023-11-11
C++實現(xiàn)查找二叉樹中和為某一值的所有路徑的示例
這篇文章主要介紹了C++實現(xiàn)查找二叉樹中和為某一值的所有路徑的示例,文中的方法是根據數(shù)組生成二叉排序樹并進行遍歷,需要的朋友可以參考下2016-02-02