1. 前言

這門課程是之前INT102的進階，它介紹算法分析的基礎概念并且介紹算法的復雜度分析。

1.1 算法（Algorithms）和數據結構（Data Structure）

1.數據結構是一種系統化地組織和訪問數據的方式。通過合理地組織數據，可以提高數據的存儲效率、訪問速度和操作便利性。常見的數據結構包括數組、鏈表、棧、隊列、樹、圖等。
2.算法是在有限時間內完成某項任務的一系列步驟。算法是解決問題的具體方法，通過一系列邏輯步驟實現特定的功能或目標。不同的算法有不同的效率和適用場景。
例如：1.導航到某個地方需要使用算法來規劃從起點到終點的最佳路徑。
2.通過算法將音頻或視頻文件從一種格式轉換為另一種格式。
3.通過算法來控制太陽能板，從而最大化太陽能的利用效率。
4.通過算法將二維或三維模型渲染成圖像或視頻。
5.用于求解方程的根（即解）的算法。
6.用于減少文件大小的壓縮算法。
7.用于尋找最優解或近似最優解的優化算法。
8.用于將圖形或圖像數據轉換為最終視覺效果的算法。
我們在學習數據結構的時候我們也會經常提到算法，因為程序是算法和程序的結合體，兩者相輔相成。每種數據結構有其對應的算法，它們也有各自的使用場景。
比如數組有不同的排序算法，比如快速排序（Quick Sort）、歸并排序（Merge Sort）、冒泡排序（Bubble Sort）等。搜索方法有二分查找（Binary Search），它們有不同的使用場景。
再比如樹有不同的遍歷算法，圖有不同的遍歷算法。

1.2 什么是好的算法？

因為算法和數據結構相輔相成，所以好的算法也需要依賴高效的數據結構。在當前討論組，我們說的“好”是運行速度快的，這將在課程中進一步闡述。

1.3 算法分析

我們使用算法分析來評價一個算法的效率。
算法分析是對計算機程序性能和資源使用的理論研究。主要關注點是算法的運行時間（時間復雜度）以及對數據結構的操作。次要關注點是算法的空間（或“內存”）使用（空間復雜度）。
本課程專注于算法及其相關數據結構的數學設計與分析，并使用相關的數學工具來實現這一目標。

我們關注運行時間或內存需求與輸入規模之間的依賴關系。
輸入規模的定義取決于具體問題的背景。例如：
在圖算法中，輸入規模通常用頂點數（V）和邊數（E）表示。
在字符串處理中，輸入規模通常用字符串的長度表示。
在數值計算中，輸入規模可以用數字的位數表示。

1.3.1 實驗分析（Experimental Analysis）

為了分析算法，我們有時通過實驗分析來分析算法，通過實際運行算法來測量其性能，而不是僅僅依賴于理論分析。這種方法可以幫助我們了解算法在實際數據上的表現，尤其是在理論分析難以準確預測的情況下。但進行實驗性分析需要合理選擇樣本輸入，并進行適當數量的測試，以便我們能夠對分析結果有統計上的信心。

由于運行時間取決于輸入的規模和具體實例，以及使用的算法和運行的環境。其中輸入的規模不難理解，對于具體實例會因為輸入的具體實例不同，即使規模相同，也可能導致運行時間不同。例如對于冒泡排序來說，已排序的數組的時間復雜度是$O(n)$，對于完全隨機的數組的時間復雜度是$O(n^2)$。
一般來說，算法或數據結構方法的運行時間會隨著輸入規模的增加而增加。


因此對于實驗分析來說有以下幾點需要注意：
1.實驗是在有限的測試輸入集上進行的。
2.所有測試必須在相同的硬件和軟件環境下進行。
3.需要實現并運行算法。

1.3.2 理論分析

理論分析與實驗分析相比有以下優勢：
1.可以考慮所有可能的輸入。
2.可以在不依賴硬件/軟件環境的情況下，比較兩個（或更多）算法的效率。
3.涉及研究算法的高級描述——偽代碼（pseudo-code）。

當我們以這種方式分析算法時，我們的目標是為每個算法關聯一個函數$f(n)$，其中$f(n)$表征了運行時間，這是基于輸入大小$n$的某種度量。
這種$f(n)$函數的典型有：$n$，$logn$，$n^2$，$nlogn$，$2^n$…
用這種方式我們可以將算法運行的時間表示出來，因為算法$A$的運行時間與$n$成正比，因此$f(n)=kn$，其中$k$是一個常數，每增加一個單位的輸入規模，運行時間就增加$k$個單位。

為了完成理論分析需要四個要素：
1.描述算法的語言，即偽代碼我們后面會再復習一遍。
2.算法執行的計算模型，常見的包括圖靈機，以及后文復習的隨機訪問機器（RAM）。
3.衡量性能的度量標準，即時間復雜度和空間復雜度。
4.描述性能的方法， 我們可以使用Big-Oh符號等來描述，后文也會復習。

我們前面就說過一個算法會因為輸入的具體實例不同而有不同的運行時間。因此有平均情況復雜度（Average-case complextiy)和最壞情況情況復雜度（Worst-case complextiy)
平均情況復雜度指的是在所有相同規模的輸入中，算法運行時間的平均值。
最壞情況復雜度指的是在所有相同規模的輸入中，算法運行時間的最大值。
平均情況復雜度反映了算法在大多數情況下的性能，而最壞情況復雜度則提供了算法在最不利情況下的性能保證。由于最壞情況復雜度對于確保系統穩定性和可靠性的重要性，我們通常更關注它。
對于平均情況分析通常需要我們基于給定的輸入分布來計算預期的運行時間。

1.3.2.1 偽代碼（Pseudo-code）

