隊列：先進先出，就如排隊一樣，先到的，先排上

1.鏈式隊列

1.1 頭文件 listQueue.h

/*** @description: 鏈式隊列* @author: michael ming* @date: 2019/4/1 22:47* @modified by:*/#ifndef QUEUE_LISTQUEUE_H #define QUEUE_LISTQUEUE_H template <class T> struct SNode {T data;SNode* pNext; };typedef unsigned int UINT; template <class T> class ListQueue { public:ListQueue(void);~ListQueue(void);bool enqueue(const T& data); //入隊 從隊列的尾部插入數據bool dequeue(); //出隊 從隊列的頭部彈出數據UINT getlength() const; //獲得隊列的長度bool empty() const; //判斷隊列是否為空void erase(); //清空隊列void print() const; //打印隊列SNode<T>* getHead(); //獲取隊首SNode<T>* getTail(); //獲取隊尾 private:SNode<T>* m_pHead;SNode<T>* m_pTail;UINT m_QueueLen; };#include "listQueue.cpp" #endif //QUEUE_LISTQUEUE_H

1.2 類實現文件 listQueue.cpp

/*** @description: 鏈式隊列實現文件* @author: michael ming* @date: 2019/4/1 22:47* @modified by:*/ //#include "listQueue.h" #include <iostream> using namespace std; template <class T> ListQueue<T>::ListQueue():m_pHead(NULL),m_pTail(NULL),m_QueueLen(0){} template <class T> ListQueue<T>::~ListQueue() {erase(); } template <class T> inline void ListQueue<T>::erase() {SNode<T>* temp;while(m_pHead != NULL){temp = m_pHead->pNext;delete m_pHead;m_pHead = temp;}m_pTail = NULL;m_QueueLen = 0; } template <class T> bool ListQueue<T>::empty() const {return m_pHead == NULL; } template <class T> UINT ListQueue<T>::getlength() const {return m_QueueLen; } template <class T> bool ListQueue<T>::enqueue(const T &data) {SNode<T>* newNode = new SNode<T>;newNode->data = data;newNode->pNext = NULL;if(m_pTail == NULL)m_pHead = m_pTail = newNode;else{m_pTail->pNext = newNode;m_pTail = newNode;}m_QueueLen++;return true; } template <class T> bool ListQueue<T>::dequeue() {if(m_pHead != NULL){SNode<T>* temp = m_pHead;m_pHead = m_pHead->pNext;if(m_pHead == NULL)m_pTail == NULL;delete temp;m_QueueLen--;return true;}return false; } template <class T> void ListQueue<T>::print() const {cout << "-------------------------------------------" << endl;cout << "List Queue from head to tail as follow: " << endl;SNode<T>* temp = m_pHead; int i = 0;while(temp != NULL){cout << "No." << ++i << " elem is " << temp->data << endl;temp = temp->pNext;} } template <class T> SNode<T>* ListQueue<T>::getHead() {return m_pHead; } template <class T> SNode<T>* ListQueue<T>::getTail() {return m_pTail; }

1.3 測試主函數 listqueue_main.cpp

/*** @description:* @author: michael ming* @date: 2019/4/1 22:49* @modified by:*/ #include "listQueue.h" #include <iostream> int main() {ListQueue<int> intqueue;int k = 5;for(int i = 0; i < k; ++i){intqueue.enqueue(i);}intqueue.print();std::cout << "len of queue is " << intqueue.getlength() << std::endl;for(int i = 0; i < k-1; ++i){intqueue.dequeue();std::cout << "after one dequeue: " << std::endl;intqueue.print();}std::cout << "len of queue is " << intqueue.getlength() << std::endl;std::cout << "head is " << intqueue.getHead()->data << std::endl;std::cout << "tail is " << intqueue.getTail()->data << std::endl;return 0; }

1.4 valgrind測試運行結果

2. 順序隊列

基于數組實現，有容量限制

2.1 頭文件 arrqueue.h

