队列是一种先进先出的数据结构，因和平常生活中的排队流程一样因此被称为队列。操作逻辑和栈刚好相反。
常用操作：
enqueue: 元素入队dequeue: 首元素出队size: 返回队列中元素的个数empty: 判断队列是否为空front: 返回队首元素
它有两个指针分别指向队列开头和结尾，出队和入队的流程为：
队列的实现方式多样，也可以和栈一样通过数组、 vector 等方式实现，这里就采用最常用的链式节点实现。
一、队列节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
typedef unsigned int uint; template <typename T> class CQueueNode { public: CQueueNode(); CQueueNode(T data, CQueueNode<T>* next = 0); ~CQueueNode(); T getData() const; CQueueNode<T>* getNext() const; void setData(T data); void setNext(CQueueNode<T>* next); private: T data; CQueueNode<T>* next; }; template <typename T> CQueueNode<T>::CQueueNode() { next = 0; } template <typename T> CQueueNode<T>::CQueueNode(T data, CQueueNode<T>* next) : data(data), next(next) { } template <typename T> CQueueNode<T>::~CQueueNode() { // 如果需要删除节点时把后面的所有节点都删除可以添加下面语句 //if (next) delete next; next = 0; } template <typename T> T CQueueNode<T>::getData() const { return data; } template <typename T> CQueueNode<T>* CQueueNode<T>::getNext() const { return next; } template <typename T> void CQueueNode<T>::setData(T data) { this->data = data; } template <typename T> void CQueueNode<T>::setNext(CQueueNode<T>* next) { this->next = next; } |
二、队列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include "node.h" template <typename T> class CQueue { public: CQueue(); ~CQueue(); T enqueue(const T data); T dequeue(); uint size() const; bool empty() const; T front() const; private: CQueueNode<T> *head, *tail; uint len; }; template <typename T> CQueue<T>::CQueue() : len(0), tail(0), head(0) { } // 入队操作 template <typename T> T CQueue<T>::enqueue(const T data) { CQueueNode<T>* temp = new CQueueNode<T>(data); // 判断队列是否为空 if (!tail) head = tail = temp; else { tail->setNext(temp); tail = temp; } len++; return temp->getData(); } // 析构函数 template <typename T> CQueue<T>::~CQueue() { CQueueNode<T>* p = head, *q; // 删除所有的节点 while (p) { q = p->getNext(); delete p; p = q; } head = 0, tail = 0, len = 0; } // 出队操作 // 出队时，应先通过 empty() 判断队列是否为空然后再操作 template <typename T> T CQueue<T>::dequeue() { // 实际不应有这一句，应该主动避免该问题 // 因为当 T 是 string 时且 head==0 时，程序会崩溃 if (!head) return 0; T data = head->getData(); CQueueNode<T>* dNode = head; if (head == tail) // 只有一个元素 head = tail = 0; else // 有多个元素 head = dNode->getNext(); delete dNode; len--; return data; } template <typename T> uint CQueue<T>::size() const { return len; } template <typename T> bool CQueue<T>::empty() const { return len == 0; } // 返回第一个元素 template <typename T> T CQueue<T>::front() const { // 和出队操作一样，此处应该主观避免 head 为空的情况 return head ? head->getData() : 0; } |