偽代碼是一種用于描述算法的高級語言。
它提供了更結構化的算法描述，允許我們對算法進行高級分析，以確定它們的運行時間（和內存需求）。
下面的例子用偽代碼編寫了一個找到一組數字中最小數字的代碼。

Algorithm Minimum-Element(A)  
input: An array A sorting n≥1 integers  
output: minimum element min
min ← A[0]
for i ← 1 to n-1 doif min > A[i] then  min ←A[i]
return min

其中我們也可以使用等號代替←，也可以使用大括號來代替if-then-end結構。

從上面的例子中我們也可以看出，偽代碼不像傳統的編程語言對語法格式有所要求，它是自然語言和高級編程語言（例如 Java、C 等）的混合體。偽代碼的目的是提供一個通用的、與特定編程語言無關的算法或數據結構實現描述。
偽代碼包括：表達式、聲明、變量初始化和賦值、條件語句、循環、數組、方法調用等。
這門課中，不會正式定義一個嚴格的偽代碼編寫方法，但當需要使用它時，我們的目標是以一種方式描述算法，使一個稱職的程序員能夠將偽代碼轉換為程序代碼，而不會誤解算法。（換句話說這門功課不會要求寫偽代碼，但是需要能夠理解偽代碼描述的算法是哪種）。
偽代碼忽略了底層的實現細節，它由一些列高級原始操作，包括賦值、調用方法、執行算術操作、比較、通過索引訪問元素、引用、返回等。然后為了分析算法的運行時間，我們計算算法執行過程中執行的操作數量。

示例如下：對于如下偽代碼我們可以計算算法中執行的原始操作有多少次。

 Algorithm arrayMax(A,n):input: array Aoutput: maximum element currentMaxcurrentMax ← A[0]for j ← 1 to n-1 doif currentMax<A[j]then currentMax ← A[j]returncurrentMax

對于第一行，我們通過索引讀取數組里的值，然后再賦值，因此是$2$次。
第二行我們先賦值一次，然后我們會比較$n$次，$1<n$，所以是$n+1$次。
第三行我們通過索引讀取數組里的值，然后再比較，因此是$2(n?1)$次。
第四行中如果我們的值每次要更新那就會運行$2(n?1)$次，索引讀取和賦值，但是如果我們賦值的就是最大的值。
之后我們其實需要讓j自增1，這一步是一次算術和一次賦值，因此是$2(n?1)$次。
最后返回值$1$次。
最好情況：$2+1+n+4(n?1)+1=5n$。
最壞情況：$2+1+n+6(n?1)+1=7n?2$。
由于數操作數沒有一個標準，因此考試也不會考察該部分。

下面我們再看一個遞歸算法。
例如$T(n)=3,n=1;T(n)=T(n?1)+7,n\ge 2$，我們可以將其遞歸關系轉換為封閉形式$T(n)=7T(n?1)+3=7n?4$。
了解基本的遞歸算法后我們可以嘗試一下斐波拉契數列，嘗試寫出它的偽代碼。
示例如下。

Algorithm: fibonacci numbers  
Input: upper limit n
Output: The n-th term of Fibonacci  
int fib (int n){
if n <=2  return 1;
elsereturn fib(n-1)+fib(n-2);
}

我們之前就學過遞歸算法，雖然遞歸算法在某些情況下可能看起來更簡單，但它們也可能引入一些問題。比如重復解決子問題，遞歸算法將大問題分解為小問題，而這些小問題可能在遞歸調用過程中被多次遇到。
如下圖所示。

計算第六項的時候計算了前面的第三項三次。所以如果輸入值較大時，可能因為大量重復計算而導致棧空間迅速增加，最終超出計算機的內存限制。
我們可以使用動態規劃（Dynamic Programming）方法避免每個子問題進行了多次計算。
動態規劃的斐波拉契數列偽代碼如下。

Algorithm: fibonacci numbers  
Input: upper limit Nmax
Int f(int Nmax)
{
f1 ←1;
f2 ←1;
for n←3:(Nmax-2){  fn← f2 + f1;f1 ←f2;  f2 ←fn;}
return fn;
}

1.3.2.2 隨機訪問機器（Random Access Machine）

隨機訪問機器是一種計算模型，通過簡化計算機的操作來便于分析。
在RAM模型中，計算機由一個中央處理單元（CPU）和一個存儲單元組（內存）組成。CPU負責執行計算和控制操作，而內存用于存儲數據。其中內存單元是基本的存儲單位，可以存儲不同類型的數據，如整數、浮點數、字符或內存地址。這種靈活性使得RAM模型能夠模擬各種計算機操作。
我們假設原始操作（如單個加法、乘法或比較）需要恒定的時間來執行，即無論操作數的大小如何，這些操作的執行時間都是相同的。雖然 RAM 模型假設所有基本操作都需要恒定時間，但實際上，不同操作的執行時間可能不同。例如，乘法通常比加法需要更多的時間來執行。這種假設簡化了算法分析，但可能不完全反映真實計算機的性能。

1.3.2.3 時間復雜度（Time omplexity）

時間復雜度關注的是算法運行時間隨著輸入規模趨近于無窮大時的變化趨勢，而不是具體的運行時間。通常用下面我們說的漸進符號來表示其變化趨勢。

1.3.2.4 漸進符號（Asymptotic notation）

我們使用漸進符號描述算法運行時間或其他資源需求隨著輸入規模增長的變化趨勢。因此我們可以實驗漸進符號來比較兩個算法的運行時間。在算法分析中，漸近符號用于簡化分析過程。它估計執行的原始操作數量，但只考慮常數因子。這意味著我們關注的是算法運行時間的主導項，而不是常數乘數。
下圖展示了對于不同算法運行時間對應的最大問題規模$（n）$。

