五、队(Queue)
前一篇讲了栈(Stack),队和栈其实只有一个差别,栈是先进后出,队是先进先出,如图:

从图中可以看出,队有两个常用的方法,Enqueue和Dequeue,顾名思义,就是进队和出队了。队和栈一样,既可以用数组实现,也可以用链表实现,我还是偏向于用数组,我的实现示意图如下:

队有啥用呢?一个最常用的用途就是“buffer”,即缓冲区,比如有一批从网络来的数据,处理需要挺长的时间,而数据抵达的间隔并不均匀,有时快,有时慢,先来的先处理,后来的后处理,于是你创建了一个队,用来缓存这些数据,出队一笔,处理一笔,直到队列为空。当然队的作用远不止于此,下面的例子也是一个很经典的例子,希望读者能举一反三。
例子:使用队对树进行广度优先遍历。
广度优先区别于深度优先,即优先遍历最靠近根节点的各个节点:

我们的算法是:
1,根节点入队
2,出队一个节点,算一次遍历,直到队列为空
3,将刚出队的节点的子节点入队
4,转到2
队列的状况如下图:


树的遍历一般习惯使用递归,理论上所有的递归都可以转变为迭代,如何实现这个转变?队就是其中一种有效的办法,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;
}