队列
抽象数据类型
佇列,又稱為伫列(queue),计算机科學中的一種抽象資料型別,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。
Queue | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
用大O符号表示的时间复杂度 | |||||||||||||||||||||
|
队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。
单链队列编辑
单链队列使用链表作为基本数据结构,所以不存在伪溢出的问题,队列长度也没有限制。但插入和读取的时间代价较高
存储结构编辑
/* c3-2.h 单链队列--队列的链式存储结构 */typedef struct QNode{QElemType data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front,rear; /* 队头、队尾指针 */}LinkQueue;
基本操作编辑
/* bo3-2.c 链队列(存储结构由c3-2.h定义)的基本操作(9个) */void InitQueue(LinkQueue *Q){/* 构造一个空队列Q */(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));if(!(*Q).front)exit(OVERFLOW);(*Q).front->next=NULL;}void DestroyQueue(LinkQueue *Q){/* 销毁队列Q(无论空否均可) */while((*Q).front){(*Q).rear=(*Q).front->next;free((*Q).front);(*Q).front=(*Q).rear;}}void ClearQueue(LinkQueue *Q){/* 将Q清为空队列 */QueuePtr p,q;(*Q).rear=(*Q).front;p=(*Q).front->next;(*Q).front->next=NULL;while(p){q=p;p=p->next;free(q);}}Status QueueEmpty(LinkQueue Q){/* 若Q为空队列,则返回TRUE,否则返回FALSE */if(Q.front->next==NULL)return TRUE;elsereturn FALSE;}int QueueLength(LinkQueue Q){/* 求队列的长度 */int i=0;QueuePtr p;p=Q.front;while(Q.rear!=p){i++;p=p->next;}return i;}Status GetHead_Q(LinkQueue Q,QElemType *e) /* 避免与bo2-6.c重名 */{/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */QueuePtr p;if(Q.front==Q.rear)return ERROR;p=Q.front->next;*e=p->data;return OK;}void EnQueue(LinkQueue *Q,QElemType e){/* 插入元素e为Q的新的队尾元素 */QueuePtr p=(QueuePtr)malloc(sizeof(QNode));if(!p) /* 存储分配失败 */exit(OVERFLOW);p->data=e;p->next=NULL;(*Q).rear->next=p;(*Q).rear=p;}Status DeQueue(LinkQueue *Q,QElemType *e){/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */QueuePtr p;if((*Q).front==(*Q).rear)return ERROR;p=(*Q).front->next;*e=p->data;(*Q).front->next=p->next;if((*Q).rear==p)(*Q).rear=(*Q).front;free(p);return OK;}void QueueTraverse(LinkQueue Q,void(*vi)(QElemType)){/* 从队头到队尾依次对队列Q中每个元素调用函数vi() */QueuePtr p;p=Q.front->next;while(p){vi(p->data);p=p->next;}printf("\n");}
循环队列编辑
循环队列可以更简单防止伪溢出的发生,但队列大小是固定的。
// 队列的顺序存储结构(循环队列)#define MAX_QSIZE 5 // 最大队列长度+1typedef struct { int *base; // 初始化的动态分配存储空间 int front; // 头指针,若队列不空,指向队列头元素 int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置} SqQueue;// 构造一个空队列QSqQueue* Q_Init() { SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue)); // 存储分配失败 if (!Q){ exit(OVERFLOW); } Q->base = (int *)malloc(MAX_QSIZE * sizeof(int)); // 存储分配失败 if (!Q->base){ exit(OVERFLOW); } Q->front = Q->rear = 0; return Q;}// 销毁队列Q,Q不再存在void Q_Destroy(SqQueue *Q) { if (Q->base) free(Q->base); Q->base = NULL; Q->front = Q->rear = 0; free(Q);}// 将Q清为空队列void Q_Clear(SqQueue *Q) { Q->front = Q->rear = 0;}// 若队列Q为空队列,则返回1;否则返回-1int Q_Empty(SqQueue Q) { if (Q.front == Q.rear) // 队列空的标志 return 1; else return -1;}// 返回Q的元素个数,即队列的长度int Q_Length(SqQueue Q) { return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;}// 若队列不空,则用e返回Q的队头元素,并返回OK;否则返回ERRORint Q_GetHead(SqQueue Q, int &e) { if (Q.front == Q.rear) // 队列空 return -1; e = Q.base[Q.front]; return 1;}// 打印队列中的内容void Q_Print(SqQueue Q) { int p = Q.front; while (Q.rear != p) { cout << Q.base[p] << endl; p = (p + 1) % MAX_QSIZE; }}// 插入元素e为Q的新的队尾元素int Q_Put(SqQueue *Q, int e) { if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满 return -1; Q->base[Q->rear] = e; Q->rear = (Q->rear + 1) % MAX_QSIZE; return 1;}// 若队列不空,则删除Q的队头元素,用e返回其值,并返回1;否则返回-1int Q_Poll(SqQueue *Q, int &e) { if (Q->front == Q->rear) // 队列空 return -1; e = Q->base[Q->front]; Q->front = (Q->front + 1) % MAX_QSIZE; return 1;}
陣列佇列编辑
#define MAX_QSIZE 10 // 最大队列长度+1// 阵列队列的存储结构struct Queue { int Array[MAX_QSIZE]; // 阵列空间大小 int front; // 队头 int rear; // 队尾 int length; // 队列长度};// 构造一个空队列QQueue* Q_Init() { Queue *Q = (Queue*)malloc(sizeof(Queue)); if (!Q){ // 存储分配失败 exit(OVERFLOW); } //初始化 Q->front = Q->rear = Q->length = 0; return Q;}// 将Q清为空队列void Q_Clear(Queue *Q) { //清除头尾下标和长度 Q->front = Q->rear = Q->length = 0;}// 入列int Q_Put(Queue *Q, int x) { //如果当前元素数量等于最大数量 返回 -1 if (Q->rear + 1 == MAX_QSIZE) { return -1; } Q->Array[Q->rear] = x; Q->rear = Q->rear + 1; //length + 1 Q->length = Q->length + 1; return 1;}// 出列int Q_Poll(Queue *Q) { //如果当前元素数量等于最大数量 返回 -1 if (Q->front + 1 == MAX_QSIZE) return -1; int x = Q->Array[Q->front]; Q->front = Q->front + 1; // 移出后減少1 Q->length = Q->length - 1; return x;}
参考文献编辑
- ^ 高一凡. 《数据结构》算法实现及解析 2004年10月第2版. 西安: 西安电子科技大学出版社. ISBN 9787560611761 (中文).
参见编辑
🔥 Top keywords: Baike: 首页Special:搜索胖猫跳江事件背着善宰跑九龍城寨之圍城逆天奇案2璩静淚之女王歌手2024Energy (組合)新生 (网络剧)习近平匈牙利邊佑錫劉俊謙 (香港)金智媛神耆小子塞尔维亚金秀賢 (男演員)母亲节猩球崛起:王國誕生九龍寨城馴鹿寶貝家族榮耀之繼承者Seventeen (組合)六四事件不夠善良的我們张维为楊佩潔TripleS支配物种庆余年郭葦昀洪若潭命案金惠奫2024年英雄联盟季中邀请赛春色寄情人BABYMONSTER笑看風雲乘風2024排球少年!!角色列表破墓徐巧芯中华人民共和国中華民國打天下2WIND BREAKER—防風少年—习明泽排球少年!!彭丽媛磁暴ILLIT贾斯汀·比伯逆天奇案BOYNEXTDOOR猿人爭霸戰:猩凶革命張書偉我的婆婆怎麼那麼可愛我獨自升級怪獸8號謝坤達IVE (組合)與鳳行關於我轉生變成史萊姆這檔事角色列表黃道十二宮福建號航空母艦虽然不是英雄葉乃文五月天張員瑛草榴社区張文傑2024年花蓮地震极光香緹·摩爾迷宮飯呂家愷搜查班長1958日本劉德華海莉·鮑德溫蕭景鴻越位 (足球)葬送的芙莉蓮周處除三害 (電影)毛泽东願榮光歸香港林峯周雨彤伍允龍羅毓儀香港Baike: 分類索引沒有秘密猩球崛起:終極決戰角質層唐振剛柯佳嬿文化大革命