從長遠角度來看，漸進較快的算法優于漸進較慢的算法。這里漸進更快指的是在后續的Big-Oh符號等漸進符號中，前者的增長速率低于后者。例如，一個具有$O(logn)$時間復雜度的算法比具有$O(n)$時間復雜度的算法“漸進更快”，因為對數函數的增長速率遠低于線性函數。

我們現在復習以下函數的增長率。
對于多項式函數來說：
線性函數（Linear），增長率與輸入規模$n$成正比，表示為$n$。
二次函數（Quadratic），增長率與輸入規模$n$的平方成正比，表示為$n^2$。
三次函數（Cubic），增長率與輸入規模$n$的立方成正比，表示為$n^3$。
我們現在使用對數-對數圖來比較不同函數的增長率，因為它可以將指數增長或多項式增長的函數轉換為直線。

在分析增長率時，我們通常關注算法的主導項（即最高次項），因為它們對算法在大規模輸入下的性能影響最大。因此我們忽略常數因子（constant factors），例如$10n$和$100n$的常數不同，但都被認為是線性增長。我們還會忽略低階項（Lower-Order Terms），例如$n^2+n$中的$n$就是低階項。

前面我們說過理論分析是找到描述算法運行時間與輸入規模之間的關系，這個函數也就是這里用來表達算法的漸進行為，我們用漸進符號來描述這種漸進行為。

1.3.2.4.1 大O符號（Big-Oh Notation）

大O符號（Big-Oh Notation）是描述算法運行時間或其他資源消耗上界的一種常用漸近符號。它讓我們能夠以一種標準化的方式表達算法在最壞情況下的性能。
其定義如下：
給定兩個正函數$f(n)$和$g(n)$（它們都是在非負整數上定義的），我們說$f(n)$是$O(g(n))$，記作$f(n)\in O(g(n))$，如果存在常數$c$和$n_0$使得$f(n)\le c?g(n)$對所有$n\ge n_0$成立。
例如：$2n+10$用大O符號描述為$O(n)$
過程如下：
$2n+10\le cn$
$(c?2)n\ge 10$
$n\ge 10/(c?2)$
取$c=3，n_0=10$即可滿足$2n+10\le 3n$對所有$n\ge 10$，因此$2n+10$用大O符號描述為$O(n)$。

我們前面說大O符號描述算法的運行時間或空間復雜度的上界，因此對于函數$n^2$其大O符號表示不是$O(n)$。
證明過程如下：
$n^2\le cn$
$n\le c$
上述不等式不能被滿足，因為$c$必須是一個常數。要使$n\le c$對所有$n$都成立，$c$必須大于或等于所有可能的$n$，這是不可能的，因為$n$可以無限增大。
或者說$n^2$的增長速度比$n$快，所以$O(n^2)$的運行時間會比$O(n)$慢。

下圖展示了多種函數的增長速度，從左到右速度不斷增加。

更多的例子如：
$7n?2$的大O符號是$O(n)$，$c=7，n_0=1$。
$3n^3+20n^2+5$的大O符號是$O(n^3)$，$c=4，n_0=21$。

我們對增長速度做出進一步解釋，“$f(n)$是$O(g(n))$”的聲明意味著$f(n)$的增長率至多與$g(n)$的增長率一樣快。
通過大O符號，我們可以根據增長率對函數進行排序。
下圖進一步展示了剛剛說的這兩點。

外面的函數的增長速度小于等于$O$里面的函數。

對于我們的日常函數的大O符號如下：
1.常數:$O(1)$
2.對數函數:$O(logn)$
3.線性函數:$O(n)$
4.線性對數函數:$O(nlogn)$
5.二次函數:$O(n^2)$
6.三次函數:$O(n^3)$
7.多項式函數:$O(n^k)$
8.指數函數:$O(a^{n}0),a>1$
9.階乘函數:$O(n!)$

如果$f(n)$是一個次數為$d$的多項式，那么$f(n)$是$O(n^d)$。我們只需要關注最高次項，忽略低次項和常數因子。
此外還有兩點需要注意：
1.選擇能最準確描述函數增長速度的最小可能的函數類別。
例如：對于$2n$的大O符號是$O(n)$而不是$O(n^2)$。
2.選擇最簡單的表達式來表示函數類別。
例如：對于$3n+5$的大O符號是$O(n)$而不是$O(3n)$。

因此更多例子如下：
1.$13n^3+7nlogn+3$的大O符號是$O(n^3)$
2.$3logn+loglogn$的大O符號是$O(logn)$因為$3logn+loglogn\le 4logn$當$n\ge 2$時。
3.$2^{70}$的大O符號是$O(1)$
對于第三個的證明如下：$2^{70}\le 2^{70}?1$，對于$n\ge 1$都成立。

我們使用漸進算法進行分析時，我們先確定算法在最壞情況下執行的原始操作（如比較、賦值等）的數量，并將這個數量表示為輸入規模 n 的函數。然后使用大O符號來描述算法運行時間的上界。
我們以查找數組中最大元素的算法為例，前面我們數過這個算法的原始操作的次數為$7n?2$。因此我們就說這個算法的運行時間為$O(n)$。

Algorithm prefixAverage1(X,n)Input array X of n integersOutput array A of prefix averages of XA ← new array of n integersfor i ← 0 to n - 1 dos ← X[0]for j ← 1 to i dos ← s + X[j]A[i] ← s / (i+1)return A

由于這里使用了求和，所以根據求和公式，想要計算n個整數的和，通過求和公式$n(n+1)/2$，因此它的運行時間為$O(n^2)$。
或者我們看這里是由一個循環在另一個循環里面，因此是$O(n^2)$。

下面這個算法中并不是每次都要單獨計算前$n$個數的和，而是直接每次在前一次和上加最新一項，因此這里的運行時間為$O(n)$。

