第三章_棧和隊列

1、數(shù)據(jù)結構與算法設計（數(shù)據(jù)結構與算法設計（Java版）版）第1章 緒論第2章 線性表第3章 棧與隊列第4章 串第5章 數(shù)組第6章 樹和二叉樹第7章 圖第8章 排序第第3章章 棧和隊列棧和隊列3.1 棧棧3.2 隊列隊列 目的：目的：使用?；蜿犃星蠼鈶脝栴}。使用?；蜿犃星蠼鈶脝栴}。 要求：要求：掌握棧和隊列抽象數(shù)據(jù)類型，以及順掌握棧和隊列抽象數(shù)據(jù)類型，以及順 序和鏈式存儲結構實現(xiàn)；理解對于怎序和鏈式存儲結構實現(xiàn)；理解對于怎 樣的應用問題，需要使用?；蜿犃?，樣的應用問題，需要使用棧或隊列， 以及怎樣使用。以及怎樣使用。 重點：重點：棧和隊列的設計和應用。棧和隊列的設計和應用。 難點：難點：?；蜿?/p>

2、列的使用場合，以及如何使用?；蜿犃械氖褂脠龊?，以及如何使用 棧和隊列求解應用問題。棧和隊列求解應用問題。3.1 棧棧3.1.1 棧抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型3.1.2 順序棧順序棧3.1.3 鏈式棧鏈式棧3.1.4 棧的應用棧的應用3.1.1 棧抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型棧（棧（stack）是一種特殊的線性表，）是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進行。其插入和刪除操作只允許在線性表的一端進行。 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; /棧頂元素下標棧頂元素下標3.1.3 鏈式棧鏈式棧public class LinkedStack implements SStack private Node top;3.1.4 棧的應用棧的應用1.棧是嵌套調用機制的實現(xiàn)基礎棧是嵌套調用機制的實現(xiàn)基礎 2.使用棧以非遞歸方式實現(xiàn)遞歸算法使用棧以非遞歸方式實現(xiàn)遞歸算法 例例3.1 判斷表達式中

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

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

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

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