一、概述

隊(duì)列（queue）: 只允許在一端進(jìn)行插入 （隊(duì)尾） 操作，而在另一端 （隊(duì)頭） 進(jìn)行刪除操作的線性表。
隊(duì)頭：刪除操作的一端——front
隊(duì)尾：插入操作的一端——rear

特點(diǎn)：先進(jìn)先出（First In First Out）

其他常用隊(duì)列：循環(huán)隊(duì)列、阻塞隊(duì)列、并發(fā)隊(duì)列。

二、隊(duì)列的抽象數(shù)據(jù)類型

ADT 隊(duì)列 (Queue) Data同線性表。元素具有相同的類型，相鄰元素具有前驅(qū)和后繼關(guān)系 OpreationInitQueue(*Q): 初始化操作，建立一個(gè)空隊(duì)列Q。DestroyQueue(*Q): 若隊(duì)列Q存在，則銷毀它。ClearQueue(*Q): 將隊(duì)列Q清空。QueueEmpty(Q): 若隊(duì)列為空，返回true，否則返回false。GetHead(Q,*e): 若隊(duì)列Q存在且非空

二、C++隊(duì)列的方法

back()——返回最后一個(gè)元素；

empty()——如果隊(duì)列空則返回true，否則返回false；

front()——返回第一個(gè)元素；

pop()——從隊(duì)頭刪除第一個(gè)元素；

push()——在隊(duì)尾插入一個(gè)元素；

size()——返回隊(duì)列中元素的大小；

#include<iostream> #include<queue> using namespace std;int main() {queue<int> que;// 入隊(duì)for(int i = 0; i < 50; i++){que.push(i);}cout<<"the size of queue:"<<que.size()<<endl;while(!que.empty()){cout<<"the front element of queue:"<<que.front()<<" ";cout<<"the rear element of queue:"<<que.back()<<endl;que.pop();}cout<<"the size of queue:"<<que.size()<<endl;return 0; }

三、實(shí)現(xiàn)

1、順序隊(duì)列——數(shù)組實(shí)現(xiàn)

• 順序隊(duì)列需事先確定隊(duì)列的大小，不支持動(dòng)態(tài)分配存儲(chǔ)空間，所以插入和刪除元素比較省時(shí)，但是會(huì)造成空間的浪費(fèi)。

解決方法：循環(huán)隊(duì)列 =》解決空間浪費(fèi)的問題
循環(huán)隊(duì)列的實(shí)現(xiàn)：

#include <iostream> using namespace std;const int MAXSIZE = 1000; typedef int ELEMTYPE; const int N = 10; typedef struct{ELEMTYPE data[MAXSIZE];int head; /*隊(duì)頭指針*/int rear; /*隊(duì)尾指針*/ }Queue;Queue Q; void initQueue(Queue &Q); void printQueue(Queue &Q); bool isQueueEmpty(Queue &Q); bool isQueueFull(Queue &Q); bool EnQueue(Queue &Q, ELEMTYPE e); bool DeQueue(Queue &Q, ELEMTYPE &e);int main() {for(int i = 0; i < N; i++){EnQueue(Q, i);}printQueue(Q);return 0; }void initQueue(Queue &Q) {Q.head = 0;Q.rear = 0; } void printQueue(Queue &Q) {ELEMTYPE e;while(!isQueueEmpty(Q)){DeQueue(Q,e);cout<<e<<" ";}cout<<endl; } bool isQueueEmpty(Queue &Q) {if(Q.head == Q.rear)return true;elsereturn false; } bool isQueueFull(Queue &Q) {if((Q.rear+1)%MAXSIZE == Q.head)return true;elsereturn false; } bool EnQueue(Queue &Q, ELEMTYPE e) {if(isQueueFull(Q))return false;Q.rear = (Q.rear+1)%MAXSIZE;Q.data[Q.rear] = e;return true; } bool DeQueue(Queue &Q, ELEMTYPE &e) {if(isQueueEmpty(Q))return false;Q.head = (Q.head+1)%MAXSIZE;e = Q.data[Q.head];return true; }

2、鏈?zhǔn)疥?duì)列——鏈表實(shí)現(xiàn)

• 可以不需要事先知道隊(duì)列的大小，支持動(dòng)態(tài)和釋放空間，但是插入和刪除操作比較耗時(shí)