Algorithm prefixAverage2(X,n)Input array X of n integersOutput array A of prefix averages of XA ← new array of n integerss ← 0for i ← 0 to n - 1 dos ← s + X[i]A[i] ← s / (i + 1)return A

因此這里只有一次循環。

下面多給幾個例子：

s ← 0
for i ← 1 to n dos ← s + i

時間復雜度為$O(n)$。

p ← 1
for i ← 1 to 2n dop ← p * i

時間復雜度為$O(n)$。

p ← 1
for i ← 1 to n^2 dop ← p * i

時間復雜度為$O(n^2)$。因為循環是從$1$到$n^2$。

s ← 0
for i ← 1 to 2n dofor j ← 1 to i dos ← s + i

時間復雜度為$O(n^2)$。因為是嵌套循環。

1.3.2.4.2 大Ω符號（Big-Omega Notation）

我們說$f(n)$是$\Omega (g(n))$，如果存在實數常數$c$和$n_0$，使得所有$n\ge n_0$，都有$f(n)\ge cg(n)$。

1.3.2.4.3 大Θ符號（Big-Theta Notation）

我們說$f(n)$是$\Theta (g(n))$，如果$f(n)$既是$O(g(n))$又是$\Omega (g(n))$。這意味著$f(n)$的增長速率與$g(n)$完全相同，即$f(n)$既不超過$g(n)$的某個常數倍的增長速率，也不低于$g(n)$的某個常數倍的增長速率。

因此我們現在總結這三種漸進符號。
1.大O符號（Big-Oh）
如果$f(n)$是$O(g(n))$，這意味著$f(n)$的增長速率在漸近意義上小于或等于$g(n)$的增長速率。換句話說，隨著輸入規模$n$的增大，$f(n)$的增長不會超過$g(n)$的某個常數倍。
2.大Ω符號（Big-Omega）
如果$f(n)$是$\Omega (g(n))$，這意味著$f(n)$的增長速率在漸近意義上大于或等于$g(n)$的增長速率。也就是說，隨著輸入規模$n$的增大，$f(n)$的增長至少和$g(n)$的某個常數倍一樣快。
3.大Θ符號（Big-Theta）
如果$f(n)$是$\Theta (g(n))$，這意味著$f(n)$的增長速率在漸近意義上等于$g(n)$的增長速率。換句話說，隨著輸入規模$n$的增大，$f(n)$的增長速率與$g(n)$的增長速率完全相同。

示例如下：
$3logn+loglogn$的時間復雜度是$\Omega (logn)$。因為$3logn+loglogn\ge 3logn$當$n\ge 2$時。
前面我們也得到過$3logn+loglogn$的時間復雜度是$O(logn)$。
因此我們可以得到$3logn+loglogn$的時間復雜度是$\Theta (logn)$。

1.3.2.5 空間復雜度（Space Complexity）

空間復雜度是衡量算法所需的存儲空間量的一個指標。具體來說，它指的是在算法的任何時刻，在最壞情況下需要多少內存。
與時間復雜度類似，我們主要關注的是隨著輸入問題規模$N$的增長，空間需求如何增長，用大O符號來表示。
例子如下：

int sum(int x, int y, int z) {  
int r = x + y + z;return r;}

這個算法需要三個單位的空間用于參數以及一個單位的空間用于局部變量，并且這個空間需求是固定的與輸入規模$N$無關，因此它的空間復雜度是$O(1)$。

int sum(int a[], int n) {  
int r = 0;
for (int i = 0; i < n; ++i) {  r += a[i];}
return r;
}

這個算法需要$N$個單位的空間用于數組a，以及n，r和i分別一個單位的空間，因此它的空間復雜度是$O(n)$。

2. 數據結構

我們現在講數據結構。

首先我們重申一遍數據結構的重要性：
1.算法的執行依賴于數據（信息）。
2.算法計算的速度部分取決于對數據的高效使用。
3.數據結構是存儲和訪問信息的特定方法。
4.我們研究不同類型的數據結構，可以根據特定算法的需求尋找其合適的數據結構。

2.1 Stacks（棧）

棧是一種遵循“后進先出”（Last-in，First-Out，簡稱LIFO）的數據結構。這意味著最后被添加到棧中的元素將是第一個被移除的元素。
因此我們直接訪問的元素只能是最后一個被插入的元素，即棧頂元素。
但是可以在任何時候向棧中添加元素，只要棧沒有溢出（即沒有達到其最大容量限制）。而新元素是被添加到棧的棧頂。
例如，Web 瀏覽器使用棧來存儲最近訪問的網頁地址。當你點擊瀏覽器的“后退”按鈕時，瀏覽器從棧中彈出（Pop）最頂部的地址，即最后訪問的網頁，然后顯示該網頁。

2.1.1 相關方法

棧（Stacks）作為一種抽象數據類型（Abstract Data Type，簡稱 ADT），下面列出其支持的一些基本操作和方法。
1.push(Obj)：將對象 Obj 插入到棧的頂部。
2.pop()：移除（并返回）棧頂部的對象。如果棧為空，則該操作會觸發錯誤或異常。
3.initialize()：初始化棧，通常將棧設置為一個空狀態。
4.isEmpty()：返回 true 如果棧為空，否則返回 false。
5.isFull()：返回 true 如果棧已滿，否則返回 false。

對于基礎操作的push和pop的偽代碼如下：

PUSH(Obj)
# Check to see if stack is full
if size() == Nthen indicate "stack-full" error occurred
else t ← t + 1S[t] ← Obj

POP()
# Check to see if stack is empty
if isEmpty()then indicate "stack empty" error occurred
else Obj ← S[t]S[t] ← nullt ← t - 1
return Obj

具體push和pop操作過程如下圖所示。

2.1.2 應用

