【正文】 實(shí)驗(yàn)三 棧和隊(duì)列：（1） 熟悉棧的特點(diǎn)（先進(jìn)后出）及棧的基本操作，如入棧、出棧等，掌握棧的基本操作在棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；（2） 熟悉隊(duì)列的特點(diǎn)（先進(jìn)先出）及隊(duì)列的基本操作，如入隊(duì)、出隊(duì)等，掌握隊(duì)列的基本操作在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。 實(shí)驗(yàn)要求：（1） 復(fù)習(xí)課本中有關(guān)棧和隊(duì)列的知識(shí)；（2） 用C語(yǔ)言完成算法和程序設(shè)計(jì)并上機(jī)調(diào)試通過(guò)；（3） 撰寫實(shí)驗(yàn)報(bào)告，給出算法思路或流程圖和具體實(shí)現(xiàn)（源程序）、算法分析結(jié)果（包括時(shí)間復(fù)雜度、空間復(fù)雜度以及算法優(yōu)化設(shè)想）、輸入數(shù)據(jù)及程序運(yùn)行結(jié)果（必要時(shí)給出多種可能的輸入數(shù)據(jù)和運(yùn)行結(jié)果）。 基礎(chǔ)實(shí)驗(yàn)[實(shí)驗(yàn)1] 棧的順序表示和實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求:編寫一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完成如下功能：（1）初始化順序棧（2）插入元素（3）刪除棧頂元素（4）取棧頂元素（5）遍歷順序棧（6）置空順序棧分析:棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧,它是運(yùn)算受限的順序表。對(duì)于順序棧，入棧時(shí)，首先判斷棧是否為滿，棧滿的條件為：ptop= =MAXNUM1，棧滿時(shí)，不能入棧。 否則出現(xiàn)空間溢出，引起錯(cuò)誤，這種現(xiàn)象稱為上溢。出棧和讀棧頂元素操作，先判棧是否為空，為空時(shí)不能操作，否則產(chǎn)生錯(cuò)誤。通常?？兆鳛橐环N控制轉(zhuǎn)移的條件。注意：（1）順序棧中元素用向量存放（2）棧底位置是固定不變的，可設(shè)置在向量?jī)啥说娜我庖粋€(gè)端點(diǎn)（3）棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（通常稱top為棧頂指針）來(lái)指示當(dāng)前棧頂位置參考程序:includeincludedefine MAXNUM 20define ElemType int/*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedef struct { ElemType stack[MAXNUM]。 int top。}SqStack。/*初始化順序棧*/void InitStack(SqStack *p){ if(!p) printf(Eorror)。 ptop=1。}/*入棧*/void Push(SqStack *p,ElemType x){ if(ptopMAXNUM1) { ptop=ptop+1。 pstack[ptop]=x。 } else printf(Overflow!\n)。}/*出棧*/ElemType Pop(SqStack *p){ ElemType x。 if(ptop!=0) { x=pstack[ptop]。 printf(以前的棧頂數(shù)據(jù)元素%d已經(jīng)被刪除！\n,pstack[ptop])。 ptop=ptop1。 return(x)。 } else { printf(Underflow!\n)。 return(0)。 }}/*獲取棧頂元素*/ElemType GetTop(SqStack *p){ ElemType x。 if(ptop!=0) { x=pstack[ptop]。 return(x)。 } else { printf(Underflow!\n)。 return(0)。 }}/*遍歷順序棧*/void OutStack(SqStack *p){ int i。 printf(\n)。 if(ptop0) printf(這是一個(gè)空棧！)。 printf(\n)。 for(i=ptop。i=0。i) printf(第%d個(gè)數(shù)據(jù)元素是：%6d\n,i,pstack[i])。}/*置空順序棧*/void setEmpty(SqStack *p){ptop= 1。}/*主函數(shù)*/main(){ SqStack *q。 int y,cord。ElemType a。 do{ printf(\n)。 printf(第一次使用必須初始化！\n)。 printf(\n)。 printf(\n 主菜單 \n)。 printf(\n 1 初始化順序棧 \n)。 printf(\n 2 插入一個(gè)元素 \n)。 printf(\n 3 刪除棧頂元素 \n)。 printf(\n 4 取棧頂元素 \n)。 printf(\n 5 置空順序棧 \n)。 printf(\n 6 結(jié)束程序運(yùn)行 \n)。 printf(\n\n)。 printf(請(qǐng)輸入您的選擇( 1, 2, 3, 4, 5,6))。 scanf(%d,amp。cord)。 printf(\n)。 switch(cord) { case 1: { q=(SqStack*)malloc(sizeof(SqStack))。 InitStack(q)。 OutStack(q)。 }break。 case 2: { printf(請(qǐng)輸入要插入的數(shù)據(jù)元素：a=)。 scanf(%d,amp。a)。 Push(q,a)。 OutStack(q)。 }break。 case 3: { Pop(q)。 OutStack(q)。 }break。 case 4: { y=GetTop(q)。 printf(\n棧頂元素為：%d\n,y)。 OutStack(q)。 }break。 case 5: { setEmpty(q)。 printf(\n順序棧被置空！\n)。 OutStack(q)。 }break。 case 6: exit(0)。 } }while (cord=6)。}[實(shí)驗(yàn)2] 棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求:編寫一個(gè)程序?qū)崿F(xiàn)鏈棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完成如下功能：（1）初始化鏈棧（2）鏈棧置空（3）入棧（4）出棧（5）取棧頂元素（6）遍歷鏈棧分析:鏈棧是沒(méi)有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。注意：（1）LinkStack結(jié)構(gòu)類型的定義可以方便地在函數(shù)體中修改top指針本身（2）若要記錄棧中元素個(gè)數(shù)，可將元素個(gè)數(shù)屬性放在LinkStack類型中定義。（3）鏈棧中的結(jié)點(diǎn)是動(dòng)態(tài)分配的，所以可以不考慮上溢。參考程序:include include include typedef int Elemtype。typedef struct stacknode { Elemtype data。 stacknode * next。}StackNode。typedef struct { stacknode * top。 //棧頂指針}LinkStack。 /*初始化鏈棧*/void InitStack(LinkStack * s){ stop=NULL。 printf(\n已經(jīng)初始化鏈棧！\n)。}/*鏈棧置空*/void setEmpty(LinkStack * s){ stop=NULL。 printf(\n鏈棧被置空！\n)。}/*入棧*/void pushLstack(LinkStack * s, Elemtype x){ StackNode * p。 p=(StackNode *)malloc(sizeof(StackNode))。 //建立一個(gè)節(jié)點(diǎn)。 pdata=x。 pnext=stop。 //由于是在棧頂pushLstack，所以要指向棧頂。 stop=p。 //插入}/*出棧*/Elemtype popLstack(LinkStack * s){ Elemtype x。 StackNode * p。 p=stop。 //指向棧頂 if (stop ==0) { printf(\n棧空，不能出棧！\n)。 exit(1)。 } x=pdata。 stop=pnext。 //當(dāng)前的棧頂指向原棧的next free(p)。 //釋放 return x。}/*取棧頂元素*/Elemtype StackTop(LinkStack *s){ if (stop ==0) { printf(\n鏈?？誠(chéng)n)。 exit(1)。 } return stopdata。}/*遍歷鏈棧*/void Disp(LinkStack * s){ printf(\n鏈棧中的數(shù)據(jù)為：\n)。 printf(====================================