這節(jié)我們討論了兩種好玩的數(shù)據(jù)結(jié)構(gòu)，棧和隊(duì)列。

老樣子，什么是棧， 所謂的棧是棧(Stack)是操作限定在表的尾端進(jìn)行的線(xiàn)性表。表尾由于要進(jìn)行插入、刪除等操作，所以，它具有特殊的含義，把表尾稱(chēng)為棧頂（Top） ，另一端是固定的，叫棧底（Bottom） 。當(dāng)棧中沒(méi)有數(shù)據(jù)元素時(shí)叫空棧(Empty Stack)。這個(gè)類(lèi)似于送飯的飯盒子，上層放的是紅燒肉，中層放的水煮魚(yú)，下層放的雞腿。你要把這些菜取出來(lái)，這就引出來(lái)了棧的特點(diǎn)先進(jìn)后出（First in last out）。   具體敘述，加下圖。

棧通常記為：S= (a1,a2,…,an)，S是英文單詞stack的第 1 個(gè)字母。a1為棧底元素，an為棧頂元素。這n個(gè)數(shù)據(jù)元素按照a1,a2,…,an的順序依次入棧，而出棧的次序相反，an第一個(gè)出棧，a1最后一個(gè)出棧。所以，棧的操作是按照后進(jìn)先出(Last In First Out，簡(jiǎn)稱(chēng)LIFO)或先進(jìn)后出(First In Last Out，簡(jiǎn)稱(chēng)FILO)的原則進(jìn)行的， 因此， 棧又稱(chēng)為L(zhǎng)IFO表或FILO表。 棧的操作示意圖如圖所示。

棧的形式化定義為：棧(Stack)簡(jiǎn)記為 S，是一個(gè)二元組，顧定義為S = (D, R)
其中：D 是數(shù)據(jù)元素的有限集合；
R 是數(shù)據(jù)元素之間關(guān)系的有限集合。

棧的一些基本操作的概述：由于棧只能在棧頂進(jìn)行操作， 所以棧不能在棧的任意一個(gè)元素處插入或刪除元素。因此，棧的操作是線(xiàn)性表操作的一個(gè)子集。棧的操作主要包括在棧頂插入元素和刪除元素、取棧頂元素和判斷棧是否為空等等方面的操作。

同樣，我們以 C#語(yǔ)言的泛型接口來(lái)表示棧，接口中的方法成員表示基本操作。為表示的方便與簡(jiǎn)潔，把泛型棧接口取名為 IStack（實(shí)際上，在 C#中沒(méi)有泛型接口 IStack<T>， 泛型棧是從 IEnumerable<T>和 ICollection 等接口繼承而來(lái)，這一點(diǎn)與線(xiàn)性表有著本質(zhì)的區(qū)別） 。

棧的接口定義源代碼如下所示。

public interface IStack<T> {

//初始條件：棧存在；操作結(jié)果：返回棧中數(shù)據(jù)元素的個(gè)數(shù)。

int GetLength(); //求棧的長(zhǎng)度   偽代碼 index++

//初始條件：棧存在； 操作結(jié)果：如果棧為空返回 true，否則返回 false。偽代碼 if(top==null) return true;else return false;

bool IsEmpty(); //判斷棧是否為空

//初始條件：棧存在； 操作結(jié)果：使棧為空。偽代碼 top=null;

void Clear(); //清空操作

//初始條件：棧存在； 操作結(jié)果：將值為 item 的新的數(shù)據(jù)元素添加到棧頂，棧發(fā)生變化。偽代碼 top=item;index++;

void Push(T item); //入棧操作

//初始條件：棧存在且不為空； 操作結(jié)果：將棧頂元素從棧中取出，棧發(fā)生變化   偽代碼：return top;index--;

T Pop(); //出棧操作

//初始條件：棧表存在且不為空； 操作結(jié)果：返回棧頂元素的值，棧不發(fā)生變化。偽代碼 get top;

T GetTop(); //取棧頂元素
}

棧也分為兩種的形式，一種是順序棧，一種是鏈棧。

第一種 順序棧(Sequence Stack)：

用一片連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)棧中的數(shù)據(jù)元素，這樣的棧稱(chēng)為順序棧(Sequence Stack)。類(lèi)似于順序表，用一維數(shù)組來(lái)存放順序棧中的數(shù)據(jù)元素。棧頂指示器 top 設(shè)在數(shù)組下標(biāo)為 0 的端，top 隨著插入和刪除而變化，當(dāng)棧為空時(shí)，top=-1。下圖是順序棧的棧頂指示器 top與棧中數(shù)據(jù)元素的關(guān)系圖。

