數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) 1.2：數(shù)組棧（C++版）

• 1. 概念及基本框架

• 2. 基本操作程序?qū)崿F(xiàn)

• 2.1 入棧操作

• 2.2 出棧操作

• 2.3 查找操作

• 2.4 其他操作

• 3. 算法復(fù)雜度分析

• 3.1 入棧操作

• 3.2 出棧操作

• 3.3 查找操作

• 4. 完整代碼

1. 概念及基本框架

棧?可以看做一種特殊的?數(shù)組?，所以我使用第一節(jié)實(shí)現(xiàn)的?動(dòng)態(tài)數(shù)組?來實(shí)現(xiàn)棧這種數(shù)據(jù)結(jié)構(gòu)。當(dāng)然，棧也可以通過其他方式來實(shí)現(xiàn)。因?yàn)樵摋Ｊ峭ㄟ^動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的，所以稱之為?數(shù)組棧?。

棧的結(jié)構(gòu)如上圖所示，可知棧的基本特性如下：
1.棧?有?棧頂?和?棧底?兩端。
2.入棧?和?出棧?操作只能從?棧頂?進(jìn)行。
3.后?入棧?的先?出棧?，即?后進(jìn)先出（Last In First Out），LIFO?。
還有一個(gè)隱含特性，棧可以自行?擴(kuò)容（縮容），而不需要用戶關(guān)心，很顯然，動(dòng)態(tài)數(shù)組已經(jīng)滿足了這個(gè)要求。
由此可見，棧的操作并不多，我使用了一個(gè)由?純虛函數(shù)?構(gòu)成的?抽象類?作為一個(gè)接口來定義這些操作。具體代碼如下：

下面只需要通過繼承?抽象類，并且重寫?純虛函數(shù)?，就可以完成?數(shù)組棧?的實(shí)現(xiàn)。數(shù)組棧類的框架如下：

這個(gè)類內(nèi)部定義一個(gè)動(dòng)態(tài)數(shù)組類對(duì)象，為了保護(hù)數(shù)據(jù)，把它放在?private?部分，構(gòu)造函數(shù)?ArrayStack?底層調(diào)用的就是?Array?的構(gòu)造函數(shù)。用戶在構(gòu)造函數(shù)中也可以指定棧的大小。（默認(rèn)是10）為了兼容更多類型，這里使用了泛型的概念。

2. 基本操作程序?qū)崿F(xiàn)

2.1 入棧操作

入棧操作使用了動(dòng)態(tài)數(shù)組的增加最后一個(gè)元素的操作來實(shí)現(xiàn)。這里動(dòng)態(tài)數(shù)組內(nèi)部已經(jīng)提供了擴(kuò)容操作。

2.2 出棧操作

出棧操作使用了動(dòng)態(tài)數(shù)組的刪除最后一個(gè)元素的操作來實(shí)現(xiàn)。這里動(dòng)態(tài)數(shù)組內(nèi)部已經(jīng)提供了縮容操作。

2.3 查找操作

因?yàn)闂Ｖ荒塬@得棧頂元素，所以這里的查找操作也非常簡(jiǎn)單。

2.4 其他操作

3. 算法復(fù)雜度分析

3.1 入棧操作

最壞復(fù)雜度?O(1+n)?中第一個(gè)?1?是指元素移動(dòng)操作，第二個(gè)?n?是指動(dòng)態(tài)數(shù)組中的?resize?函數(shù)，以下同理。
入?？赡軙?huì)引發(fā)擴(kuò)容操作，平均而言，每增加?n?個(gè)元素，會(huì)擴(kuò)展一次，會(huì)發(fā)生?n?個(gè)元素的移動(dòng)，所以平均下來是?O(1)?。

3.2 出棧操作

3.3 查找操作

總體情況：

由此可以看出，棧操作都是?O(1)?級(jí)別的時(shí)間復(fù)雜度。
注：這里并沒有改的操作，如果更改，需要先出棧，再入棧。

4. 完整代碼

動(dòng)態(tài)數(shù)組類?代碼：

抽象類?接口代碼：

數(shù)組棧?代碼：