数据结构(2)——队

发布时间:2017-2-24 9:26:10 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数据结构(2)——队",主要涉及到数据结构(2)——队方面的内容,对于数据结构(2)——队感兴趣的同学可以参考一下。

队(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; }

上一篇:采用MQTT协议实现android消息推送
下一篇:SpringSide】dml简单版

相关文章

相关评论