#include <iostream> using namespace std; struct NODE//雙向鏈表基本單元結(jié)構(gòu) {int data;NODE *next;//后繼指針NODE *pre;//前驅(qū)指針 }; class QUEUE//定義queue類封裝數(shù)據(jù)和實(shí)現(xiàn) { private:NODE *front;//隊(duì)頭指針NODE *tail;//隊(duì)尾指針unsigned size; public:QUEUE();~QUEUE(){};void initialize(); //初始化void enqueue(int n); //入隊(duì)void dequeue(); //出隊(duì)int get_front(); //獲取元素void clear(); //清空隊(duì)列int get_size(); //返回元素個(gè)數(shù)bool isempty(); //判斷是否為空void display_queue(); //輸出隊(duì)列 }; QUEUE::QUEUE() {initialize(); } void QUEUE::initialize() {//初始化頭部和尾部指針front = new NODE();tail = new NODE();//將頭尾連接front->data = tail->data = 0;front->pre = tail->next = NULL;front->next = tail;tail->pre = front;size = 0; //設(shè)置元素個(gè)數(shù)為0 } void QUEUE::enqueue(int n) {//開辟新節(jié)點(diǎn)NODE *new_ele = new NODE();//設(shè)置數(shù)據(jù)new_ele->data = n; //將新節(jié)點(diǎn)插入到雙向鏈表尾部tail->pre->next = new_ele; new_ele->next = tail;new_ele->pre = tail->pre;tail->pre = new_ele;size++; //元素個(gè)數(shù)加1 } void QUEUE::dequeue() {if (isempty())//避開對(duì)空隊(duì)列的操作{cout << "queue is empty" << endl; return;}//獲取刪除將要?jiǎng)h除的元素指針NODE *temp = front->next;front->next = temp->next;temp->next->pre = front; delete(temp);//釋放內(nèi)存size--; } int QUEUE::get_front() {if (front->next != tail)return front->next->data;elsecout << "empty queque" << endl;return -1; } void QUEUE::clear() {NODE *temp = front;//遍歷鏈表釋放所有節(jié)點(diǎn)內(nèi)存 while(temp != tail){NODE *del_data = temp;temp = temp->next;delete(del_data);}//調(diào)用函數(shù)重新初始化initialize(); } int QUEUE::get_size() {return size; } void QUEUE::display_queue() {NODE *temp = front->next;while (temp != tail){cout << temp->data << " ";temp = temp->next;}if (isempty())cout << "queue is empty" << endl;elsecout << endl; } bool QUEUE::isempty() {return front->next == tail; } int main(int argc, char const *argv[]) {QUEUE que; /* *do somthing here */ return 0; }

3、循環(huán)隊(duì)列

• 關(guān)鍵：判斷隊(duì)列是空對(duì)還是滿隊(duì)
  • 空：head == tail
  • 滿：（tail+1）%n == head
• 當(dāng)循環(huán)隊(duì)列滿隊(duì)時(shí)，tail指針指向的位置實(shí)際并沒有存儲(chǔ)數(shù)據(jù)。=》循環(huán)隊(duì)列會(huì)浪費(fèi)一個(gè)數(shù)組的存儲(chǔ)空間

template<class T>class SeqQueue{protected:T *element;int front,rear;int maxSize;public:SeqQueue(int sz=10){front=rear=0;maxSize=sz;element=new T[maxSize];}~SeqQueue(){delete[] element;}bool EnQueue(const T& x){//入隊(duì) if(isFull()) return false;element[rear]=x;rear=(rear+1)%maxSize;return true;}bool DeQueue(T& x){//出隊(duì) if(isEmpty()) return false;x=element[front];front=(front+1)%maxSize;return true;}bool getFront(T& x){//獲取隊(duì)首元素 if(isEmpty()) return false;x=element[front];return true;}void makeEmpty(){//隊(duì)列置空 front=rear=0;}bool isEmpty()const{//判斷隊(duì)列是否為空 return (rear==front)?true:false;}bool isFull()const{//隊(duì)列是否為滿return ((rear+1)%maxSize==front)?true:false;}int getSize()const{return (rear-front+maxSize)%maxSize;}};

4、阻塞隊(duì)列

支持阻塞操作的隊(duì)列。具體來講，支持阻塞添加和阻塞移除。

阻塞添加： 當(dāng)隊(duì)列滿的時(shí)候，隊(duì)列會(huì)阻塞插入插入的元素的線程，直到隊(duì)列不滿；
阻塞移除： 在隊(duì)列為空時(shí)，隊(duì)里會(huì)阻塞插入元素的線程，直到隊(duì)列不滿。

阻塞隊(duì)列常用于“生產(chǎn)者-消費(fèi)者模型”，生產(chǎn)者是向隊(duì)列添加元素的線程；消費(fèi)者是從隊(duì)列取元素的線程。

5、并發(fā)隊(duì)列

并發(fā)隊(duì)列就是隊(duì)列的操作多線程安全。
實(shí)現(xiàn)：基于數(shù)組的循環(huán)隊(duì)列，利用CAS原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列

總結(jié)

以上是生活随笔為你收集整理的五、队列（Queue）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。