棧在現代過程式編程語言（例如 C、C++、Java 等）的運行時環境中非常重要。這是因為這些語言通常使用棧來管理函數調用、局部變量和控制流語句（如循環和條件語句）。在函數調用時，每個函數的參數、返回地址和局部變量通常被壓入（push）調用堆棧（call stack）中。當函數執行完畢后，這些信息被彈出（pop）堆棧，程序控制返回到調用函數。
此外，表達式求值、編譯器優化和內存管理等許多底層操作也依賴于棧結構。
如果使用算式表達式使用的是后綴表達式（postfix notation，也稱反向波蘭表達式，Reverse Polish notation（RPN））則可以使用棧來計算。

2.1.2.1 翻轉數組

我們前面在別的課中也學習了如何講數組里的值翻轉一遍，現在我們使用棧來解決這個問題我們會發現，棧做這種事非常適合。

ReverseArray(Data: values[])// Push the values from the array onto the stack.  Stack: stack = New StackFor i = 0 To <length of values> - 1  stack.Push(values[i])Next i// Pop the items off the stack into the array.For i = 0 To <length of values> - 1  values[i] = stack.Pop()Next i
End ReverseArray

剛好我們從頭開始讀取數組里的每一項，由于FILO，我們最先放進的值就將最后一個被讀出來因此就實現了數組的翻轉。

2.1.2.2 后綴表達式/反向波蘭表達式（Postfix notation， Reverse Polish notation）

在后綴表達式中，操作數（如變量或數字）位于算術運算符之前，當遇到一個運算符時，它應用于之前遇到的兩個操作數。例如，中綴表達式$x+y$在后綴表達式中寫作$xy+$,中綴表達式$(x+y)?z$在后綴表達式中寫作$xy+z?$,中綴表達式$x?(y+z)$在后綴表達式中寫作$xyz+?$，中綴表達式的$?x$的后綴表達式寫作$x?1?$。
同理我們也可以用后綴表達式也可以轉化為中綴表達式，后綴表達式的$xywz/??$寫成中綴表達式為$x?(y/w?z)$。

下圖展示了如何用棧處理后綴表達式。
步驟如下：
1.遇到操作數就將其壓入棧中。
2.遇到操作符就從棧中彈出所需的操作數，執行運算，并將結果壓回棧中。
3.最終，棧頂元素即為表達式的結果。

第一個元素是$7$，所以壓入棧中。
第二個元素是$5$，也壓入棧中。
第三個元素是$3$，也壓入棧中。
第四個元素是$+$，因此彈出兩個操作數出來，執行計算為$3+5$，得到$8$后再壓入棧中。
第五個元素是$?$，因此彈出兩個操作數出來，執行計算為$8?7$，得到$56$后再壓入棧中。
因此現在棧頂元素56就是表達式的結果。

后面兩張圖展示了更多例子。


如果對中綴轉后綴之類的轉換還不理解，可以看以下視頻。
中綴表達式轉前綴/后綴表達式

經過前面的學習我們現在可以總結以下后綴表達式的優點：
1.在后綴表達式中，沒有運算符優先級的概念，因為運算符總是跟在它所操作的操作數之后。這意味著表達式中的運算符從左到右的順序就是它們被執行的順序。
2.后綴表達式實際上模仿了我們計算“通常”（即中綴）表達式的方式。在中綴表達式中，我們從左到右讀取表達式，遇到運算符時，按照從左到右的順序應用之前的兩個操作數。
3.后綴表達式消除了使用括號的需要（前提是我們不會將減法運算符與負數中的“-”符號混淆），因為運算符的順序已經由它們在表達式中的位置確定。因此，計算機在讀取和處理數字時，正確的格式和處理非常重要。

2.1.2.3 迷宮問題等搜索問題

考慮一只被困在迷宮中的老鼠，它試圖找到通往出口的路徑。迷宮通常可以用二維數組表示，其中每個單元格點可以是通道（通常用0表示）或墻（用1表示）。
如圖所示。

我們現在利用棧寫一個程序來解決關于下面這個簡單迷宮問題。

exitMaze()
initialize stack, exitCell, entryCell, currentCell = entryCell;  
while currentCell is not exitCellmark currentCell as visited;push onto the stack the unvisited neighbors of currentCell;If stack is emptyfailure;else pop off a cell from the stack and make it  currentCell;
success;

迷宮如下。

下圖展示了用剛剛的代碼解決這個問題的過程。

m表示老鼠位置，老鼠剛開始位于（3，3），不是終點，因此將其標為來過的，然后將周圍的未來過的地方壓進棧，即（2，3）和（3，2）。
因此我們接下來推出一個新的位置作為當前老鼠的位置，因此老鼠當前位置是（3，2），不是終點，因此將其標為來過的，然后將周圍的未來過的地方壓進棧，即（2，2）和（3，1）。
我們接下來再推出一個新的位置作為當前老鼠的位置，因此老鼠當前位置是（3，1），不是終點，因此將其標為來過的，然后將周圍的未來過的地方壓進棧，即（2，1）。
我們接下來再推出一個新的位置作為當前老鼠的位置，因此老鼠當前位置是（2，1），不是終點，因此將其標為來過的，然后將周圍的未來過的地方壓進棧，即（2，2）。
我們接下來再推出一個新的位置作為當前老鼠的位置，因此老鼠當前位置是（2，2），不是終點，因此將其標為來過的，然后將周圍的未來過的地方壓進棧，即（2，3）。
我們接下來再推出一個新的位置作為當前老鼠的位置，因此老鼠當前位置是（2，3），不是終點，因此將其標為來過的，然后將周圍的未來過的地方壓進棧，即（1，3）和（2，4）。
我們接下來再推出一個新的位置作為當前老鼠的位置，因此老鼠當前位置是（2，4），是終點，可以逃出迷宮。

