小程序制作pdf,seo收录查询工具,知识库wordpress插件,网站alexa排名查询CSDN的uu们#xff0c;大家好。这里是C语言数据结构的第七讲。 目标#xff1a;前路坎坷#xff0c;披荆斩棘#xff0c;扶摇直上。 博客主页#xff1a;姬如祎队列的基础知识队列#xff08;queue#xff09;是只允许在一端进行插入操作#xff0c;而在另一端进行删除…· CSDN的uu们大家好。这里是C语言数据结构的第七讲。· 目标前路坎坷披荆斩棘扶摇直上。· 博客主页姬如祎队列的基础知识队列queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。队列是一种先进先出First In First Out的线性表简称FIFO。允许插入的一端称为队尾允许删除的一端称为队头。2. 链式存储OR顺序存储线性表有顺序存储和链式存储栈是线性表具有这两种存储方式。同样队列作为一种特殊的线性表也同样存在这两种存储方式。2.1 队列顺序存储的不足顺序存储的队列就是用数组哈数组下标为0的一端即是队头。入队列就是在队尾插入一个数据对于数组而言不需要移动任何元素因此时间复杂度是O(1)。但是在出队列时如果徐翔浪费任何空间的话就需要将全部数据前移。时间复杂度也就是O(N)。当然你也可以参照数组模拟队列的思路维护两个指针frontrear。front指向队头的元素rear指向队尾元素。出队列的时候仅需要将front加一即可。这样以来就有空间的浪费。如此看来使用顺序结构来实现队列不是很理想。如果已经确定了队列的元素个数你可以使用循环队列这样一来数组来实现队列就是非常完美的事了关于循环队列会在栈与队列刷题的那一节提及。2.2 队列的链式存储队列的链式存储结构其实就是线性表的单链表只不过他只能尾进头出而已我们把它简称为链队列。入队就是链表的尾插我们知道如果不做任何处理的话单链表尾插的时间复杂度是O(N)为了使得时间复杂度是O(1)我们需要维护一个指针让他指向链表的尾节点即是队尾。出队就是链表的头删这个操作的时间复杂度是O(1)。队列的链式存储能够在O(1) 的时间复杂度内实现各种操作也没有浪费空间。所以我们优先考虑用链表实现队列。因为我们既要维护指向链表头结点的指针又要维护指向链表尾节点的指针并且我们还需要维护一个变量size来记录队列的大小所以我们将这些变量封装在一个结构体里面便于操作。当然你也可以不这么做那么在函数传参的时候你就需要传多个参数。并且涉及指针的改变形参还必须是二级指针。如果有不理解的地方请参考http://t.csdn.cn/QXmxD 是不是相当滴麻烦。那么我们就将它们封装成一个结构体吧3. 函数接口一览#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.h//方便维护
typedef int QueueDataType;//实现队列的链表的节点
typedef struct QueueNode
{struct QueueNode* next;QueueDataType data;
} QueueNode;//将需要维护的headtailsize封装成结构体
typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
} Queue;//队列的初始化
void QueueInit(Queue* pq);//队列的销毁
void QueueDestory(Queue* pq);//队列是否为空
bool QueueEmpty(Queue* pq);//队尾增加元素
void QueuePush(Queue* pq, QueueDataType x);//出队列
void QueuePop(Queue* pq);//队列的元素个数
int QueueSize(Queue* pq);//队头元素
QueueDataType QueueFront(Queue* pq);//队尾元素
QueueDataType QueueBack(Queue* pq);4. 函数接口的实现4.1 void QueueInit(Queue* pq) 函数的实现队列的初始化需要我们做什么呢将我们封装的结构体里面的变量赋初值注意对pq的断言防止发生空指针的解引用。//队列的初始化
void QueueInit(Queue* pq)
{//断言assert(pq);//赋初值pq-head pq-tail NULL;pq-size 0;
}4.2 void QueueDestory(Queue* pq) 函数的实现销毁队列的主要目的释放堆区开辟的空间也就是释放单链表的每一个节点。这当然需要遍历呀我们维护一个指针例如cur用其遍历单链表让后将遍历到的节点释放。注意保存释放节点的下一个节点就行。还别忘了将我们维护的三个变量headtailsize处理一下防止出现野指针。//队列的销毁
void QueueDestory(Queue* pq)
{//断言防止空指针的解引用assert(pq);//cur指针遍历链表QueueNode* cur pq-head;while (cur){//保存cur指针的下一个节点QueueNode* next cur-next;//释放cur指向的节点free(cur);//迭代cur next;}//处理pq-head pq-tail NULL;pq-size 0;
}4.3 bool QueueEmpty(Queue* pq) 函数的实现这个函数的实现有两种方式1就是判断一下头指针是否为空指针就行头指针为空就说明了链表没有节点也就说明了队列为空。队列为空时尾节点此时也是空指针的哦2我们不是维护了一个变量size嘛其记录了队列的大小我们只需要判断size是不是0就ok啦//队列是否为空
bool QueueEmpty(Queue* pq)
{//断言防止空指针的解引用assert(pq);//one way//return pq-size 0;//another wayreturn pq-head NULL;
}4.4 void QueuePush(Queue* pq, QueueDataType x) 函数的实现前面也提到了入队列的操作就是在链表的尾部插入节点。我们传入的是结构体的指针想要改变结构体里面的head指针tail指针是可以做到的因此队列入数据时注意改变head指针和tail指针就行。当队列为空时需要特殊处理一下同时改变head和tail指向开辟的新节点。//队尾增加元素
void QueuePush(Queue* pq, QueueDataType x)
{//断言防止空指针的解引用assert(pq);//开辟新的节点QueueNode* newNode (QueueNode*)malloc(sizeof(QueueNode));if (newNode NULL){perror(QueuePush::malloc);exit(-1);}else{//数据域赋值newNode-data x;newNode-next NULL;//当队列为空时if (!pq-head){pq-head pq-tail newNode;}else{//链表不为空时pq-tail-next newNode;pq-tail newNode;}pq-size;}
}4.5 void QueuePop(Queue* pq)的实现出队列操作就是链表的头删。理论上我们只需要释放头结点改变head指针的指向就行。但是当队列剩下最后一个元素时如果还是仅改变head指针的指向那么tail指针就会是一个野指针这样做显然是不正确的。因此我们需要对队列只有一个元素的情况进行特殊判断。//出队列
void QueuePop(Queue* pq)
{//防止空指针的解引用assert(pq);//队列为空不允许出队列assert(!QueueEmpty(pq));//one way//对一个节点的情况处理if (pq-head pq-tail){free(pq-head);pq-head pq-tail NULL;}else{//队列中的元素大于一个QueueNode* next pq-head-next;free(pq-head);pq-head next;}//更新sizepq-size--;//another way// 都是处理队列中只有一个元素的情况只不过实现的方式不同//QueueNode* next pq-head-next;//free(pq-head);//pq-head next;//pq-size--;//if (pq-head NULL)// pq-tail NULL;
}4.6 int QueueSize(Queue* pq)函数的实现我们只需要返回我们维护的size变量的值就行。//队列的元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}4.7 QueueDataType QueueFront(Queue* pq)函数的实现我们维护了一个指针head它指向的就是队头元素返回该节点的打他即可。//队头元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);//队列为空不允许查看队头数据assert(!QueueEmpty(pq));return pq-head-data;
}4.8 QueueDataType QueueBack(Queue* pq)函数的实现我们维护了一个指针tail它指向的就是队尾元素我们只需要返回该节点的data即可。//队尾元素
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}
