棧 棧的操作原則是：先進后出，后進先出二、棧的特點根據(jù)棧的定義可知，最先放入棧中元素在棧底，最后放入的元素在棧頂，而刪除元素剛好相反，最后放入的元素最先刪除，最先放入的元素最后刪除。也就是說，棧是一種后進先出(Last In First Out)的線性表，簡稱為LIFO表。 三、棧的運算 1.初始化棧：INISTACK(&S)將棧S置為一個空棧(不含任何元素)。2.進棧：PUSH(&S,X)將元素X插入到棧S中，也稱為 “入棧”、 “插入”、 “壓入”。3.出棧： POP(&S) 刪除棧S中的棧頂元素，也稱為”退棧”、 “刪除”、 “彈出”。4.取棧頂元素： GETTOP(S)取棧S中棧頂元素。5.判棧空： EMPTY(S)判斷棧S是否為空，若為空，返回值為1，否則返回值為0。  棧總是處于棧空、棧滿或不空不滿三種狀態(tài)之一，它們是通過棧頂指針top的值體現(xiàn)出來的。規(guī)定：top的值為下一個進棧元素在數(shù)組中的下標值。棧空時（初始狀態(tài)），top=0;棧滿時，top=MAXN. 三、棧的五種運算
（一） 進棧1） 進棧算法（1） 檢查棧是否已滿，若棧滿，進行“溢出”處理。（2） 將新元素賦給棧頂指針所指的單元。（3） 將棧頂指針上移一個位置（即加1）。  （二） 出棧1） 出棧算法（1） 檢查棧是否為空，若棧空，進行“下溢”處理。（2）將棧頂指針下移一個位置（即減1） 。（3）取棧頂元素的值，以便返回給調(diào)用者。 四．棧的共享存儲單元有時，一個程序設計中，需要使用多個同一類型的棧,這時候，可能會產(chǎn)生一個棧空間過小，容量發(fā)生溢出，而另一個棧空間過大，造成大量存儲單元浪費的現(xiàn)象。 為了充分利用各個棧的存儲空間，這時可以采用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實現(xiàn)存儲空間優(yōu)勢互補。 4、兩個棧共享同一存儲空間    　當程序中同時使用兩個棧時，可以將兩個棧的棧底設在向量空間的兩端，讓兩個棧各自向中間延伸。當一個棧里的元素較多，超過向量空間的一半時，只要另一個棧的元素不多，那么前者就可以占用后者的部分存儲空間。    只有當整個向量空間被兩個棧占滿（即兩個棧頂相遇）時，才會發(fā)生上溢。因此，兩個棧共享一個長度為m的向量空間和兩個棧分別占用兩個長度為 └ m/2┘和┌m/2┐的向量空間比較，前者發(fā)生上溢的概率比后者要小得多。  隊列   1、定義    　隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表 （1）允許刪除的一端稱為隊頭（Front）。　　（2）允許插入的一端稱為隊尾（Rear）。　　（3）當隊列中沒有元素時稱為空隊列。　　（4）隊列亦稱作先進先出（First In First Out）的線性表，簡稱為FIFO表。    　隊列的修改是依先進先出的原則進行的。新來的成員總是加入隊尾（即不允許"加塞"），每次離開的成員總是隊列頭上的（不允許中途離隊），即當前"最老的"成員離隊。 隊列的存儲結構： 順序隊列隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表，和順序表一樣，順序隊列也是必須用一個數(shù)組來存放當前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設兩個指針和分別指示隊頭和隊尾元素在隊列中的位置。  
1.隊列先進先出，棧先進后出。2. 對插入和刪除操作的"限定"。 棧是限定只能在表的一端進行插入和刪除操作的線性表。      隊列是限定只能在表的一端進行插入和在另一端進行刪除操作的線性表。     從"數(shù)據(jù)結構"的角度看，它們都是線性結構，即數(shù)據(jù)元素之間的關系相同。但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的"限定"。     棧和隊列是在程序設計中被廣泛使用的兩種線性數(shù)據(jù)結構，它們的特點在于基本操作的特殊性，棧必須按"后進先出"的規(guī)則進行操作，而隊列必須按"先進先出" 的規(guī)則進行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結構。3.遍歷數(shù)據(jù)速度不同。棧只能從頭部取數(shù)據(jù) 也就最先放入的需要遍歷整個棧最后才能取出來，而且在遍歷數(shù)據(jù)的時候還得為數(shù)據(jù)開辟臨時空間，保持數(shù)據(jù)在遍歷前的一致性隊列怎不同，他基于地址指針進行遍歷，而且可以從頭或尾部開始遍歷，但不能同時遍歷，無需開辟臨時空間，因為在遍歷的過程中不影像數(shù)據(jù)結構，速度要快的多棧（Stack）是限定只能在表的一端進行插入和刪除操作的線性表。隊列（Queue）是限定只能在表的一端進行插入和在另一端進行刪除操作的線性表。從"數(shù)據(jù)結構"的角度看，它們都是線性結構，即數(shù)據(jù)元素之間的關系相同。但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的"限定"。棧和隊列是在程序設計中被廣泛使用的兩種線性數(shù)據(jù)結構，它們的特點在于基本操作的特殊性，棧必須按"后進先出"的規(guī)則進行操作，而隊列必須按"先進先出"的規(guī)則進行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結構。可將線性表和棧及隊列的插入和刪除操作對比如下：線性表 Insert(L,i,x)(1≤i≤n+1) Delete(L,i)(1≤i≤n) 如線性表允許在表內(nèi)任一位置進行插入和刪除 棧 Insert(L,n+1,x) Delete(L,n) 而棧只允許在表尾一端進行插入和刪除 隊列 Insert(L,n+1,x) Delete(L,1) 隊列只允許在表尾一端進行插入，在表頭一端進行刪除-5