2.2 隊列（Queues）

隊列是一種遵循先進先出（First-In, First-Out）原則的數據結構，類似于我們在現實世界中使用的隊列，如排隊等候服務。
同樣我們可以在任何適合再隊列的尾部（rear）插入對象，這種操作通常稱為入隊（enqueue）。
但是只有隊列首部（front）的元素可以被移除，這種操作通常稱為出隊（dequeue）。
元素從隊列的尾部進入，從隊列的前部被移除。
一個常見的隊列應用示例是打印機任務隊列。多個打印任務被發送到打印機，它們按照到達的順序排隊等候打印。

2.2.1 相關方法

隊列（Queues）作為一種抽象數據類型（Abstract Data Type，簡稱 ADT），下面列出其支持的一些基本操作和方法。
1.enqueue(Obj)：這個方法用于在隊列的尾部（rear）插入一個對象（Obj）
2.dequeue()：這個方法用于移除并返回隊列首部（front）的對象。如果隊列為空，則此操作會觸發錯誤。
因此隊列這種數據結構需要包含指向頭部（head）和尾部（tail）的指針或引用，以便有效地執行入隊（enqueue）和出隊（dequeue）操作。

頭部指針指向第一個元素，因為我出隊是要返回隊列首部的對象。而尾部指針指向最后一個元素的后一個位置，因為我入隊是要在尾部插入一個新的對象。

3.size()：返回隊列中對象的數量。
4.isEmpty()：如果隊列為空，則返回 true；否則返回 false。
5.isFull()：如果隊列已滿（達到其容量限制），則返回 true；否則返回 false。
6.front()：返回但不移除隊列首部的對象。如果隊列為空，則此操作會返回錯誤。可以用于查看隊列前端的元素，而不改變隊列的狀態。

下圖展示了一個隊列的例子。

剛開始頭部和尾部指針一致。將$3$入隊后，插入的位置就是原來尾部指針的位置，插入后。頭部指針指向$3$，而尾部指針指向最后一個元素（$3$）的下一個。
再將$7$入隊后，尾部指針因此又向后移動一個。
再將$8$入隊后，尾部指針因此又向后移動一個。
執行出隊后，移除頭部指針指向的元素，并返回該元素，即移除和返回$3$,在將頭部指針向后移動一個。
將$1$入隊，在尾部指針的位置插入$1$，再將指針向后移動一個。
執行出隊后，移除頭部指針指向的元素，并返回該元素，即移除和返回$7$,在將頭部指針向后移動一個。
執行出隊后，移除頭部指針指向的元素，并返回該元素，即移除和返回$8$,在將頭部指針向后移動一個。

2.2.2 實踐

2.2.2.1 循環隊列（Circular Queue）

循環隊列是一種隊列的實現方式，它使用一個固定大小的數組來存儲隊列中的元素，并使用兩個指針來分別追蹤隊列的前端和后端。當隊列滿時，新元素會覆蓋最早進入隊列的元素，從而實現循環利用數組空間。
如下圖所示。

在循環隊列中，當尾部指針到達數組末尾時，它會環繞到數組的開頭，這就是“循環”一詞的由來。其的優點便是有效地使用固定大小的數組空間，避免了因隊列增長而需要的動態數組擴容。

2.2.2.2 多線程編程（Multithreading）

我們在操作系統中學習了多線程編程的概念，隊列最大的應用便是利用隊列來實現線程間的CPU時間分配。
多線程編程是一種實現有限形式的并行性（parallelism）的方法，其允許多個任務或線程同時運行。
例如：計算機（或程序）可能使用多個線程，其中一個線程負責捕獲鼠標點擊，另一個線程可能負責在屏幕上繪制動畫。
在設計使用多個線程的程序（或操作系統）時，我們必須確保單個線程不會獨占CPU。
一種解決方案是使用隊列來以輪詢（round-robin）協議分配CPU時間給線程，即我們可以使用一個隊列來保存線程集合。隊列開頭的線程被移除，分配一部分CPU時間，然后被放回隊列的尾部。

2.3 列表（List）

列表是一種數據結構，由一系列項（items）組成，每個項存儲在一個節點（node）中。每個節點包含一個數據字段（用于存儲數據）和一個指向列表中下一個元素的指針。
與前面的數據結構的不同在于，數據可以通過在列表中的任意位置插入新節點并重新分配指針來插入到列表中，因此數據不僅可以隨時插入，還可以在任意位置插入。
列表ADT支持引用（訪問特定位置的元素）、更新（包括插入和刪除操作）以及搜索方法。
列表ADT可以被實現為單鏈表或雙鏈表（這一點在數據結構課上有詳細說明）。
單鏈表（Singly-linked list）：每個節點包含數據字段和指向下一個節點的指針。
雙鏈表（Doubly-linked list）：每個節點包含數據字段和兩個指針，一個指向下一個節點，另一個指向前一個節點。

2.3.1 相關方法

1.first()：返回列表中第一個元素的位置。如果列表為空，則操作會觸發錯誤。
2.last()：返回列表中最后一個元素的位置。如果列表為空，則操作會觸發錯誤。
3.isFirst§：如果元素 p 是列表中的第一個元素，則返回 true，否則返回 false。
4.isLast§：如果元素 p 是列表中的最后一個元素，則返回 true，否則返回 false。
5.before§：返回列表中位置 p 之前的那個元素的位置。如果 p 是第一個元素，則操作會觸發錯誤，因為第一個元素之前沒有其他元素。
6.after§：返回列表中位置 p 之后的那個元素的位置。如果 p 是最后一個元素，則操作會觸發錯誤，因為最后一個元素之后沒有其他元素。
7.replaceElement(p,e)：將位置 p 處的元素替換為新元素 e。
8.swapElements(p,q)：交換位置 p 和 q 處的元素。
9.insertFirst(e)：在列表的開頭插入新元素 e。
10.insertLast(e)：在列表的末尾插入新元素 e。
11.insertBefore(p,e)：在位置 p 之前插入新元素 e。
12.insertAfter(p,e)：在位置 p 之后插入新元素 e。
13.remove§：移除位置 p 處的元素。