順序棧類(lèi) SeqStack<T>源代碼的實(shí)現(xiàn)如下所示。

public class SeqStack<T> : IStack<T> {
private int maxsize; //順序棧的容量 最大的存儲(chǔ)空間
private T[] data; //數(shù)組，用于存儲(chǔ)順序棧中的數(shù)據(jù)元素 存儲(chǔ)數(shù)據(jù)的多少 
private int top; //指示順序棧的棧頂  棧頂指針

//索引器
public T this[int index]
{
get
{
return data[index];
}
set
{
data[index] = value;
}
}

//容量屬性
public int Maxsize
{
get
{
return maxsize;
}

set
{
maxsize = value;
}
}

//棧頂屬性
public int Top
{
get
{
return top;
}
}

//構(gòu)造器  進(jìn)行相應(yīng)初始化的工作    進(jìn)行賦值
public SeqStack(int size)
{
data = new T[size];
maxsize = size;
top = -1;
}

//求棧的長(zhǎng)度   用頭指針來(lái)加一
public int GetLength()
{
return top+1;
}

如圖所示：

//判斷順序棧是否為空

//就是判斷頭指針是否為-1 為就為空 不為就為假

public bool IsEmpty()
{
if (top == -1)
{
return true;
}
else
{
return false;
}
}

具體如下圖所示：

//判斷順序棧是否為滿(mǎn) 或最大尺寸相比較 相等 返回真 不相等返回假
public bool IsFull()
{
if (top == maxsize-1)
{
return true;
}
else
{
return false;
}
}

相應(yīng)情況，一切盡在圖例中。

//入棧 將其放入頂部 top 加加
public void Push(T item)
{

//如果滿(mǎn)了 就不進(jìn)行添加

if(IsFull())
{
Console.WriteLine("Stack is full");
return;
}
//進(jìn)行加入到頂部
data[++top] = item;
}

具體情況，一切盡在圖例中

//出棧 進(jìn)行出棧后 頭指針減減
public T Pop()
{
T tmp = default(T);
if (IsEmpty())
{

Console.WriteLine("Stack is empty");
return tmp;
}

tmp = data[top];
--top;
return tmp;

具體情況，一切盡在圖例中。

//獲取棧頂數(shù)據(jù)元素 把頭指針指向的元素進(jìn)行彈出的操作
public T GetTop()
{

//如果是空 就返回一個(gè)默認(rèn)值
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
return default(T);
}

return data[top];

具體情況，一切盡在圖例中：

}

}

}

這就是對(duì)順序棧的相應(yīng)的介紹。

下面，我們就來(lái)到了另一種棧——鏈棧的介紹

什么是鏈棧了，所謂鏈棧是棧的另外一種存儲(chǔ)方式是鏈?zhǔn)酱鎯?chǔ)，這樣的棧稱(chēng)為鏈棧(Linked Stack)。鏈棧通常用單鏈表來(lái)表示，它的實(shí)現(xiàn)是單鏈表的簡(jiǎn)化。所以，鏈棧結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表結(jié)點(diǎn)的結(jié)構(gòu)一樣，如圖所示。由于鏈棧的操作只是在一端進(jìn)行，為了操作方便，把棧頂設(shè)在鏈表的頭部，并且不需要頭結(jié)點(diǎn)。

鏈棧結(jié)點(diǎn)類(lèi)(Node<T>)源代碼的實(shí)現(xiàn)如下： 

public class Node<T>
{
private T data; //數(shù)據(jù)域
private Node<T> next; //引用域

//構(gòu)造器
public Node(T val, Node<T> p)
{
data = val;
next = p;
}

//構(gòu)造器

public Node(Node<T> p)
{
next = p;
}

//構(gòu)造器
public Node(T val)
{
data = val;
next = null;
}

//構(gòu)造器
public Node()
{
data = default(T);
next = null;
}

//數(shù)據(jù)域?qū)傩?
public T Data
{
get
{
return data;
}
set
{
data = value;
}
}

//引用域?qū)傩?
public Node<T> Next
{
get
{
return next;
}
set
{
next = value;
}
}

}

下圖是鏈棧示意圖。 

