概念与结构
概念：只允许在⼀端进行插入数据操作，在另⼀端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。
入队列：进行插入操作的⼀端称为队尾。
出队列：进行删除操作的⼀端称为队头。
队列底层结构选型
队列也可以数组和链表的结构实现，使用链表的结构实现更优⼀些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
队列的代码实现：
Queue.h #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; typedef struct Queue { QueueNode* phead; QueueNode* ptail; int size; }Queue; void QueuePrint(Queue* pq); void QueueInit(Queue* pq); //尾插 void QueueBush(Queue* pq, QDataType x); bool QueueEmpty(Queue* pq); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); int QueueSize(Queue* pq); void QueueDestroy(Queue* pq);
Queue.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueBush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = pq->ptail->next; } pq->size ; } void QueuePrint(Queue*pq) { while (pq->ptail) { printf("%d->", pq->ptail->data); pq->ptail = pq->ptail->next; } } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QueueNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } void QueueDestroy(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QueueNode* pcur = pq->phead; while (pcur) { QueueNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
text.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void QueueText01() { Queue q; QueueInit(&q); QueueBush(&q, 1); QueueBush(&q, 2); QueueBush(&q, 3); QueueBush(&q, 4); //QueuePop(&q); //QueuePop(&q); //QueuePop(&q); //QueuePrint(&q); //QueuePop(&q); //QueuePrint(&q); } int main() { QueueText01(); return 0; }
