作者:一个喜欢猫咪的的程序员
专栏:《数据结构》
喜欢的话:世间因为少年的挺身而出,而更加瑰丽。 ——《人民日报》
目录
队列的结构和概念:
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。
队列分为了两种结构
一种是数组,一种是链表。
数组在头删上面效率低,需要挪动数据。
链表头删容易。我们定义一个尾指针tail,我们就可以大大提高尾插的效率了。
链表分为单双,是否循环,是否带头。我们的选择:单链表
Queue.h文件
#pragma once #include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QInit(Queue* pq); void QDestroty(Queue* pq); void QPush(Queue* pq, QDataType x); void QPop(Queue* pq); QDataType QFront(Queue* pq); QDataType QBack(Queue* pq); bool QEmpty(Queue* pq); int QSize(Queue* pq);
Queue.c文件
#include"Queue.h" void QInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } void QDestroty(Queue* pq) { assert(pq); assert(!QEmpty(pq)); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; } void QPush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail==NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QPop(Queue* pq) { assert(pq); assert(!QEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = NULL; pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); del = NULL; } pq->size--; } QDataType QFront(Queue* pq) { assert(pq); assert(!QEmpty(pq)); return pq->head->data; } QDataType QBack(Queue* pq) { assert(pq); assert(!QEmpty(pq)); return pq->tail->data; } bool QEmpty(Queue* pq) { assert(pq); if (pq->head == NULL && pq->tail == NULL) return true; else return false; } int QSize(Queue* pq) { assert(pq); return pq->size; }
这里跟链表的设计差不多,我提几个要注意的点:
- 这里需要assert是因为pq要调用head和tail,理论上一定不为空,pq是指向一个结构体,结构体不为空。
- 这里的循环条件是不等于NULL而不是不等于尾,尾是一个结构体。
- 当头删的时候,可能会照成一种隐藏的bug,当只剩下一个数据的时候,删掉后,head为NULL,tail为野指针,会造成尾插代码的bug。
Test.c文件:
#include"Queue.h" void test1() { Queue pq; QInit(&pq); QPush(&pq, 1); QPush(&pq, 2); QDataType x = QFront(&pq); QDataType y = QBack(&pq); printf("%d %d", x, y); QDestroty(&pq); } int main() { test1(); return 0; }
当我们要改变一个指针的地址的时候有三种方法:
利用二级指针改变一级指针
利用返回值
利用结构体,将指针放在结构体内,传结构体。