1堆疊的概念
堆疊和順序表、鏈表一樣是屬于線性表的一種，堆疊的特性和順序表及鏈表有很大的不同，其他兩種結構都支持在頭部和尾部還有中部的插入、洗掉和查找，但堆疊只能在線性表的一端進行插入資料和洗掉資料等操作，堆疊對資料的操作遵循==“后入先出”==原則，即先放入堆疊中的資料拿出來的時候順序就靠后，這種概念通過畫圖更有助于理解，如圖
資料從表的一段插入到表中，表的另一端不能進行任何操作，這一端稱為堆疊的堆疊底，而放入資料的一端稱為堆疊頂，插入資料稱為壓堆疊，也可以從堆疊頂不斷的拿出資料直至空堆疊，拿出資料稱為出堆疊，出堆疊如圖示：
就像上面兩幅圖是，假定有資料元素1，2，3，4.當進堆疊順序是1<-2<-3<-4時，那么依次出堆疊的順序就是4<-3<-2<-1了，這種資料運行的規律就好像給一個彈夾裝子彈一樣，彈夾就是堆疊，子彈是一個個的資料，不斷加入到彈夾中，子彈打出來的時候是后裝入的先打出來，還比如老師改作業時的場景，先交的作業放在下面，后交的在上面，改作業時是從上面一本本拿出來改，生活中這種“后入先出”的場景還有很多，就不一一列舉了，對堆疊的操作一次壓入一個資料，或彈出一個資料，上面元素1，2，3，4，不改變進堆疊順序，但可以有多種出堆疊順序，出堆疊可以是2<-1<4-<3這里就是先連續壓入1，2，再彈出來，然后壓入3，4，再彈出來，
2.堆疊的代碼實作
堆疊可以在順序表或鏈表的基礎上改進之后就實作了，因為堆疊跟這兩種線性表相比就是少了好多的功能，堆疊只需在一端插入資料，洗掉資料即可，當用順序表來實作堆疊時，只要實作順序表的尾插和尾刪這樣的功能就行了，而且順序表有可以隨機訪問的作用，比用鏈表來實作時效率要高，這里我用順序表來實作堆疊，
先在頭檔案中定義一下堆疊的存盤結構，顯示要存的資料型別，容量和當前元素個數，
typedef int Datatype;
typedef struct STACK
{
Datatype* a;
int top;
int capacity;
}ST;
在test.c檔案中創建一個這種結構體型別的變數
ST Sta;
然后在頭檔案中宣告要實作堆疊操作的各種函式，
void stackinit(ST* plist); //對堆疊的初始化
void stackdestory(ST* plist); //堆疊的銷毀
void stackpush(ST* plist,Datatype); //壓入資料到堆疊中
void stackblus(ST* plist); //增容函式
Datatype stackpop(ST* plist); //從堆疊中彈出資料
int stacksize(ST* plist); // 計算堆疊中的資料元素個數
void stackdelete(ST* plist); //堆疊的元素洗掉
bool stackEmpty(ST* plist); //判斷堆疊是否為空
在stack.c源檔案中定義頭檔案中宣告的各個函式
#include"stack.h"
void stackinit(ST*plist)
{
plist->a = NULL;
plist->capacity = plist->top = 0;
}
void stackpush(ST* plist,Datatype x)
{
if (plist->top == plist->capacity)
stackblus(plist);
plist->a[plist->top] = x;
plist->top++;
}
void stackblus(ST* plist)
{
int newcapacity = (plist->top == 0) ? 4 : (2 * (plist->top));
Datatype* tem = (Datatype*)realloc(plist->a, newcapacity* sizeof(Datatype));
assert(tem);
plist->a = tem;
plist->capacity = newcapacity;
}
void stackdestory(ST* plist)
{
free(plist->a);
plist->a = NULL;
plist->capacity = plist->top = 0;
}
Datatype stackpop(ST* plist)
{
assert(plist->top); //空堆疊沒有資料可以彈出
Datatype tem = plist->a[plist->top-1];
plist->top--;
return tem;
}
int stacksize(ST* plist)
{
return plist->top;
}
void stackdelete(ST* plist)
{
assert(plist->top); //判斷是否還有元素可刪
plist->top--;
}
bool stackEmpty(ST* plist)
{
if (plist->top)
return true;
else
return false;
}
最后就可以在test.c中測驗堆疊的各種操作了
void test1()
{
ST Sta;
stackinit(&Sta);
stackpush(&Sta, 1);
stackpush(&Sta, 2);
stackpush(&Sta, 3);
Datatype a = stackpop(&Sta);
printf("%d ", a);
a = stackpop(&Sta);
printf("%d ", a);
a = stackpop(&Sta);
printf("%d ", a);
}
int main()
{
test1();
return 0;
}
結束語
博客剛開始寫，寫的比較粗糙，不過也是一個不斷學習的程序，我會向大佬看齊的，提高自己的表達能力，對知識總結更加到位，大家一起加油，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342211.html
標籤：其他
上一篇：終于有人把作業系統，CPU，基礎知識，網路一次講清楚了，絕絕子
下一篇：Linux動態庫和靜態庫