/*** @description: 順序隊列，內部基于數組* @author: michael ming* @date: 2019/4/2 21:24* @modified by:*/ #ifndef QUEUE_ARRQUEUE_H #define QUEUE_ARRQUEUE_H typedef unsigned int UINT; template <class T> class arrQueue { public:arrQueue(const int capa = 10);~arrQueue(void);bool enqueue(const T& data); //入隊 從隊列的尾部插入數據bool dequeue(); //出隊 從隊列的頭部彈出數據UINT getlength() const; //獲得隊列的長度bool empty() const; //判斷隊列是否為空bool full() const; //判斷隊列是否滿void erase(); //清空隊列void print() const; //打印隊列const T& getHead() const; //獲取隊首const T& getTail() const; //獲取隊尾 private:int m_pHead;int m_pTail;UINT m_QueueLen;UINT m_capacity;T* arrQ; };#include "arrqueue.cpp" #endif //QUEUE_ARRQUEUE_H

2.2 類實現文件 arrqueue.cpp

/*** @description: 順序隊列實現文件* @author: michael ming* @date: 2019/4/2 21:26* @modified by:*/ #include <iostream> using namespace std; template <class T> arrQueue<T>::arrQueue(const int capa):m_pHead(0),m_pTail(-1),m_QueueLen(0),m_capacity(capa) {arrQ = new T[m_capacity]; } template <class T> arrQueue<T>::~arrQueue() {erase();delete [] arrQ; } template <class T> inline void arrQueue<T>::erase() {m_QueueLen = 0;m_pHead = 0;m_pTail = -1; } template <class T> bool arrQueue<T>::empty() const {return m_QueueLen == 0; } template <class T> bool arrQueue<T>::full() const {return m_QueueLen == m_capacity; } template <class T> bool arrQueue<T>::enqueue(const T &data) {if(full())return false;else{if(empty()){m_pHead = m_pTail = 0;arrQ[0] = data;m_QueueLen++;}else if(m_pTail < m_capacity-1){arrQ[++m_pTail] = data;m_QueueLen++;}else //隊列沒滿，但是隊尾到達數組末尾了，數據整體移至數組頭部{for(UINT i = 0; i < m_QueueLen; ++i){arrQ[i] = arrQ[m_pHead++];}m_pHead = 0;arrQ[m_QueueLen++] = data;m_pTail = m_QueueLen - 1;}return true;} } template <class T> bool arrQueue<T>::dequeue() {if(empty())return false;else{m_pHead++;m_QueueLen--;if(m_QueueLen == 0){m_pHead = 0;m_pTail = -1;}return true;} } template <class T> UINT arrQueue<T>::getlength() const {return m_QueueLen; } template <class T> const T& arrQueue<T>::getHead() const {return arrQ[m_pHead]; } template <class T> const T& arrQueue<T>::getTail() const {return arrQ[m_pTail]; } template <class T> void arrQueue<T>::print() const {if(empty())cout << "empty queue!" << endl;cout << "arrQueue from head to tail as follow:" << endl;int j = m_pHead;for(UINT i = 0; i < m_QueueLen; ){cout << "No." << ++i << " elem is " << arrQ[j++] << endl;}cout << "--------------print end----------------" << endl; }

2.3 測試主程序 arrqueue_main.cpp

/*** @description:* @author: mingm* @date: 2019/4/1 22:44* @param:* @return:*/ #include <iostream> #include "arrqueue.h" int main() {arrQueue<int> intqueue(7);for(UINT i = 0; i < 8; ++i){intqueue.enqueue(i);intqueue.print();}for(UINT i = 0; i < 5; ++i){intqueue.dequeue();intqueue.print();}intqueue.enqueue(100);intqueue.print();cout << "the length of queue is " << intqueue.getlength() << endl;cout << "head is " << intqueue.getHead() << ", tail is " << intqueue.getTail() << endl;return 0; }

2.4 valgrind測試結果正確

總結

以上是生活随笔為你收集整理的数据结构--队列Queue--链式队列、顺序队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。