2.3.2 實踐

2.3.2.1 單鏈表（Singly-linked list）

單鏈表是一種常見的數據結構，由一系列節點（nodes）組成，每個節點包含數據元素和指向列表中下一個節點的鏈接（next link）。每個節點中的鏈接指向列表中的下一個元素。如果一個元素是列表的最后一個元素，那么它的鏈接是 null，表示沒有后續元素。
下圖展示了一個節點的組成。

下圖展示了一個單鏈表。

2.3.2.2 雙鏈表（Doubly-linked list）

雙鏈表與單鏈表的區別是多存儲了一個鏈接，原來的鏈接叫做next鏈接，額外儲存的是指向前一個元素的prev鏈接。
因此它為列表ADT提供了一種直觀且高效的實現方式。
所以現在一個節點的組成如下：
元素（Element）：存儲實際的數據。
前一個節點的鏈接：指向前一個節點的鏈接。
下一個節點的鏈接：指向下一個節點的鏈接。
下圖展示了一個節點的組成。

但是我們這里有兩個特例，即頭部和尾部的節點該怎么處理，我們可以直接將第一個節點的prev鏈接設置為null，最后一個節點的next鏈接設置為null。當然也可以采用下面的方案。
專門多兩個特殊節點：
1.頭節點（Header nodes）：通常位于列表的開始位置，用作列表的入口點。頭節點可能不存儲任何實際的數據元素，或者存儲一個特殊值，用于標識列表的開始。
2.尾節點（Trailer nodes）：位于列表的末尾，用于標識列表的結束。尾節點的 next 鏈接通常設置為 null，表示沒有更多的節點跟隨其后。
因此一個雙鏈表如下所示。

我們一般使用的都是雙鏈表，所以我們接下來看一下雙鏈表如何實現前面說的一些基本操作。
插入元素操作如下圖所示，執行了insertAfter(1,e)。

我們找到插入的位置后，然后創建一個新節點，然后其元素儲存對應的值。然后prev鏈接指向前一個節點，next鏈接指向下一個節點。最后更新前一個節點的next鏈接和后一個節點的prev鏈接使它們指向新節點。

該操作的偽代碼如下。

INSERTAFTER(p,e)//Create a new node v
v.element ←e//Link v to its predecessor
v.prev ← p//Link v to its successor
v.next ←p.next//Link p’s old successor to v
(p.next).prev ← v//Link p to its new successor v
p.next ←v
return v

下圖是代碼運行過程的解釋，數字代表代碼的行數。

注意這里的順序不能先修改原來的鏈表的鏈接，否則我們會找不到下一個節點。

說完插入元素，我們說一下移除元素。
下圖展示了執行remove(2)的結果。

首先找到第二個元素“Greece”然后調整前一個節點的next鏈接，直接指向“Greece”的下一個節點。然后“Greece”的下一個節點的prev鏈接指向“Greece”的前一個節點。最后釋放或刪除“Greece”節點所占用的內存。
同樣，這里如果先刪除“Greece”指向下一個節點的next鏈接會導致找不到“Greece”的下一個節點。

該操作的偽代碼如下。

REMOVE(p)//Assign a temporary variable to hold returnvalue
t ←p.element//Unlink p from list
(p.prev).next ← p.next
(p.next).prev ← p.prev//invalidatep
p.prev ←null
p.next ←null
return t

下圖是代碼運行過程的解釋，數字代表代碼的行數。

2.4 根樹（Rooted Tree）

根樹 T 是一種樹形數據結構，由一組節點組成，這些節點以父子關系（parent-child relationship）相互連接。
在根樹 T 中，有一個特殊的節點 r，稱為樹的根（root）。根節點是樹的起始點，s所以沒有父節點。
樹中的每個節點（除了根節點）都有一個父節點（parent node）。父節點指向其子節點，子節點指向其父節點。
下圖展示了一個根樹。

2.4.1 相關術語（Terminology）

1.父節點和子節點（Parent和Child）：如果節點 u 是節點 v 的父節點，那么 v 就是 u 的子節點。
2.兄弟節點（Siblings）：如果兩個節點是同一個父節點的子節點，那么這兩個節點互為兄弟節點。
3.葉節點（Leaf或External Node）：如果一個節點沒有子節點（即沒有孩子），那么這個節點就是葉子節點或外部節點。
4.內部節點（Internel Node）：如果一個節點有子節點（即至少有一個孩子），那么這個節點就是內部節點。
5.有序樹（Ordered Tree）：如果樹中每個內部節點的子節點都有一個定義良好的線性順序（即每個內部節點都有一個明確的第一子節點、第二子節點等），那么這棵樹就是有序的。有序樹允許我們按特定順序訪問或遍歷子節點，例如，先訪問第一個子節點，再訪問第二個子節點，依此類推。

2.4.2 二叉樹（Binary Trees）

二叉樹是一種特殊的有序樹：它是一種有根的有序樹。在二叉樹中，每個節點最多有兩個子節點，通常稱為左子節點（left child）和右子節點（right child）。
完全二叉樹（Proper Binary Tree）：如果二叉樹中的每個內部節點都恰好有兩個子節點，則稱這棵二叉樹為完全二叉樹。

2.4.3 相關方法

2.4.3.1 訪問方法

1.root()：返回樹的根節點。
2.parent(v)：返回節點 v 的父節點。
3.children(v)：返回指向節點 v 的子節點的鏈接。

