3-2棧v第三章棧和隊(duì)列棧的邏輯結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)學(xué)什么？順序棧和鏈棧的比較3-2-1棧的邏輯結(jié)構(gòu)v第三章棧和隊(duì)列棧的定義棧：限定僅在一端進(jìn)行插入和刪除操作的線性表（a1,…,an-1,an）棧頂（top）：允許插入和刪除的一端稱為棧頂棧底（bottom）：另一端稱為棧底插入位置：1~n+1刪除位置：1~n線性表插入位置：n+1刪除位置：n棧棧底棧頂棧的操作特性插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧a插入刪除bc此時(shí)執(zhí)行出棧操作，哪個(gè)元素可以出棧呢？棧的操作特性：后進(jìn)先出（LastInFirstOut，LIFO）空棧：不含任何數(shù)據(jù)元素的棧

條件判斷

abc棧只是對(duì)插入和刪除操作的位置進(jìn)行了限制并沒有限定插入和刪除操作進(jìn)行的時(shí)間例1有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？情況一出棧：cbaabc情況二出棧：bca棧的操作特性abc能否得到如下出棧序列？出棧：cab例1有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的操作特性棧的抽象數(shù)據(jù)類型定義ADTStackDataModelOperationendADT棧中元素具有相同類型及后進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系InitStack：棧的初始化DestroyStack：棧的銷毀Push：入棧Pop：出棧GetTop：取棧頂元素Empty：判空相對(duì)于其他數(shù)據(jù)結(jié)構(gòu)，棧的基本操作是確定的InitStack輸入：無功能：棧的初始化，初始化一個(gè)空棧輸出：無

DestroyStack輸入：無功能：銷毀棧，釋放棧所占用的存儲(chǔ)空間輸出：無Push

輸入：元素值x

功能：在棧頂插入一個(gè)元素x

輸出：如果插入成功，棧頂增加了一個(gè)元素，否則返回失敗信息入棧出棧Push操作需要指明插入位置嗎？棧的抽象數(shù)據(jù)類型定義

Pop輸入：無功能：刪除棧頂元素輸出：如果刪除成功，返回被刪元素值；否則返回失敗信息GetTop輸入：無功能：讀取當(dāng)前的棧頂元素輸出：若棧不空，返回當(dāng)前的棧頂元素值；否則返回失敗信息Empty輸入：無功能：判斷棧是否為空輸出：如果棧為空，返回1；否則，返回0入棧出棧棧的抽象數(shù)據(jù)類型定義3-2-2棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)v第三章棧和隊(duì)列順序棧的存儲(chǔ)結(jié)構(gòu)定義順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)

012345678如何表示棧頂：設(shè)變量top存儲(chǔ)棧頂元素所在的下標(biāo)如何表示棧底：用數(shù)組的一端作為棧底如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)呢？topabc什么是順序存儲(chǔ)？constintStackSize=10;template<typenameDataType>classSeqStack{public:SeqStack();~SeqStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();intEmpty();private:DataTypedata[StackSize];inttop;};

順序棧的類定義InitStack：棧的初始化DestroyStack：棧的銷毀Push：入棧Pop：出棧GetTop：取棧頂元素Empty：判空棧的抽象數(shù)據(jù)類型定義？棧滿：top=StackSize-1template<typenameDataType>voidSeqStack<DataType>::Push(DataTypex){

if(top==StackSize-1)throw"上溢";

data[++top]=x;}時(shí)間復(fù)雜度？什么情況下無法入棧？順序棧的實(shí)現(xiàn)——入棧

012…

StackSize-1topabcx棧空：top=-1template<typenameDataType>DataTypeSeqStack<DataType>::Pop(){

DataTypex;

if(top==-1)throw"下溢";

x=data[top--];

returnx;}如何取棧頂元素？什么情況下無法出棧？

012…

StackSize-1abctop順序棧的實(shí)現(xiàn)——出棧判空的函數(shù)原型是什么？Empty

輸入：無功能：判斷棧是否為空輸出：如果棧為空，返回1；否則，返回0

012…

StackSize-1abctop?？眨簍op=-1template<typenameDataType>intSeqStack<DataType>::Empty(){if(top==-1)return1elsereturn0;}順序棧的實(shí)現(xiàn)——判空3-2-3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)v第三章棧和隊(duì)列存儲(chǔ)結(jié)構(gòu)定義鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表是如何存儲(chǔ)線性表的？firsta1a2an∧ai棧頂topanan-1a1∧firsta1a2an∧aiP：用鏈表的哪一端作為棧頂？A：為方便操作，用鏈頭作為棧頂P：鏈棧需要加頭結(jié)點(diǎn)嗎？P：?jiǎn)捂湵頌槭裁醇宇^結(jié)點(diǎn)？A：鏈棧無須加頭結(jié)點(diǎn)，也可以為了一致加上頭結(jié)點(diǎn)鏈棧的類定義template<typenameDataType>classLinkedStack{public:LinkedStack();~LinkedStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();intEmpty();private:

Node<DataType>*top;};InitStack：棧的初始化DestroyStack：棧的銷毀Push：入棧Pop：出棧GetTop：取棧頂元素Empty：判空棧的抽象數(shù)據(jù)類型定義？鏈棧的實(shí)現(xiàn)——入棧topanan-1a1∧xstoptemplate<typenameDataType>voidLinkedStack<DataType>::Push(DataTypex){Node<DataType>*s=nullptr;s=newNode<DataType>;s->data=x;//申請(qǐng)結(jié)點(diǎn)s數(shù)據(jù)域?yàn)閤

s->next=top;top=s;//將結(jié)點(diǎn)s插在棧頂}鏈棧的入棧操作為什么不用判斷是否棧滿？template<typenameDataType>DataTypeLinkedStack<DataType>::Pop(){Node<DataType>*p=nullptr;DataTypex;if(top==nullptr)throw"下溢";x=top->data;p=top;//暫存棧頂元素

top=top->next;//將棧頂結(jié)點(diǎn)摘鏈deletep;returnx;}topanan-1a1∧