目錄

1.棧

1.1棧的概念及結(jié)構(gòu)

?1.2棧的實現(xiàn)

2.隊列

2.1隊列的概念及結(jié)構(gòu)

?2.2隊列的實現(xiàn)

2.3循環(huán)隊列

?3.棧和隊列的面試題

4.概念選擇題

1.棧

1.1棧的概念及結(jié)構(gòu)

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據(jù)插入和刪除的一端稱為棧頂，另一端稱為棧底。棧中數(shù)據(jù)元素遵守后進先出LIFO（Last In First Out）.

• 壓棧：棧的插入操作叫做 進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
• 出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

?1.2棧的實現(xiàn)

棧的實現(xiàn)一般可以用數(shù)組或者鏈表實現(xiàn)，相對而言數(shù)組的結(jié)構(gòu)實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據(jù)的代價比較小。

?? 數(shù)據(jù)結(jié)構(gòu)棧（Last In First Out）實現(xiàn)

2.隊列

2.1隊列的概念及結(jié)構(gòu)

隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)。

• 入隊列：進行插入操作的一端稱為隊尾；
• 出隊列：進行刪除操作的一端稱為隊頭；

2.2隊列的實現(xiàn)

隊列可以一數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上取數(shù)據(jù)，效率會很低。

數(shù)據(jù)結(jié)構(gòu)隊列（First In First Out）實現(xiàn)

2.3循環(huán)隊列

另外擴展了解一下，實際中我們有時還會使用一種隊列叫做循環(huán)隊列。如操作系統(tǒng)課程講解生產(chǎn)者消費模型時就會使用到循環(huán)隊列。環(huán)形隊列可以使用數(shù)組實現(xiàn)，也可以使用循環(huán)鏈表實現(xiàn)。文章來源地址http://www.zghlxwxcb.cn/news/detail-426850.html

3.棧和隊列的面試題

1. 括號匹配問題。答案
2. 用隊列實現(xiàn)棧。答案
3. 用棧實現(xiàn)隊列。答案
4. 設(shè)計循環(huán)隊列。答案

4.概念選擇題

1.一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出
棧的順序是（ ）。
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA

2.若進棧序列為 1,2,3,4 ，進棧過程中可以出棧，則下列不可能的一個出棧序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1

3.循環(huán)隊列的存儲空間為 Q(1:100) ，初始狀態(tài)為 front=rear=100 。經(jīng)過一系列正常的入隊與退隊操作
后， front=rear=99 ，則循環(huán)隊列中的元素個數(shù)為（ ）
A 1
B 2
C 99
D 0或者100

4.以下( )不是隊列的基本運算？
A 從隊尾插入一個新元素
B 從隊列中刪除第i個元素
C 判斷一個隊列是否為空
D 讀取隊頭元素的值

5.現(xiàn)有一循環(huán)隊列，其隊頭指針為front，隊尾指針為rear；循環(huán)隊列長度為N。其隊內(nèi)有效長度為？(假設(shè)
隊頭不存放數(shù)據(jù))
A (rear - front + N) % N + 1
B (rear - front + N) % N
C (rear - front) % (N + 1)
D (rear - front + N) % (N - 1)

1.B
2.C
3.D
4.B
5.B

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)3：棧和隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！