2.4.3.2 查詢方法

1.isInternal(v)：測試節點 v 是否為內部節點（internal node）。
2.isExternal(v)：測試節點 v 是否為外部節點（external node）。
3.isRoot(v)：測試節點 v 是否為根節點。

2.4.3.3 通用方法

1.size()：返回樹中節點的數量。
2.elements():返回樹中所有元素的列表。
3.positions()：返回所有元素地址的列表。
4.swapElements(u,v)：交換位置 u 和 v 處存儲的元素。
5.replaceElements(v,e)：用元素 e 替換位置 v 處的元素。

2.4.4 實踐

2.4.4.1 節點的深度

節點的深度是指從根節點到該節點的路徑長度，即從根節點開始，經過的邊（或鏈接）的數量。下面利用偽代碼展示利用遞歸如何計算節點的深度。

DEPTH(T,v)
if T.isRoot(v)
then return 0
else return 1 +DEPTH(T, T.parent(v))

如果節點 v 是樹 T 的根節點（T.isRoot(v) 返回 true），則 v 的深度為 0。如果節點 v 不是根節點，那么它的深度是其父節點的深度加 1（return 1 + DEPTH(T, T.parent(v))）。這里 T.parent(v) 返回節點 v 的父節點，然后遞歸地計算父節點的深度。

2.4.4.2 樹的高度

樹的高度等同于樹中葉子節點的最大深度。下面的偽代碼計算了以節點 v 為根的子樹的高度。

HEIGHT(T,v)
if ISEXTERNAL(v)then return0
elseh = 0for each w ∈T.CHILDREN(v)doh = MAX(h,HEIGHT(T,w))return 1 + h

檢查節點 v 是否為葉子節點（即沒有子節點的外部節點）。如果節點 v 是葉子節點（IS_EXTERNAL(v) 返回 true），則返回 0，因為葉子節點的高度為 0。然后初始化變量 h 為 0。這個變量將用于存儲子樹的最大高度。再用遞歸計算子樹的高度遍歷節點 v 的所有子節點 w，對每個子節點 w，遞歸地調用 HEIGHT(T, w) 來計算其高度，使用 MAX(h, HEIGHT(T, w)) 來更新 h，確保 h 存儲的是目前為止找到的最大高度。最后返回 1 + h，因為樹的高度是其子樹中最大高度加 1（根節點的高度至少為 1）。

2.4.4.3 樹遍歷（Tree Traversal）

樹遍歷是一種對樹中所有節點按某種順序進行訪問并執行操作的過程。遍歷的目標是確保每個節點都被訪問一次，并且可以對每個節點執行特定的操作。
盡管遍歷和搜索聽起來相似，它們的目的和應用場景可能有所不同。
遍歷：指按照某種系統化的順序訪問樹中的所有節點，例如打印節點值、收集信息或執行某種操作。
搜索：指查找特定節點或值，例如在二叉搜索樹中查找最小或最大值。

二叉樹支持以下三種遍歷方式：
1.前序遍歷（Preorder Traversal）：
訪問順序：根節點 → 左子樹 → 右子樹。
2.后序遍歷（Postorder Traversal）：
訪問順序：左子樹 → 右子樹 → 根節點。
3.中序遍歷（Inorder Traversal）：
訪問順序：左子樹 → 根節點 → 右子樹。

2.4.4.3.1 前序遍歷（Preorder traversal）

在前序遍歷中，節點會在其所有后代（descendant，也就是子節點）之前被訪問。
其的偽代碼如下。

Algorithm preOrder(v)visit(v)for each child w of vpreOrder(w)

可以用于打印結構化文檔，如下圖所示。

下圖的樹如果使用前序遍歷。

那么遍歷的順序是：A，B，C，D，E，F，G，H，I，J，K.

2.4.4.3.2 后序遍歷（Postorder traversal）

在后序遍歷中，節點在訪問其所有后代（子節點）之后被訪問。
其的偽代碼如下：

Algorithm postOrder(v)for each child w of vpostOrder(w)visit(v)

后序遍歷的一個應用是計算文件目錄及其子目錄中文件所占用的空間，如下圖所示。

同樣的圖。

遍歷的順序是：D，E，C，F，B，I，J，H，K，G，A.

2.4.4.3.3 中序遍歷（Inorder traversal）

在中序遍歷中，節點在訪問其左子樹之后，而在右子樹之前被訪問。即在左子樹和右子樹之間被訪問。
其的偽代碼如下：

Algorithm inOrder(v)if hasLeft(v)inOrder(left(v))visit(v)if hasRight(v)inOrder(right(v))

中序遍歷的一個應用是繪制二叉樹。通過中序遍歷，我們可以確定節點的中序排名（inorder rank）和深度（depth）。在二叉搜索樹（二叉搜索樹和二叉樹不同，其在二叉樹的基礎上將里面的每個節點以左節點小于該節點，右節點大于該節點的順序排序）中，中序遍歷可以生成有序序列。這是因為二叉搜索樹的性質保證了左子樹的所有節點值都小于根節點，右子樹的所有節點值都大于根節點。因此，通過中序遍歷，我們可以得到一個從小到大的有序序列。
如下圖所示。

同樣的圖。

遍歷的順序是：D，C，E，B，F，A，I，H，J，G，K.

2.4.4.4 算術表達式

二叉樹與算術表達式相關聯，其中每個葉節點（external node）是一個變量或常量，每個內部節點（internal node）定義了其兩個子節點上的算術運算。
如下圖所示。

我們用中序遍歷的方式遍歷該樹就可以獲得中綴表達式$(2?(a?1)+(3?b))$。
同理，下圖給出了另一個例子。

中綴表達式為$((4+7)?6+(11?5)+3)?(8?(4+6)?3)$。