|
|
教學公告
22軟工 第4周安排
[作者：
楊桂芝 發布時間：2023-09-26 17:00:51 瀏覽次數：1322次]
理論課:
講解第3章的內容 70-90頁
重點
1、棧的順序存儲結構
2、隊列的鏈式存儲結構（循環隊列）
3、棧和隊列的操作特性
4、棧和隊列的應用
大家可以根據自己的情況進行相應的預習
師說
棧最大的特點是先進后出（LIFO），最先進去的數據最后出來，而隊列（Quene）其操作特性是先進先出（FIFO）,最先進去的數據最先出來，棧和隊列都是線性表。棧和隊列的共同點是只允許在端點處插入和刪除元素。
日常生活中隊列很常見。還有什么棧的典型例子?
夏天逛超市時，你可能會忍不住想喝一瓶冰飲料降降溫。
可是，困擾你的是:放冰箱外頭的飲料往往并不冰，而冰箱深處你夠不著的地方，才是你想要的。
想想看:冰箱中的飲料應該組織成“隊列”還是“棧”?你對超市中的冰箱設計有什么改進性的建議?
比如交試卷，假設學生交試卷的方向都統一，且后來的學生都放在先來學生試卷之上。
如果都是正面朝上交，那么就是一個棧。
如果都是正面朝下交，那么就是一個隊列。
跟冰箱一個例子的還有坐電梯，先進后出。交作業，先交的放在下面。彈匣就是棧。
冰箱中的飲料應該組織成“隊列”；可以設計成像自動售貨機一樣豎直擺放的，從最上面放入，從最下面拿取；我們常見的冰箱應該是棧，先進后出。
而如果需要盡可能的能拿到最冰的則需要隊列，先進先出。
關于棧與隊列的面試題
1、兩個棧實現一個隊列
2、兩個隊列實現一個棧
3、一個數組實現兩個棧
4、實現一個棧，能夠push、pop、min（求棧中最小的數據）
