数据结构-链式队列

// link_queue_node.h #ifndef LINK_QUEUE_NODE_H #define LINK_QUEUE_NODE_H #include <iostream> template<typename Type> class LinkQueue; template<typename Type> class QueueNode { private: friend class LinkQueue<Type>; QueueNode(const Type item, QueueNode<Type> *next=NULL) : m_data(item), m_next(next){} private: Type m_data; QueueNode<Type> *m_next; }; #endif // LINK_QUEUE_NODE_H // link_queue.h #ifndef LINK_QUEUE_H #define LINK_QUEUE_H #include "link_queue_node.h" template<typename Type> class LinkQueue { public: LinkQueue() : m_prear(NULL), m_pfront(NULL){} ~LinkQueue() { MakeEmpty(); } void EnQueue(const Type item); Type DeQueue(); void MakeEmpty(); Type GetFront(); void Print(); bool IsEmpty() const { return (m_pfront == NULL); } private: QueueNode<Type> *m_prear, *m_pfront; }; template<typename Type> void LinkQueue<Type>::EnQueue(const Type item) { if(m_pfront == NULL) { m_pfront = m_prear = new QueueNode<Type>(item); } else { m_prear = m_prear->m_next = new QueueNode<Type>(item); } } template<typename Type> Type LinkQueue<Type>::DeQueue() { if(IsEmpty()) { std::cout << __FUNCTION__ << " error : queue is empty " << std::endl; exit(1); } Type tmp = m_pfront->m_data; QueueNode<Type> *pdel = m_pfront; m_pfront = m_pfront->m_next; delete pdel; return tmp; } template<typename Type> void LinkQueue<Type>::MakeEmpty() { QueueNode<Type> *pdel; while(m_pfront) { pdel = m_pfront; m_pfront = pdel->m_next; delete pdel; } } template<typename Type> Type LinkQueue<Type>::GetFront() { if(IsEmpty()) { std::cout << __FUNCTION__ << " error : queue is empty " << std::endl; exit(1); } return m_pfront->m_data; } template<typename Type> void LinkQueue<Type>::Print() { using std::cout; using std::endl; QueueNode<Type> *pCursor = m_pfront; cout << "front"; while(pCursor) { cout << "--->" << pCursor->m_data; pCursor = pCursor->m_next; } cout << "--->rear" << endl << endl << endl; } #endif // LINK_QUEUE_H // main.cpp #include <iostream> #include "link_queue.h" using namespace std; int main(int argc, char *argv[]) { LinkQueue<int> queue; int init[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; for(int i = 0; i < 10; i++) { queue.EnQueue(init[i]); } queue.Print(); cout << "dequeue : " << queue.DeQueue() << endl; queue.Print(); cout << "get front : " << queue.GetFront() << endl; queue.Print(); queue.MakeEmpty(); queue.Print(); return 0; }