图解数据结构（3）——队

五、队（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;
}

代码不算通用，但用来演示和理解足够了，下一篇的内容更精彩！