把鏈棧看作一個(gè)泛型類(lèi)，類(lèi)名為 LinkStack<T>。LinkStack<T>類(lèi)中有一個(gè)字段 top表示棧頂指示器。由于棧只能訪(fǎng)問(wèn)棧頂?shù)臄?shù)據(jù)元素，而鏈棧的棧頂指示器又不能指示棧的數(shù)據(jù)元素的個(gè)數(shù)。所以，求鏈棧的長(zhǎng)度時(shí)，必須把棧中的數(shù)據(jù)元素一個(gè)個(gè)出棧， 每出棧一個(gè)數(shù)據(jù)元素， 計(jì)數(shù)器就增加 1， 但這樣會(huì)破壞棧的結(jié)構(gòu)。為保留棧中的數(shù)據(jù)元素， 需把出棧的數(shù)據(jù)元素先壓入另外一個(gè)棧， 計(jì)算完長(zhǎng)度后，再把數(shù)據(jù)元素壓入原來(lái)的棧。但這種算法的空間復(fù)雜度和時(shí)間復(fù)雜度都很高，所以， 以上兩種算法都不是理想的解決方法。 理想的解決方法是 LinkStack<T>類(lèi)增設(shè)一個(gè)字段 num表示鏈棧中結(jié)點(diǎn)的個(gè)數(shù)。

鏈棧類(lèi) LinkStack<T>的實(shí)現(xiàn)說(shuō)明如下所示。
public class LinkStack<T> : IStack<T> {
private Node<T> top; //棧頂指示器
private int num; //棧中結(jié)點(diǎn)的個(gè)數(shù)

//棧頂指示器屬性
public Node<T> Top
{
get
{
return top;
}
set
{
top = value;
}
}

//元素個(gè)數(shù)屬性 進(jìn)行了計(jì)數(shù) 
public int Num
{
get
{
return num;
}
set
{
num = value;
}
}

//構(gòu)造器 進(jìn)行了函數(shù)的初始化
public LinkStack()
{
top = null;
num = 0;
}

//求鏈棧的長(zhǎng)度   返回計(jì)算的復(fù)雜度  此算法的復(fù)雜度是O(1)
public int GetLength()
{
return num;
}

//清空鏈棧 進(jìn)行清空的操作 此算法的復(fù)雜度是O(1)
public void Clear()
{
top = null;
num = 0;
}

//判斷鏈棧是否為空   判斷 計(jì)數(shù)的變量和頭指針是否是空  返回為真  否則 為假  此算法的復(fù)雜度是O(n)
public bool IsEmpty()
{
if ((top == null) && (num == 0))
{
return true;
}
else
{
return false;
}
}

//入棧 進(jìn)行棧內(nèi) 入棧的操作
public void Push(T item)
{
Node<T> q = new Node<T>(item);

if (top == null)
{
top = q;
}
else

{
q.Next = top;
top = q;
}

++num;
}

//出棧 進(jìn)行出棧的操作 頭指針相減。此算法的復(fù)雜度為1
public T Pop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
return default(T);
}

Node<T> p = top;
top = top.Next;
--num;

return p.Data;
}

//獲取棧頂結(jié)點(diǎn)的值  返回頭指針的值 此算法的復(fù)雜度為一。
public T GetTop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty!");
return default(T);
}
return top.Data;
}

}

這就是鏈棧的介紹的。還介紹一個(gè)棧的明顯的應(yīng)用，這就是簡(jiǎn)易萬(wàn)能計(jì)算器的應(yīng)用。

我們都知道在使用算符優(yōu)先文法時(shí)必須使用兩個(gè)基本棧，數(shù)棧(operand stack)和運(yùn)算符棧(operator stack)，來(lái)完成計(jì)算工作，然而單單使用這兩個(gè)棧有一定的局限性，因此在設(shè)計(jì)時(shí)，我引入了第三個(gè)棧(op stack)，下面我們就來(lái)分析一下。

在使用兩個(gè)棧時(shí)，如果遇到表達(dá)式 2-3*/6#，會(huì)發(fā)生什么呢？

此時(shí)，錯(cuò)誤信息為：在minus附近可能存在錯(cuò)誤。但實(shí)際上問(wèn)題出在*或/號(hào)附近，這種報(bào)錯(cuò)的定位結(jié)果是不能令人滿(mǎn)意的。

于是讓我們看看如果引入第三個(gè)棧作符號(hào)棧會(huì)如何？符號(hào)棧的功能是保存所有分析過(guò)程中的符號(hào)，包括數(shù)符和運(yùn)算符兩種。

