五、隊(duì)（Queue）
前一篇講了棧（Stack），隊(duì)和棧其實(shí)只有一個(gè)差別，棧是先進(jìn)后出，隊(duì)是先進(jìn)先出，如圖：
從圖中可以看出，隊(duì)有兩個(gè)常用的方法，Enqueue和Dequeue，顧名思義，就是進(jìn)隊(duì)和出隊(duì)了。隊(duì)和棧一樣，既可以用數(shù)組實(shí)現(xiàn)，也可以用鏈表實(shí)現(xiàn)，我還是偏向于用數(shù)組，我的實(shí)現(xiàn)示意圖如下：
隊(duì)有啥用呢？一個(gè)最常用的用途就是“buffer”，即緩沖區(qū)，比如有一批從網(wǎng)絡(luò)來(lái)的數(shù)據(jù)，處理需要挺長(zhǎng)的時(shí)間，而數(shù)據(jù)抵達(dá)的間隔并不均勻，有時(shí)快，有時(shí)慢，先來(lái)的先處理，后來(lái)的后處理，于是你創(chuàng)建了一個(gè)隊(duì)，用來(lái)緩存這些數(shù)據(jù)，出隊(duì)一筆，處理一筆，直到隊(duì)列為空。當(dāng)然隊(duì)的作用遠(yuǎn)不止于此，下面的例子也是一個(gè)很經(jīng)典的例子，希望讀者能舉一反三。
例子：使用隊(duì)對(duì)樹進(jìn)行廣度優(yōu)先遍歷。
廣度優(yōu)先區(qū)別于深度優(yōu)先，即優(yōu)先遍歷最靠近根節(jié)點(diǎn)的各個(gè)節(jié)點(diǎn)：
我們的算法是：
1，根節(jié)點(diǎn)入隊(duì)
2，出隊(duì)一個(gè)節(jié)點(diǎn)，算一次遍歷，直到隊(duì)列為空
3，將剛出隊(duì)的節(jié)點(diǎn)的子節(jié)點(diǎn)入隊(duì)
4，轉(zhuǎn)到2
隊(duì)列的狀況如下圖：
樹的遍歷一般習(xí)慣使用遞歸，理論上所有的遞歸都可以轉(zhuǎn)變?yōu)榈绾螌?shí)現(xiàn)這個(gè)轉(zhuǎn)變？隊(duì)就是其中一種有效的辦法，OK，下面我給出上述例題的代碼以及注釋。
//Not grace code but enough for demo. ^_^
#include "stdio.h"
// The Node
//////////////////////////////////////////////////////////////////////////
struct Node
{
Node(char cChar, int iSubNodeNum=0);
~Node();
char m_cChar;
int m_iSubNodeNum;
Node** m_arrNodePointer; //Pointers to the sub-node.
};
Node::Node(char cChar, int iSubNodeNum)
{
m_cChar = cChar;
m_iSubNodeNum = iSubNodeNum;
if(iSubNodeNum!=0)
m_arrNodePointer = new Node*[iSubNodeNum];
else
m_arrNodePointer = NULL;
}
Node::~Node()
{
if(m_arrNodePointer!=NULL)
delete[] m_arrNodePointer;
}
// The Queue
//////////////////////////////////////////////////////////////////////////
class Queue
{
public:
Queue(int iAmount=10);
~Queue();
//return 0 means failed, return 1 means succeeded.
int Enqueue(Node* node);
int Dequeue(Node* & node);
private:
int m_iAmount;
int m_iCount;
Node** m_ppFixed; //The pointer array to implement the queue.
int m_iHead;
int m_iTail;
};
Queue::Queue(int iAmount)
{
m_iCount = 0;
m_iAmount = iAmount;
m_ppFixed = new Node*[iAmount];
m_iHead = 0;
m_iTail = iAmount-1;
}
Queue::~Queue()
{
delete[] m_ppFixed;
}
int Queue::Enqueue(Node* node)
{
if(m_iCount<m_iAmount)
{
++m_iTail;
if(m_iTail > m_iAmount-1)
m_iTail = 0;
m_ppFixed[m_iTail] = node;
++m_iCount;
return 1;
}
else
return 0;
}
int Queue::Dequeue(Node* & node)
{
if(m_iCount>0)
{
node = m_ppFixed[m_iHead];
++m_iHead;
if(m_iHead > m_iAmount-1)
m_iHead = 0;
--m_iCount;
return 1;
}
else
return 0;
}
// Main
//////////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
//Construct the tree.
Node nA('A', 3);
Node nB('B', 2);
Node nC('C');
Node nD('D', 3);
Node nE('E');
Node nF('F', 2);
Node nG('G');
Node nH('H', 1);
Node nI('I');
Node nJ('J');
Node nK('K');
Node nL('L');
nA.m_arrNodePointer[0] = &nB;
nA.m_arrNodePointer[1] = &nC;
nA.m_arrNodePointer[2] = &nD;
nB.m_arrNodePointer[0] = &nE;
nB.m_arrNodePointer[1] = &nF;
nD.m_arrNodePointer[0] = &nG;
nD.m_arrNodePointer[1] = &nH;
nD.m_arrNodePointer[2] = &nI;
nF.m_arrNodePointer[0] = &nJ;
nF.m_arrNodePointer[1] = &nK;
nH.m_arrNodePointer[0] = &nL;
Queue que;
que.Enqueue(&nA);
Node *pNode;
while (que.Dequeue(pNode)==1)
{
printf("%c ", pNode->m_cChar);
int i;
for(i=0; i<pNode->m_iSubNodeNum; i++)
{
que.Enqueue(pNode->m_arrNodePointer[i]);
}
}
return 0;
}
代碼不算通用，但用來(lái)演示和理解足夠了，下一篇的內(nèi)容更精彩！
（未完待續(xù)……）