文章目錄

• • 1 棧的原理
  • 2 棧的算法實(shí)現(xiàn)
  • • 2.1 棧數(shù)據(jù)結(jié)構(gòu)的定義
    • 2.2 棧的初始化
    • 2.3 入棧
    • 2.4 出棧
    • 2.5 獲取棧頂元素
    • 2.6 判斷空棧
    • 2.7 獲取棧中元素個(gè)數(shù)
    • 2.8 銷(xiāo)毀棧
    • 2.9 測(cè)試代碼

1 棧的原理

胡同里的小汽車(chē)是排成一條直線，是線性排列，而且只能從一端進(jìn)出，后進(jìn)的汽車(chē)先出去，后進(jìn)先出（Last In First Out，LIFO），這就是"棧"。棧也是一種線性表，只不過(guò)它是操作受限的線性表，只能在一端操作。

進(jìn)出的一端稱(chēng)為棧頂（top），另一端稱(chēng)為棧底（base）。

其中，base 指向棧底，top 指向棧頂。

注意：棧只能在一端操作，后進(jìn)先出，這是棧的關(guān)鍵特征，也就是說(shuō)不允許在中間查找、取值、插入、刪除等操作，我們掌握好順序棧的初始化、入棧，出棧，取棧頂元素等操作即可。

---

2 棧的算法實(shí)現(xiàn)

2.1 棧數(shù)據(jù)結(jié)構(gòu)的定義

#define MaxSize 128 //預(yù)先分配空間，這個(gè)數(shù)值根據(jù)實(shí)際需要預(yù)估確定typedef int ElemType;typedef struct _SqStack{ElemType *base; //棧底指針ElemType *top; //棧頂指針 }SqStack;

2.2 棧的初始化

bool InitStack(SqStack &S) //構(gòu)造一個(gè)空棧 S {S.base = new int[MaxSize];//為順序棧分配一個(gè)最大容量為 Maxsize 的空 間if (!S.base) //空間分配失敗return false;S.top=S.base; //top 初始為 base，空棧return true; }

2.3 入棧

入棧操作：判斷是否棧滿，如果棧已滿，則入棧失敗，否則將元素放入棧頂，棧頂指針向上移動(dòng)一個(gè)空間（top++）。

bool PushStack(SqStack &S, int e) // 插入元素 e 為新的棧頂元素 {if (S.top-S.base == MaxSize) //棧滿return false;*(S.top++) = e; //元素 e 壓入棧頂，然后棧頂指針加 1，等價(jià)于*S.top=e;S.top++;return true; }

2.4 出棧

出棧操作: 和入棧相反，出棧前要判斷是否棧空，如果棧是空的，則出棧失敗，否則將棧頂元素暫存給一個(gè)變量，棧頂指針向下移動(dòng)一個(gè)空間（top–）。

bool PopStack(SqStack &S, ElemType &e) //刪除 S 的棧頂元素，暫存在變量 e中 {if (S.base == S.top){ //棧空return false;}e = *(--S.top); //棧頂指針減 1，將棧頂元素賦給 ereturn true; }

2.5 獲取棧頂元素

取棧頂元素和出棧不同，取棧頂元素只是把棧頂元素復(fù)制一份，棧的元素個(gè)數(shù)不變，而出棧是指棧頂元素取出，棧內(nèi)不再包含這個(gè)元素。

ElemType GetTop(SqStack &S) //返回 S 的棧頂元素，棧頂指針不變 {if (S.top != S.base){ //棧非空return *(S.top - 1); //返回棧頂元素的值，棧頂指針不變}else{return -1;} }

2.6 判斷空棧

bool IsEmpty(SqStack &S){//判斷棧是否為空if (S.top == S.base){return true;}else{return false;} }

2.7 獲取棧中元素個(gè)數(shù)

int GetSize(SqStack &S){//返回棧中元素個(gè)數(shù)return (S.top-S.base); }

2.8 銷(xiāo)毀棧

void DestoryStack(SqStack &S) {if(S.base){free(S.base);S.base = NULL;S.top = NULL;} }

2.9 測(cè)試代碼

int main() {int n,x;SqStack S;InitStack(S);//初始化一個(gè)順序棧 Scout <<"請(qǐng)輸入元素個(gè)數(shù) n：" <<endl;cin>>n;cout <<"請(qǐng)依次輸入 n 個(gè)元素，依次入棧：" <<endl;while(n--){cin>>x; //輸入元素PushStack(S, x);}cout <<"元素依次出棧：" <<endl;while(!IsEmpty(S))//如果棧不空，則依次出棧{cout<<GetTop(S)<<"\t";//輸出棧頂元素PopStack(S, x); //棧頂元素出棧}cout <<endl;DestoryStack(S);system("pause");return 0; }

---

參考資料：

C/C++從入門(mén)到精通-高級(jí)程序員之路【奇牛學(xué)院】

總結(jié)

以上是生活随笔為你收集整理的栈的原理及实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。