|
|
教學(xué)公告
理論課:
講解第3章的內(nèi)容 70-90頁
重點
1、棧的順序存儲結(jié)構(gòu)
2、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（循環(huán)隊列）
3、棧和隊列的操作特性
4、棧和隊列的應(yīng)用
大家可以根據(jù)自己的情況進(jìn)行相應(yīng)的預(yù)習(xí)
師說
棧最大的特點是先進(jìn)后出（LIFO），最先進(jìn)去的數(shù)據(jù)最后出來，而隊列（Quene）其操作特性是先進(jìn)先出（FIFO）,最先進(jìn)去的數(shù)據(jù)最先出來，棧和隊列都是線性表。棧和隊列的共同點是只允許在端點處插入和刪除元素。
日常生活中隊列很常見。還有什么棧的典型例子?
夏天逛超市時，你可能會忍不住想喝一瓶冰飲料降降溫。
可是，困擾你的是:放冰箱外頭的飲料往往并不冰，而冰箱深處你夠不著的地方，才是你想要的。
想想看:冰箱中的飲料應(yīng)該組織成“隊列”還是“棧”?你對超市中的冰箱設(shè)計有什么改進(jìn)性的建議?
比如交試卷，假設(shè)學(xué)生交試卷的方向都統(tǒng)一，且后來的學(xué)生都放在先來學(xué)生試卷之上。
如果都是正面朝上交，那么就是一個棧。
如果都是正面朝下交，那么就是一個隊列。
跟冰箱一個例子的還有坐電梯，先進(jìn)后出。交作業(yè)，先交的放在下面。彈匣就是棧。
冰箱中的飲料應(yīng)該組織成“隊列”；可以設(shè)計成像自動售貨機(jī)一樣豎直擺放的，從最上面放入，從最下面拿??；我們常見的冰箱應(yīng)該是棧，先進(jìn)后出。
而如果需要盡可能的能拿到最冰的則需要隊列，先進(jìn)先出。
關(guān)于棧與隊列的面試題
1、兩個棧實現(xiàn)一個隊列
2、兩個隊列實現(xiàn)一個棧
3、一個數(shù)組實現(xiàn)兩個棧
4、實現(xiàn)一個棧，能夠push、pop、min（求棧中最小的數(shù)據(jù)）
