第三章_棧和隊(duì)列

1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)（數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)（Java版）版）第1章 緒論第2章 線性表第3章 棧與隊(duì)列第4章 串第5章 數(shù)組第6章 樹和二叉樹第7章 圖第8章 排序第第3章章 棧和隊(duì)列棧和隊(duì)列3.1 棧棧3.2 隊(duì)列隊(duì)列 目的：目的：使用?；蜿?duì)列求解應(yīng)用問題。使用?；蜿?duì)列求解應(yīng)用問題。 要求：要求：掌握棧和隊(duì)列抽象數(shù)據(jù)類型，以及順掌握棧和隊(duì)列抽象數(shù)據(jù)類型，以及順 序和鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)；理解對于怎序和鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)；理解對于怎 樣的應(yīng)用問題，需要使用?；蜿?duì)列，樣的應(yīng)用問題，需要使用?；蜿?duì)列， 以及怎樣使用。以及怎樣使用。 重點(diǎn)：重點(diǎn)：棧和隊(duì)列的設(shè)計(jì)和應(yīng)用。棧和隊(duì)列的設(shè)計(jì)和應(yīng)用。 難點(diǎn)：難點(diǎn)：?；蜿?duì)

2、列的使用場合，以及如何使用?；蜿?duì)列的使用場合，以及如何使用 棧和隊(duì)列求解應(yīng)用問題。棧和隊(duì)列求解應(yīng)用問題。3.1 棧棧3.1.1 棧抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型3.1.2 順序棧順序棧3.1.3 鏈?zhǔn)綏ｆ準(zhǔn)綏?.1.4 棧的應(yīng)用棧的應(yīng)用3.1.1 棧抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型棧（棧（stack）是一種特殊的線性表，）是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進(jìn)行。其插入和刪除操作只允許在線性表的一端進(jìn)行。 public interface SStack boolean isEmpty(); /判斷是否空棧判斷是否空棧 boolean push(E element); /入棧入棧 E

3、pop(); /出棧出棧 E get(); /取棧頂元素值取棧頂元素值3.1.2 順序棧順序棧public class SeqStack implements SStack private Object value ; private int top; /棧頂元素下標(biāo)棧頂元素下標(biāo)3.1.3 鏈?zhǔn)綏ｆ準(zhǔn)綏ublic class LinkedStack implements SStack private Node top;3.1.4 棧的應(yīng)用棧的應(yīng)用1.棧是嵌套調(diào)用機(jī)制的實(shí)現(xiàn)基礎(chǔ)棧是嵌套調(diào)用機(jī)制的實(shí)現(xiàn)基礎(chǔ) 2.使用棧以非遞歸方式實(shí)現(xiàn)遞歸算法使用棧以非遞歸方式實(shí)現(xiàn)遞歸算法 例例3.1 判斷表達(dá)式中

4、圓括號是否匹配判斷表達(dá)式中圓括號是否匹配例例3.2 使用棧計(jì)算表達(dá)式的值。使用棧計(jì)算表達(dá)式的值。中綴表達(dá)式中綴表達(dá)式1+2*(3-4)+51.將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式2.后綴表達(dá)式求值后綴表達(dá)式求值 3.2 隊(duì)列隊(duì)列3.2.1 隊(duì)列抽象數(shù)據(jù)類型隊(duì)列抽象數(shù)據(jù)類型3.2.2 順序隊(duì)列順序隊(duì)列3.2.3 鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列3.2.4 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用3.2.1 隊(duì)列抽象數(shù)據(jù)類型隊(duì)列抽象數(shù)據(jù)類型隊(duì)列（隊(duì)列（queue）是一種特殊的線性表，其插入和刪除）是一種特殊的線性表，其插入和刪除操作分別在線性表的兩端進(jìn)行。操作分別在線性表的兩端進(jìn)行。public interfac

5、e QQueue /隊(duì)列接口隊(duì)列接口 boolean isEmpty(); /判斷隊(duì)列是否為空判斷隊(duì)列是否為空 boolean enqueue(E element); /入隊(duì)入隊(duì) E dequeue(); /出隊(duì)出隊(duì) 3.2.2 順序隊(duì)列順序隊(duì)列1.順序隊(duì)列，假溢出順序隊(duì)列，假溢出 2.順序循環(huán)隊(duì)列順序循環(huán)隊(duì)列 front=(front+1) % length;rear=(rear+1) % length;3.順序循環(huán)隊(duì)列類順序循環(huán)隊(duì)列類 public class SeqQueue implements QQueue private Object value; private int fron

6、t,rear; /隊(duì)列頭尾下標(biāo)隊(duì)列頭尾下標(biāo)3.2.3 鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列public class LinkedQueue implements QQueue /鏈?zhǔn)疥?duì)列類鏈?zhǔn)疥?duì)列類 private Node front, rear; 3.2.4 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用例例3.3 求解素?cái)?shù)環(huán)問題。求解素?cái)?shù)環(huán)問題。 素?cái)?shù)：質(zhì)數(shù)（素?cái)?shù)：質(zhì)數(shù)（prime number）又稱素?cái)?shù)，有無）又稱素?cái)?shù)，有無限個(gè)。一個(gè)大于限個(gè)。一個(gè)大于1的的自然數(shù)自然數(shù)，除了，除了1和它本身外，和它本身外，不能被其他自然數(shù)不能被其他自然數(shù)整除整除（除（除0以外）的數(shù)稱之為素以外）的數(shù)稱之為素?cái)?shù)（質(zhì)數(shù)）；否則稱為數(shù)（質(zhì)數(shù)）；否則稱為

7、合數(shù)合數(shù)。根據(jù)。根據(jù)算術(shù)基本定理算術(shù)基本定理，每一個(gè)比每一個(gè)比1大的整數(shù)，要么本身是一個(gè)質(zhì)數(shù)，要么大的整數(shù)，要么本身是一個(gè)質(zhì)數(shù)，要么可以寫成一系列質(zhì)數(shù)的乘積；而且如果不考慮這些可以寫成一系列質(zhì)數(shù)的乘積；而且如果不考慮這些質(zhì)數(shù)在乘積中的順序，那么寫出來的形式是唯一的質(zhì)數(shù)在乘積中的順序，那么寫出來的形式是唯一的。最小的質(zhì)數(shù)是。最小的質(zhì)數(shù)是2。3.2.4 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用例例3.3 求解素?cái)?shù)環(huán)問題。求解素?cái)?shù)環(huán)問題。素?cái)?shù)環(huán)：素?cái)?shù)環(huán)： 將從將從1到到n這這n個(gè)整數(shù)圍成一個(gè)圓環(huán)，若個(gè)整數(shù)圍成一個(gè)圓環(huán)，若其中任意其中任意2個(gè)相鄰的數(shù)字相加，結(jié)果均個(gè)相鄰的數(shù)字相加，結(jié)果均為素?cái)?shù)，那么這個(gè)環(huán)就成為素?cái)?shù)環(huán)。為素?cái)?shù)，那么這個(gè)環(huán)就成為素?cái)?shù)環(huán)。使用順序表和順序隊(duì)列來解素