數(shù)據(jù)結(jié)構(gòu)之堆棧
掃描二維碼
隨時(shí)隨地手機(jī)看文章
堆棧的基本概念
堆棧是一種特殊的線(xiàn)性表，堆棧的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線(xiàn)性表完全相同，其差別是：線(xiàn)性表允許在任意位置插入和刪除數(shù)據(jù)元素操作，而堆棧只允許在固定一端進(jìn)行插入和刪除數(shù)據(jù)元素操作
根據(jù)堆棧的定義，每次進(jìn)棧的數(shù)據(jù)元素都放在原當(dāng)前棧頂元素之前而成為新的棧頂元素，每次退棧的數(shù)據(jù)元素都是原當(dāng)前棧頂元素，這樣，最后進(jìn)入堆棧的數(shù)據(jù)元素總是最先退出堆棧，因此，堆棧也稱(chēng)作后進(jìn)先出的線(xiàn)性表，或簡(jiǎn)稱(chēng)后進(jìn)先出表。
例子
設(shè)有數(shù)據(jù)元素序列A,B,C，是否可以利用一個(gè)堆棧，得到數(shù)據(jù)元素序列B, A, C。
分析：按照如下方法操作：A入棧，B入棧，B出棧，A出棧，C入棧，C出棧，則輸出數(shù)據(jù)元素序列為B, A, C。因此，利用一個(gè)堆棧，可以把數(shù)據(jù)元素序列A, B, C變換為數(shù)據(jù)元素序列B, A,C。其操作過(guò)程的堆棧內(nèi)容示意圖下圖所示。
在軟件設(shè)計(jì)中，需要利用堆棧進(jìn)行數(shù)據(jù)元素序列轉(zhuǎn)換的例子很多。例如，在編譯軟件系統(tǒng)中，就需要頻繁地把中綴表達(dá)式形式的算術(shù)表達(dá)式，轉(zhuǎn)換成后綴表達(dá)式形式的算術(shù)表達(dá)式。又如，任何支持遞歸算法的程序設(shè)計(jì)語(yǔ)言，都是借助堆棧來(lái)實(shí)現(xiàn)遞歸算法需要的后調(diào)用的過(guò)程先執(zhí)行的要求的。
堆棧操作集合
-
初始化StackInitiate(S)：初始化堆棧S。 -
非空否StackNotEmpty(S)：堆棧S非空否。若堆棧非空，則函數(shù)返回1；否則函數(shù)返回0。 -
入棧StackPush(S, x)：在堆棧S的當(dāng)前棧頂插入數(shù)據(jù)元素x。 -
出棧StackPop(S, d)：把堆棧S的當(dāng)前棧頂數(shù)據(jù)元素刪除并由參數(shù)d帶回。若出棧成功，則返回1；失敗，則返回0。 -
取棧頂數(shù)據(jù)元素StackTop(S, d)：取堆棧S的當(dāng)前棧頂數(shù)據(jù)元素并由參數(shù)d帶回。若取到數(shù)據(jù)元素，則返回1；否則返回0。
順序堆棧的存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)結(jié)構(gòu)的堆棧稱(chēng)作順序堆棧。
順序堆棧和順序表的數(shù)據(jù)成員是相同的，不同之處是，順序堆棧的入棧和出棧操作只能對(duì)當(dāng)前棧頂元素進(jìn)行。
順序堆棧的存儲(chǔ)結(jié)構(gòu)示意圖如圖3-3所示。其中，a0, a1, a2, a3, a4表示順序堆棧要存儲(chǔ)的數(shù)據(jù)元素序列，stack表示順序堆棧存放數(shù)據(jù)元素的數(shù)組，MaxStackSize表示順序堆棧數(shù)組stack的最大存儲(chǔ)單元個(gè)數(shù)，top表示順序堆棧數(shù)組stack的當(dāng)前棧頂位置。
定義結(jié)構(gòu)體SeqStack如下：
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize]; //連續(xù)內(nèi)存空間存放棧中元素
int top; //存放棧頂元素在data數(shù)組中的下標(biāo)
}SqStack;
順序堆棧的操作實(shí)現(xiàn)
-
初始化StaticInitiate(*S)
void StaticInitiate(*S)
{
S->top=0; //初始化棧頂下標(biāo)值
}
-
非空否StackNotEmpty(S)
int StackNotEmpty(S) //判斷順序堆棧S是否為空，非空返回1，否則返回0
{
if(S.top<=0)
return 0;
else
return 1;
}
-
入棧StackPush(SeqStack *S,DataType x)
int StackPush(SeqStack *S,DataType x)//把數(shù)據(jù)元素x存入順序堆棧S中，入棧成功返回1，否則返回0
{
if(S->top>=MaxStackSize)
{
printf("堆棧已滿(mǎn)，無(wú)法插入！\n")
return 0;
}
else
{
S->Stack[S->top]=x;
S->top++;
return 1;
}
}
-
出棧StackPop(SeqStack *S,DataType)
int StackPop(SeqStack *S,DataType) //取出順序堆棧S的棧頂元素值由參數(shù)d帶回，出棧成功則返回1，否則返回0
{
if(S->top<=0)
{
printf("堆棧已空無(wú)數(shù)據(jù)元素出棧！\n");
return 0;
}
else
{
S->top--; //得注意top--，--top的差別
*d=S->stack[S->top];
return 1;
}
}
-
取棧頂數(shù)據(jù)元素StackTop(SeqStack S,DataType *d)
int StackTop(SeqStack S,DataType *d) //取棧頂數(shù)據(jù)元素值由參數(shù)d帶回，成功返回1，不成功返回0
{
if(S.top<=0)
{
printf("堆棧已空！\n");
return 0;
}
else
{
*d=S.stack[S.top-1];
return 1;
}
}
-
撤銷(xiāo)動(dòng)態(tài)申請(qǐng)空間Destory(SLNode *head)
void Destory(SLNode *head)
{
LSNode *p,*p1;
p=head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p);
}
}
堆棧應(yīng)用
括號(hào)匹配問(wèn)題: 假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類(lèi)型的括號(hào)，編寫(xiě)一個(gè)函數(shù)，用來(lái)判別表達(dá)式中括號(hào)是否正確配對(duì)，并設(shè)計(jì)一個(gè)測(cè)試主函數(shù)。
算法思想: 檢驗(yàn)括號(hào)是否配對(duì)可以設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，如果是左括號(hào)，則直接進(jìn)棧，如果讀入的是右括號(hào)，并且與當(dāng)前棧頂?shù)淖罄ㄌ?hào)是同類(lèi)型的，則說(shuō)明括號(hào)是配對(duì)的，將棧頂?shù)淖罄ㄌ?hào)出棧，否則不配對(duì)。如果輸入序列已經(jīng)讀完，而棧中仍然有等待配對(duì)的左括號(hào)，則該括號(hào)不配對(duì)。
代碼實(shí)現(xiàn)
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include "string.h"
/*宏定義和鏈棧類(lèi)型定義*/
typedef char DataType;
#include "LinkStack.h" //包括鏈棧實(shí)現(xiàn)文件
int Match(DataType e,DataType ch); //檢驗(yàn)括號(hào)是否配對(duì)函數(shù)
int main()
{
LinkStack S;
char *p;
DataType e;
DataType ch[60];
InitStack(&S); //初始化鏈棧
printf("請(qǐng)輸入帶括號(hào)的表達(dá)式");
gets(ch);
p=ch;
while(*p)
{
switch(*p)
{
case '(':
case '[':
case '{':
PushStack(S,*p++);
break;
case ')':
case ']':
case '}':
if (StackEmpty(S))
{
printf("缺少左括號(hào)。\n");
return 0;
}
else
{
GetTop(S,&e);
if (Match(e,*p))
{
PopStack(S,&e);
}
else
{
printf("左括號(hào)不配對(duì)\n");
return 0;
}
}
default: //如果是其他字符，則不處理，直接指向下一個(gè)字符
p++;
}
}
if (StackEmpty(S))
{
printf("括號(hào)匹配\n");
return 1;
}
else
{
printf("缺少右括號(hào)\n");
return 0;
}
}
int Match(DataType e,DataType ch)
{
if (e=='('&&ch==')')
{
return 1;
}
else if (e=='['&&ch==']')
{
return 1;
}
else if (e=='{'&&ch=='}')
{
return 1;
}
else
{
return 0;
}
}
算術(shù)表達(dá)式計(jì)算問(wèn)題
-
中綴表達(dá)式和后綴表達(dá)式的描述
在編譯系統(tǒng)中，算術(shù)表達(dá)式可以分為三類(lèi)：算術(shù)表達(dá)式，關(guān)系表達(dá)式，邏輯表達(dá)式。任何一個(gè)算術(shù)表達(dá)式都是由：操作數(shù)，運(yùn)算符和分界符組成。我們把操作數(shù)，運(yùn)算符和分界符（分界符標(biāo)志了一個(gè)算術(shù)表達(dá)式的結(jié)束）稱(chēng)為一個(gè)算術(shù)表達(dá)式的單詞。
中綴表達(dá)式：算術(shù)表達(dá)式中的運(yùn)算符總是出現(xiàn)在兩個(gè)操作數(shù)之間（除單目運(yùn)算符外）
A+（B-C/D）*E
后綴表達(dá)式：表達(dá)式中的運(yùn)算符出現(xiàn)在操作數(shù)之后。編譯系統(tǒng)對(duì)于中綴表達(dá)式處理方法是將其變成后綴表達(dá)式
ABCD/-E*+
-
后綴表達(dá)式的特點(diǎn)
-
后綴表達(dá)式的操作數(shù)和中綴表達(dá)式的操作數(shù)先后次序完全相同（上面ABCDE），只是運(yùn)算符的先后次序改變了（+-/*）； -
后綴表達(dá)式中沒(méi)有括號(hào)，后綴表達(dá)式的運(yùn)算次序就是其執(zhí)行次序
-
后綴表達(dá)式的實(shí)現(xiàn)過(guò)程
編譯系統(tǒng)設(shè)置一個(gè)存放運(yùn)算符的堆棧，初始時(shí)棧頂置一個(gè)分界符“#”。編譯系統(tǒng)從左到右依次掃描中綴表達(dá)式，每讀到一個(gè)操作數(shù)就把它作為后綴表達(dá)式的一部分輸出，每讀到一個(gè)運(yùn)算符（分界符也看作運(yùn)算符）就將其優(yōu)先級(jí)與棧頂運(yùn)算符優(yōu)先級(jí)運(yùn)算符進(jìn)行比較，以決定是就所讀到的運(yùn)算符進(jìn)棧，還是將棧頂運(yùn)算符作為最為后綴算術(shù)表達(dá)式的一部分輸出。
-
運(yùn)算符優(yōu)先級(jí)別注意：若把O1看成棧頂運(yùn)算符，O2看成當(dāng)前掃描讀到的運(yùn)算符。
當(dāng)O1為“+”或“-”，O2為“*”或“/”時(shí)，O1的優(yōu)先級(jí) < O2的優(yōu)先級(jí)(滿(mǎn)足先乘除，后加減) 當(dāng)O1為“+”“-”“*”或“/”，O2為“（”時(shí)，O1的優(yōu)先級(jí) < O2的優(yōu)先級(jí)（滿(mǎn)足先括號(hào)內(nèi)，后括號(hào)外的規(guī)則） 當(dāng)O1的運(yùn)算符和O2的運(yùn)算符同級(jí)別時(shí)，O1的優(yōu)先級(jí) > O2的優(yōu)先級(jí)別（同級(jí)別先左后右規(guī)則） 由于后綴表達(dá)式無(wú)括號(hào)，當(dāng)O1為“（”，O2為“）”時(shí)，用標(biāo)記“=”使算法在此時(shí)去掉該對(duì)算法； 當(dāng)O1為“#”時(shí)，O2為“#”時(shí)，用標(biāo)記“=”使算法在此時(shí)結(jié)束處理 若表中的值為空，則不允許出現(xiàn)這種情況，一旦出現(xiàn)即為中綴算術(shù)表達(dá)式語(yǔ)法出錯(cuò)，如O1為“）”，而O2為“（”情況，即為中綴表達(dá)式語(yǔ)法錯(cuò)誤！
-
算法步驟：
（1）設(shè)置一個(gè)堆棧，初始時(shí)將棧頂元素置為#
（2）順序讀入中綴算術(shù)表達(dá)式，當(dāng)讀到的單詞為操作數(shù)是就將其輸出，并接著讀下一個(gè)單詞
（3）單讀到的單詞為運(yùn)算符時(shí)，令a為當(dāng)前棧頂運(yùn)算符的變量，b為當(dāng)前掃描讀到運(yùn)算符的變量，把當(dāng)前讀到的運(yùn)算符賦給b,然后比較變量a的優(yōu)先級(jí)和b的優(yōu)先級(jí)。若a的優(yōu)先級(jí)高于ｂ的優(yōu)先級(jí)，則將ａ退棧并作為后綴表達(dá)式的一個(gè)單詞輸出，，然后比較新的棧頂元素運(yùn)算符ａ的優(yōu)先級(jí)與ｂ的優(yōu)先級(jí)。
若優(yōu)先級(jí)?。幔迹猓瑒t將ｂ的值進(jìn)棧，然后接著讀下一個(gè)單詞 若優(yōu)先級(jí)?。幔荆?，則將ａ退棧并作為后綴表達(dá)式的一個(gè)單詞輸出，然后比較新的棧頂元素運(yùn)算符ａ的優(yōu)先級(jí)與ｂ的優(yōu)先級(jí)。 若優(yōu)先級(jí) ａ＝ｂ且ａ為“（”，ｂ為“）”。則將ａ退棧，接著讀下一個(gè)單詞 若優(yōu)先級(jí) ａ＝ｂ且ａ為“?！保鉃椤埃！?。算法結(jié)束。
函數(shù)實(shí)現(xiàn)
int PostExp(char str[]) //借助堆棧計(jì)算后綴表達(dá)式str的值
{
DataType x,x1,x2;
int i;
LsNode *head; //定義頭指針變量head
StackInitiate(&head); //初始化鏈?zhǔn)蕉褩ead
for(i-0;str[i]!=#;i++) //循環(huán)直到輸入為#
{
if(isdigit(str[i])) //當(dāng)str[i]為操作數(shù)時(shí)
{
x=(int)(str[i]-48); //轉(zhuǎn)換成int類(lèi)型數(shù)據(jù)存于變量x中
StackPush(head,x); //x入棧
}
else //當(dāng)str[i]為運(yùn)算符時(shí)
{
StackPop(head,&x2); //退棧的操作數(shù)，存于變量x2中
StackPop(head,&x1); //退棧的被操作數(shù)，存于變量x1中
switch(str[i]) //執(zhí)行str[i]所表示的運(yùn)算
{
case '+':
{
x1+=x2; break;
}
case '-':
{
x1-=x2; break;
}
case '*':
{
x1*=x2; break;
}
case '/':
{
if(x2==0.0)
{
printf("除數(shù)為0錯(cuò)誤！\n");
exit(0);
}
else
{
x1/=x2;
break;
}
}
}
StackPush(head,x1); //運(yùn)算結(jié)果入棧
}
}
StackPop(head,&x); //得到計(jì)算結(jié)果存于x
return x; //返回計(jì)算結(jié)果
}
應(yīng)用
設(shè)有后綴算術(shù)表達(dá)式ABCD/-E*+，其中，變量A等于3，變量B等于6，變量C等于4，變量D等于2，變量E等于5，設(shè)計(jì)一個(gè)程序，求出該后綴算術(shù)表達(dá)式的值。
代碼實(shí)現(xiàn)
#include<stdio.h>
#include<malloc.h> //包含有exit()函數(shù)
#include<stdlib.h> //包含isdigit()函數(shù)
#include<ctype.h> //定義DataType（）函數(shù)
typedef int DataType;
#include"LinStack.h"
int PostExp(char str[]) //借助堆棧計(jì)算后綴表達(dá)式str的值
{
DataType x,x1,x2;
int i;
LsNode *head; //定義頭指針變量head
StackInitiate(&head); //初始化鏈?zhǔn)蕉褩ead
for(i-0;str[i]!=#;i++) //循環(huán)直到輸入為#
{
if(isdigit(str[i])) //當(dāng)str[i]為操作數(shù)時(shí)
{
x=(int)(str[i]-48); //轉(zhuǎn)換成int類(lèi)型數(shù)據(jù)存于變量x中
StackPush(head,x); //x入棧
}
else //當(dāng)str[i]為運(yùn)算符時(shí)
{
StackPop(head,&x2); //退棧的操作數(shù)，存于變量x2中
StackPop(head,&x1); //退棧的被操作數(shù)，存于變量x1中
switch(str[i]) //執(zhí)行str[i]所表示的運(yùn)算
{
case '+':
{
x1+=x2; break;
}
case '-':
{
x1-=x2; break;
}
case '*':
{
x1*=x2; break;
}
case '/':
{
if(x2==0.0)
{
printf("除數(shù)為0錯(cuò)誤！\n");
exit(0);
}
else
{
x1/=x2;
break;
}
}
}
StackPush(head,x1); //運(yùn)算結(jié)果入棧
}
}
StackPop(head,&x); //得到計(jì)算結(jié)果存于x
return x; //返回計(jì)算結(jié)果
}
void main()
{
char str[]="3642/-5*+#";
int result;
result=PostExp(str);
printf("后綴算術(shù)表達(dá)式計(jì)算結(jié)果為：%d",result);
}
程序運(yùn)行結(jié)果：23
掃碼關(guān)注我們
看更多嵌入式案例
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀(guān)點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
