1.队列的概念
队列是一种特殊的线性表，特殊在只能从一端进行插入操作，另一端进行删除操作，队列具有Fist In First Out的原则。
队尾：进行插入操作的一端，这个过程叫做入队列
队头：进行删除操作的一端，这个过程叫做出队列
抽号机：先来先服务，先给号码排队 （涉及嵌入式）
2.队列的结构
队列我们采用链表实现：顺序表在满了要扩容，删完了后再入队列的时候还得扩容
链表的话，入队列就是尾插，定义一个尾指针。出队列就是头删，定义一个头指针
3.实现队列的基本操作
3-1结构体定义
typedef int QDateType; typedef struct QueueNode { struct QueueNode* next; QDateType val; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue;
3-2队列的初始化
这里的链表队列我并没有带头，没有带头就要在入队列和出队列时有一点特殊情况的考虑
void QueueInit(Queue* ps) { assert(ps); ps->head = ps->tail = NULL; }
3-3入队列
相当于尾插，考虑特殊情况：队列为空的情况
//入队列：尾插 void QueuePush(Queue* ps,QDateType x) { assert(ps); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->next = NULL; newnode->val = x; if (newnode == NULL) { perror("malloc fail."); exit(-1); } if (ps->tail == NULL) { ps->head = ps->tail = newnode; } else { ps->tail->next = newnode; ps->tail = ps->tail->next; } }
3-4出队列
相当于头删，考虑特殊情况：只有一个结点的情况，出队列后要改变ps->tail
void QueuePop(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); if (ps->head->next == NULL) { free(ps->head); ps->head = ps->tail = NULL; } else { QueueNode* next = ps->head->next; free(ps->head); ps->head = next; } }
3-5取队头元素
QDateType QueueFront(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->head->val; }
3-6取队尾元素
QDateType QueueBack(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->tail->val; }
3-7队列判空
1. bool QueueEmpty(Queue* ps) 2. { 3. assert(ps); 4. return ps->tail == NULL; 5. }
3-8队列长度
int QueueSize(Queue* ps) { assert(ps); int size = 0; QueueNode* cur = ps->head; while(cur) { ++size; cur = cur->next; } return size; }
3-9队列销毁
void QueueDestory(Queue* ps) { assert(ps); QueueNode* cur = ps->head; while (cur) { QueueNode* next = cur->next; free(cur); cur = next; } ps->head = ps->tail = NULL; }
4.源代码
4-1queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"queue.h" void QueueInit(Queue* ps) { assert(ps); ps->head = ps->tail = NULL; } void QueueDestory(Queue* ps) { assert(ps); QueueNode* cur = ps->head; while (cur) { QueueNode* next = cur->next; free(cur); cur = next; } ps->head = ps->tail = NULL; } //入队列：尾插 void QueuePush(Queue* ps,QDateType x) { assert(ps); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->next = NULL; newnode->val = x; if (newnode == NULL) { perror("malloc fail."); exit(-1); } if (ps->tail == NULL) { ps->head = ps->tail = newnode; } else { ps->tail->next = newnode; ps->tail = ps->tail->next; } } void QueuePop(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); if (ps->head == ps->tail) { free(ps->head); ps->head = ps->tail = NULL; } else { QueueNode* next = ps->head->next; free(ps->head); ps->head = next; } } QDateType QueueFront(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->head->val; } QDateType QueueBack(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->tail->val; } bool QueueEmpty(Queue* ps) { assert(ps); return ps->tail == NULL; } int QueueSize(Queue* ps) { assert(ps); int size = 0; QueueNode* cur = ps->head; while(cur) { ++size; cur = cur->next; } return size; }
4.2queue.h
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDateType; typedef struct QueueNode { struct QueueNode* next; QDateType val; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue; void QueueInit(Queue* ps); void QueuePush(Queue* ps, QDateType x); void QueuePop(Queue* ps); QDateType QueueFront(Queue* ps); QDateType QueueBack(Queue* ps); bool QueueEmpty(Queue* ps); int QueueSize(Queue* ps); void QueueDestory(Queue* ps);
4.3test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"queue.h" int main() { Queue Q; QueueInit(&Q); QueuePush(&Q, 1); QueuePush(&Q, 2); QueuePush(&Q, 3); QueuePush(&Q, 4); QueuePush(&Q, 5); QDateType ret1 = QueueFront(&Q); printf("QueueFront:%d\n", ret1); QDateType ret2 = QueueBack(&Q); printf("QueueBack:%d\n", ret2); int size = QueueSize(&Q); printf("size：%d\n", size); while (!QueueEmpty(&Q)) { printf("%d", QueueFront(&Q)); QueuePop(&Q); } QueueDestory(&Q); return 0; }
4.4效果图
