當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

【数据结构与算法】栈的介绍及基本运算（出栈、入栈、销毁栈等）

發(fā)布時(shí)間：2023/12/31 编程问答 26 豆豆

生活随笔收集整理的這篇文章主要介紹了【数据结构与算法】栈的介绍及基本运算（出栈、入栈、销毁栈等）小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

一、棧的介紹
棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。
允許插入和刪除運(yùn)算的一端稱作棧頂（top）。
不允許插入和刪除的另一端稱作棧底（bottom）。
在棧頂進(jìn)行的插入操作稱為入棧或進(jìn)棧(push)
在棧頂進(jìn)行的刪除操作稱為出棧或退棧(pop)
棧的特點(diǎn)：后進(jìn)先出，即 LIFO(Last In First Out)
如下圖：

順序棧的數(shù)據(jù)類型
靜態(tài)分配：

#define MaxSize 100 #define int ElemType typedef struct { ElemType data[MaxSize]; // 數(shù)組存儲(chǔ)空間int top; //棧頂下標(biāo) } SqStack; // 順序棧數(shù)據(jù)類型

MaxSize為順序棧的最大容量；
top為棧頂元素的下標(biāo)，0 <= top <= MaxSize-1
棧空：top = -1;
棧滿：top = MaxSize-1

注意棧空和棧滿的判斷條件，如上圖，棧頂top = 0 時(shí)，有數(shù)據(jù)元素a1，所以top = -1時(shí)，才能判斷棧空。棧滿時(shí)，由上圖看知。

動(dòng)態(tài)分配：

#define int ElemType typedef struct { ElemType *base; //棧底的指針ElemType *top; //棧頂?shù)闹羔?/span> } SqStack; // 順序棧數(shù)據(jù)類型

鏈?zhǔn)綏５臄?shù)據(jù)型

typedef struct LNode {ElemType data; //數(shù)據(jù)域struct LNode *next; //后繼結(jié)點(diǎn)指針 } LinkStNode; //鏈棧結(jié)點(diǎn)類型

S：單鏈表頭指針，指向頭結(jié)點(diǎn)。
棧頂：單鏈表第一個(gè)元素結(jié)點(diǎn)的位置，即頭結(jié)點(diǎn)的后一個(gè)位置。

二、順序棧的基本運(yùn)算
1、初始化棧
建立一個(gè)新的空棧s，實(shí)際上是將棧頂指示變量置-1即可。

//初始化空順序棧 int InitStack(SqStack &S) {S.top = -1;return 1; }

2、入棧：
①判斷棧是否已滿，若滿則產(chǎn)生上溢出錯(cuò)誤，退出算法，否則執(zhí)行第②步；
②棧頂下標(biāo)增一（top++），指向新的棧頂位置；
③將新元素置于棧頂。

//item是需要入棧的數(shù)據(jù)元素 bool Push(SqStack &S, ElemType item) {if (S.top == MaxSize - 1){cout << "棧滿" << endl;return false;}S.top++;S.data[S.top] = item;return true; }

3、出棧：
①判斷棧是否為空，若空則產(chǎn)生下溢出錯(cuò)誤，退出算法，否則執(zhí)行第②步；
②棧頂元素出棧；
③棧頂下標(biāo)減一（top++），指向新的棧頂位置；

bool Pop(SqStack &S, ElemType &item) {if (S.top == -1){cout << "棧空" << endl;return false;}item = S.data[S.top];S.top--;return true; }

4、判斷棧是否為空
棧S為空的條件是s.top==-1。

//判棧空 int StackEmpty(SqStack &S) {if(S.top==-1)return 1;elsereturn 0; }

5、取棧頂元素
在棧不為空的條件下，將棧頂元素賦給e。

//取棧頂 int GetTop(SqStack &S, DataType &e) {if(S.top <= -1){cout<<"棧空"<<endl;return 0;}item=S.items[S.top];return 1; }

注意：
取棧頂元素和出棧不同，取棧頂元素只是把棧頂元素復(fù)制一份，棧頂指針并沒(méi)有改變。如下圖：

入棧時(shí)要判斷棧是否滿，出棧時(shí)要判斷是否為空。

三、鏈?zhǔn)綏５幕具\(yùn)算
1、初始化棧
建立一個(gè)空棧s。實(shí)際上是創(chuàng)建鏈棧的頭結(jié)點(diǎn)，并將其next域置為NULL。

void (SNode *&s) { s=(SNode *)malloc(sizeof(SNode));//s=new SNode;s->next=NULL; }

2、入棧：

bool Push(LinkStNode *S, ElemType item) { //帶頭結(jié)點(diǎn)單鏈表的表頭插入法LinkStNode *t = new LinkStNode; //①生成新結(jié)點(diǎn)if (t == NULL){cout << "內(nèi)存不足";return false;}t->data = item;//②在棧頂插入新結(jié)點(diǎn)t->next = S->next;S->next = t; //③return true; }

3、出棧：

bool Pop(LinkStNode *S, ElemType &item) { //刪除單鏈表的第一個(gè)元素結(jié)點(diǎn)//①判斷棧是否為空if (S->next == NULL){cout << "棧空";return false;}//②刪除棧頂元素LinkStNode *t = S->next;S->next = t->next;item = t->data;delete t;return true; }

4、銷毀棧

//釋放鏈棧 void Destroy(SNode *&s) {SNode *p;while(s!=NULL){p=s;s=s->next;delete p;} }

5、判斷棧是否為空
棧S為空的條件是s->next==NULL，即單鏈表中沒(méi)有數(shù)據(jù)結(jié)點(diǎn)。

//判棧空 int StackEmpty(SNode *s) {if(s->next==NULL)return 1;elsereturn 0; }

6、取棧頂元素

int GetTop(SNode *s，DataType &e) { if (s->next==NULL) //棧空的情況{return 0;}e=s->next->data;return 1; }

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】栈的介绍及基本运算（出栈、入栈、销毁栈等）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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