介紹棧和隊列基本概念和用法。

?

設輸入序列1、2、3、4，則下述序列中（ ）不可能是出棧序列。【中科院中國科技大學2005】

A. 1、2、3、4 ? ? ? ? ? ? ? ? ? ? ?B. 4、 3、2、1

C. 1、3、4、2 ? ? ? ? ? ? ? ? ? ? ?D.４、1、2、3

選D

我是一個個模擬來做的。

?

描述棧的基本型性質：

1、集合性：棧是由若干個元素集合而成，沒有元素（空集）成為空棧。

2、線性：除棧頂和棧底之外，任意元素均有唯一前趨和后繼。

3、運算受限：只在一端插入刪除的線性表即為棧

?

順序存儲和順序存取：順序存取是只能逐個存或取結構中的元素，例如棧。順序存儲是利用一個連續的空間相繼存放，例如棧可基于一維數組存放元素。

?

一個較早入棧的元素能否在后面元素之前出棧？如果后面元素壓在它上面，就不可以了。如果后面元素未壓入，它可以彈出。在其他元素前面。

?

?

棧與遞歸：

? 當在一個函數的運行期間調用另一個函數時，在運行 該被調用函數之前，需先完成三件事： ?將實參等傳遞給被調用函數，保存返回地址（入棧）； ?為被調用函數的局部變量分配存儲區； ? ?將控制轉移到被調用函數的入口。 ?

從被調用函數返回調用函數之前，應該完成： ?保存被調函數的計算結果； ?釋放被調函數的數據區； ?按被調函數保存的返回地址（出棧）將控制轉移到調 ? ? ? ?用函數。

多個函數嵌套調用的規則是：后調用先返回。

?此時的內存管理實行“棧式管理”

?

隊列：

? ? ? ? 在多用戶計算機系統中，各個用戶需要使用 CPU 運行自己的程序，它們分別向操作系統提出使用 CPU 的請求，操作系統按照每個請求在時間上的先后順序， 將其排成一個隊列，每次把CPU分配給隊頭用戶使用， 當相應的程序運行結束，則令其出隊，再把CPU分配 給新的隊頭用戶，直到所有用戶任務處理完畢。

?

以主機和打印機為例來說明，主機輸出數據給打印 機打印，主機輸出數據的速度比打印機打印的速度要快 得多，若直接把輸出的數據送給打印機打印，由于速度 不匹配，顯然不行。解決的方法是設置一個打印數據緩 沖區，主機把要打印的數據依此寫到這個緩沖區中，寫 滿后就暫停輸出，繼而去做其它的事情，打印機就從緩 沖區中按照先進先出的原則依次取出數據并打印，打印 完后再向主機發出請求，主機接到請求后再向緩沖區寫 入打印數據，這樣利用隊列既保證了打印數據的正確， 又使主機提高了效率。

?

雙端隊列：

某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，若元素a,b,c,d,e依次入隊列后，再進行出隊操作，則不可能得到的順序是（ ）。?

A. bacde ? ? ? ? ? ? ? ?B. dbace ? ? ? ? ? ? ?C. dbcae ? ? ? ? ? ? ? ?D. ecbad

解析：出隊只能一端，所以abcde一定是這個順序。

反模擬入隊，每次只能在兩邊出元素。