錯(cuò)誤定位在/號(hào)，錯(cuò)誤信息為：在divide附近存在錯(cuò)誤。這樣將使用戶(hù)更有可能找到表達(dá)式中的問(wèn)題所在。我們通過(guò)每次運(yùn)算時(shí)(對(duì)應(yīng)于SemanticAnalyzer.FakeCalculate()方法)，利用了絕對(duì)相鄰優(yōu)先級(jí)表對(duì)符號(hào)棧的彈出符號(hào)進(jìn)行相鄰性檢查，只要發(fā)現(xiàn)棧頂?shù)膬蓚€(gè)符號(hào)不能相鄰，則馬上報(bào)錯(cuò)。具體情況，如圖所示：

什么是隊(duì)列，所謂的隊(duì)列是隊(duì)列(Queue)是插入操作限定在表的尾部而其它操作限定在表的頭部進(jìn)行的,線(xiàn)性表。把進(jìn)行插入操作的表尾稱(chēng)為隊(duì)尾(Rear)，把進(jìn)行其它操作的頭部稱(chēng)為隊(duì)頭(Front)。當(dāng)對(duì)列中沒(méi)有數(shù)據(jù)元素時(shí)稱(chēng)為空對(duì)列(Empty Queue)。隊(duì)列通常記為：Q= (a1,a2,…,an)，Q是英文單詞queue的第 1 個(gè)字母。a1為隊(duì)頭元素，an為隊(duì)尾元素。這n個(gè)元素是按照a1,a2,…,an的次序依次入隊(duì)的，出對(duì)的次序與入隊(duì)相同，a1第一個(gè)出隊(duì)，an最后一個(gè)出隊(duì)。所以，對(duì)列的操作是按照先進(jìn)先出(First In First Out)或后進(jìn)后出( Last In Last Out)的原則進(jìn)行的，這就像 排隊(duì)買(mǎi)票 ，買(mǎi)完就做。因此，隊(duì)列又稱(chēng)為FIFO表或LILO表。隊(duì)列Q的操作示意圖如圖所示。具體情況，如圖所示：

隊(duì)列的形式化定義為：隊(duì)列(Queue)簡(jiǎn)記為 Q，是一個(gè)二元組， Q = (D, R) 其中：D 是數(shù)據(jù)元素的有限集合； 是數(shù)據(jù)元素之間關(guān)系的有限集合。 在實(shí)際生活中有許多類(lèi)似于隊(duì)列的例子。比如，排隊(duì)取錢(qián)，先來(lái)的先取，后來(lái)的排在隊(duì)尾。

同樣，我們以 C#語(yǔ)言的泛型接口來(lái)表示隊(duì)列，接口中的方法成員表示基本操作。為了表示的方便與簡(jiǎn)潔，把泛型隊(duì)列接口取名為 IQueue<T>（實(shí)際上，在C#中泛型隊(duì)列類(lèi)是從 IEnumerable<T>、 ICollection 和 IEnumerable 接口繼承而來(lái)，沒(méi)有 IQueue<T>泛型接口） 。隊(duì)列接口 IQueue<T>源代碼的定義如下所示。

public interface IQueue<T> {
int GetLength(); //求隊(duì)列的長(zhǎng)度；初始條件：隊(duì)列存在； 操作結(jié)果：返回隊(duì)列中數(shù)據(jù)元素的個(gè)數(shù)。一切開(kāi)始，如圖所示：

bool IsEmpty(); //判斷對(duì)列是否為空；初始條件：隊(duì)列存在； 操作結(jié)果：如果隊(duì)列為空返回 true，否則返回 false。  一切情況，如圖所示：

void Clear(); //清空隊(duì)列；初始條件：隊(duì)列存在； 操作結(jié)果：使隊(duì)列為空。

void In(T item); //入隊(duì) 初始條件：隊(duì)列存在;操作結(jié)果：將值為 item 的新數(shù)據(jù)元素添加到隊(duì)尾，隊(duì)列發(fā)生變化.

T Out(); //出隊(duì) 進(jìn)行出隊(duì)的操作 返回頭結(jié)點(diǎn)  具體情況 如圖所示

此算法復(fù)雜度是O(1)

T GetFront(); //取對(duì)頭元素 取頭元素 具體情況 如圖所示

此算法的復(fù)雜度是O(1)

此算法復(fù)雜度是O(1)

}

這就是隊(duì)列是  基本介紹。

下面我介紹了的隊(duì)列的應(yīng)用，我就是在五子棋，用與保存棋譜，悔棋的操作。這就很好的利用了隊(duì)列先進(jìn)特點(diǎn)保存了，當(dāng)你悔棋了，就把棋子的位置拉出來(lái)。

這就是隊(duì)列和棧的介紹。

最新評(píng)論