C/C++數(shù)據(jù)結(jié)構(gòu) - 隊列 循環(huán)隊列

快速入門

介紹

1. 隊列的定義

隊列是一種線性存儲結(jié)構(gòu)，每次對隊列的增刪操作如下

• 增：在隊列尾部添加元素

• 刪（取出）：在隊列頭部刪除元素

  這種數(shù)據(jù)存儲方式遵循“先進先出”（First In First Out）的原則，簡稱FIFO結(jié)構(gòu)；

2.隊列的相關(guān)概念

（1）隊頭

（2）隊尾

（3）空隊列

（4）滿隊列

3. 隊列相關(guān)操作

（1）入隊：push()

（2）出隊：pop()

（3）統(tǒng)計隊列元素個數(shù)：countSize()

（4）判斷隊列是否為空：isEmpty()

（5）獲取隊頭： getFront()

（6）獲取隊尾：getBack()

示例代碼1：C++庫函數(shù)舉例

C++隊列queue模板類的定義在<queue>頭文件中,queue 模板類需要兩個模板參數(shù)，一個是元素類型，一個容器類型，元素類型是必要的，容器類型是可選的，默認為deque 類型。C++隊列Queue是一種容器適配器，它給予程序員一種先進先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)。

1. 頭文件，隊列聲明，隊列方法

#include <queue>queue<int> q; int i = 10;q.push(i) 在隊尾壓入新元素 q.pop() 刪除隊列首元素但不返回其值 q.size() 返回隊列中元素的個數(shù) q.empty() 如果隊列為空返回true，否則返回false q.front() 返回隊首元素的值，但不刪除該元素 q.back() 返回隊列尾元素的值，但不刪除該元素

2.示例

#include <iostream> #include <queue> #include <string>using namespace std;int main() {queue<int> my_q;string log; for (int i = 0; i < 10; i++) {my_q.push(i);}cout << "the front of q is " << my_q.front() << endl; // 返回定義類型cout << "the back of q is " << my_q.back() << endl; // 返回定義類型log = my_q.empty() == true ? "empty":"not empty"; // 返回布爾cout << "my_q is " << log << endl;cout << "my_q size is " << my_q.size() << endl; // 返回整數(shù)while(!my_q.empty()) {cout << "cur pop data = " << my_q.front();my_q.pop(); // 無返回值cout << " is poped" << endl;}return 0; }

示例代碼2：C語言靜態(tài)隊列（循環(huán)隊列，定長隊列）

C語言中，如果采用固定長度的一維數(shù)組來實現(xiàn)隊列，通常使用循環(huán)隊列的形式，避免普通隊列由于順序存儲導致執(zhí)行操作POP出隊時帶來的時間花費問題：每次從數(shù)組頭部刪除元素（出隊）后，需要將頭部以后的所有元素往前移動一個位置，這是一個時間復雜度為O（n）的操作。

循環(huán)隊列的具體原理可以參考：

https://blog.csdn.net/li1914309758/article/details/81363166

由于循環(huán)隊列存在弊端：

當隊空時：front=rear
當隊滿時：front=rear 亦成立
因此只憑等式front=rear無法判斷隊空還是隊滿。 有兩種方法處理上述問題：
（1）另設(shè)一個標志位以區(qū)別隊列是空還是滿。
（2）少用一個元素空間，約定以“隊列頭指針front在隊尾指針rear的下一個位置上”作為隊列“滿”狀態(tài)的標志。即：
隊空時： front=rear
隊滿時： (rear+1)%maxsize=front

1. 頭文件定義

本示例代碼采用第一種方式處理循環(huán)隊列的隊空隊滿問題。

typedef struct _queue {enum QUEUE_TYPE type;int qcapacity; // 容量int qsize; // 當前隊列數(shù)據(jù)的數(shù)量int front; // 隊頭int back; // 隊尾int *qdata; } Queue;

2. 源文件

#include <stdio.h> #include <stdbool.h> #include <stdlib.h> #include <string.h> #include "DH_queue.h"static Queue *static_queue(int len) {Queue *queue = (Queue *)malloc(sizeof(Queue));memset(queue, 0, sizeof(Queue));queue->qcapacity = len;queue->qsize = 0;queue->front = 0;queue->back = 0;queue->qdata = (int *)malloc(sizeof(int) * len);memset(queue->qdata, 0, sizeof(int) * len);return queue; }static int static_countSize(Queue *q) {return q->qsize; }static bool static_isEmpty(Queue *q) {if (q->qsize == 0) {return 1; }return 0; }static bool static_isFull(Queue *q) {if (q->qsize == q->qcapacity) {return 1;}return 0; }static int static_getFront(Queue *q) {return q->qdata[q->front]; }static int static_getBack(Queue *q) {int index = ((q->back == 0) ? q->qcapacity - 1 : q->back - 1);return q->qdata[index]; }static bool static_push(Queue *q, void *data) {if (q->qsize == q->qcapacity) {printf("queue is full, push fail\n");return false;}q->qdata[q->back] = *(int *)data;q->qsize += 1;q->back = (q->back + 1) % q->qcapacity;printf("q->back = %d", q->back);return true; }static bool static_pop(Queue *q, int *data) {if (q->qsize == 0) {printf("queue is empty, pop fail\n");return false;}int tmp = 0;tmp = q->qdata[q->front];q->qsize -= 1;q->front = (q->front + 1) % q->qcapacity; return true; }// 主函數(shù)：測試代碼 int main() {// 創(chuàng)建隊列Queue *my_queue = static_queue(5);// 入列for (int i = 0; i < 6; i++) {printf("= %d\n", static_push(my_queue, &i));}// 遍歷for (int i = 0; i < 5; i++) {printf("%d\n", my_queue->qdata[i]);}// 隊頭和隊尾printf("my_q front = %d, get front = %d, back = %d, get back = %d\n", my_queue->front, static_getFront(my_queue), my_queue->back, static_getBack(my_queue));// 容積和隊列元素printf("my_q capacity = %d, qsize = %d\n", my_queue->qcapacity, my_queue->qsize);// 隊空和隊滿printf("my_q isEmpty = %d, isFull = %d\n", static_isEmpty(my_queue), static_isFull(my_queue));// 出隊列for (int i = 0; i < 6; i++) {printf("= %d\n", static_pop(my_queue, &i));}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的C/C++队列与循环队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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