隊列

? ? 隊列簡稱隊,?也是一種操作受限的線性表,?只允許在表的一端進行插入,?而在表的另一端進行刪除.其特點為”先進先出(FIFO)”,故又稱為先進先出的線性表,簡單隊列如圖所示:

?

循環隊列

? ? 順序隊列有一個先天不足,?那就是空間利用率不高,?會產生”假溢出”現象,即:其實隊列中還有空閑的空間以存儲元素,?但我們在判斷隊列是否還有空間時,?隊列告訴我們隊列已經滿了,?因此這種溢出并不是真正的溢出,?在data數組中依然存在可以放置元素的空位置,?所以說這是一種”假溢出”;

? ? 于是我們就引入了循環隊列的概念,?將順序隊列臆造為一個環狀的空間,?即把存儲隊列元素的表從邏輯上看成一個環,?稱為循環隊列,其示意圖如下:

注意:如圖中所示,我們的循環隊列為了在實現上的便利,?會有一個位置的空閑,?m_front(如圖中的front)指針總會指向一個元素值為空的位置,因此(m_front+1)%capacity才真正的指向隊首元素,?而m_rear(圖中為rear)才指向一個真實存在的隊尾元素;

//循環隊列的實現與解析 template <typename Type> class MyQueue {template <typename T>friend ostream &operator<<(std::ostream &os, const MyQueue<T> &queue); public:MyQueue(int queueSize = 64);~MyQueue();void push(const Type &item);void pop() throw (std::range_error);const Type &front() const throw (std::range_error);const Type &rear() const throw (std::range_error);bool isEmpty() const;private:Type *m_queue;int m_front; //隊首指針(其實(m_front+1)%capacity才真正的指向隊首元素)int m_rear; //隊尾指針int capacity; //隊列的內存大小, 但實際可用的大小為capacity-1 }; template <typename Type> MyQueue<Type>::MyQueue(int queueSize): capacity(queueSize) {if (queueSize < 1)throw std::range_error("queueSize must >= 1");m_queue = new Type[capacity];if (m_queue == NULL)throw std::bad_alloc();m_front = m_rear = 0; } template <typename Type> MyQueue<Type>::~MyQueue() {delete []m_queue;m_queue = NULL;m_front = m_rear = 0;capacity = -1; } template <typename Type> inline bool MyQueue<Type>::isEmpty() const {return m_front == m_rear; } template <typename Type> inline void MyQueue<Type>::push(const Type &item) {if ((m_rear+1)%capacity == m_front) //隊列已滿{Type *newQueue = new Type[2 * capacity]; //新隊列的長度為原隊列的2倍if (newQueue == NULL)throw std::bad_alloc();int start = (m_front+1)%capacity; //數據序列的起始地址if (start <= 1) //隊列指針尚未回繞{//只需拷貝一次:從start所指向的元素直到m_rear所指向的元素//std::copy(m_queue+start, m_queue+start+capacity-1, newQueue);std::copy(m_queue+start, m_queue+m_rear+1, newQueue);}else{//需要拷貝兩次//1:從start所指向的元素直到數組(不是隊列)末尾std::copy(m_queue+start, m_queue+capacity, newQueue);//2:從數組(不是隊列)起始直到隊列末尾std::copy(m_queue, m_queue+m_rear+1, newQueue+capacity-start);}//重新設置指針位置:詳細信息請看下面圖解m_front = 2*capacity-1;m_rear = capacity-2;capacity *= 2;delete []m_queue;m_queue = newQueue;}//隊尾指針后移//注意:此處m_front+1可能需要回繞m_rear = (m_rear+1)%capacity;m_queue[m_rear] = item; } template <typename Type> inline const Type &MyQueue<Type>::front() const throw (std::range_error) {if (isEmpty())throw range_error("queue is empty");//注意:此處m_front+1可能需要回繞return m_queue[(m_front+1)%capacity]; }template <typename Type> inline const Type &MyQueue<Type>::rear() const throw (std::range_error) {if (isEmpty())throw range_error("queue is empty");return m_queue[m_rear]; } template <typename Type> inline void MyQueue<Type>::pop() throw (std::range_error) {if (isEmpty())throw range_error("queue is empty");//注意:此處m_front+1可能需要回繞m_front = (m_front+1)%capacity;m_queue[m_front].~Type(); //顯示調用析構函數以銷毀(析構)對象 } //輸出隊列所有內容以做測試 template <typename Type> ostream &operator<<(ostream &os, const MyQueue<Type> &queue) {for (int i = (queue.m_front+1)%(queue.capacity);i <= queue.m_rear; /**空**/ ){os << queue.m_queue[i] << ' ';if (i == queue.m_rear)break;elsei = (i+1)%(queue.capacity);}return os; }

補充說明

當隊列已滿時的兩類擴充操作:

擴充之后的內存布局:

?

?

附-測試代碼:

int main() {MyQueue<char> cQueue(3);cQueue.push('A');cQueue.push('B');//因為cQueue實際能夠用的大小為2, 所以此處會對數組進行放大cQueue.push('C');cout << cQueue << endl;cout << "front = " << cQueue.front() << ", rear = "<< cQueue.rear() << endl;cQueue.pop();cQueue.pop();cQueue.push('D');cQueue.push('E');cQueue.push('F');//此時queue的m_rear會進行回繞cQueue.push('G');cQueue.pop();cQueue.push('H');//此時隊列已滿, 再添加元素則會進行對隊列擴張//此時m_rear已經回繞, 則會觸發兩次拷貝操作cQueue.push('I');//驗證是否能夠正常工作cout << cQueue << endl;cout << "front = " << cQueue.front() << ", rear = "<< cQueue.rear() << endl;for (char ch = '1'; ch <= '9'; ++ch)cQueue.push(ch);for (int i = 0; i < 4; ++i)cQueue.pop();cout << cQueue << endl;cout << "front = " << cQueue.front() << ", rear = "<< cQueue.rear() << endl;return 0; }

總結

以上是生活随笔為你收集整理的数据结构基础(7) --循环队列的设计与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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