0
0

【数据结构】队列

文章目录

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

image-20220804162855428

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低

image-20220804170034552

话不多说，我们直接来实现队列：(一定要记得自己去实现一个队列)

1.队列的结构

队列的初始化是比较简单的：由单链表构成，一个结构体为队列的结点，但是只有一个指针，我们需要队头和队尾，方便队头删除，队尾插入(所以不需要前面那些什么头删、尾删，队列中队头是用来删除的，队尾是用来插入的)所以另一个结构体为队列的头、尾指针

typedefint QDataType;typedefstructQueueNode{structQueueNode* next;
    QDataType data;}QNode;typedefstructQueue{
    QNode* head;
    QNode* tail;int size;}Queue;

在这个地方，这里有两个结构体哦，我们不需要二级指针：

我们只需要改结构体（只需要改变结构体里面的head和tail），我们只需要结构体的指针(一级指针)即可

2.初始化

voidQueueInit(Queue* pq){assert(pq);
    pq->head = pq->tail =NULL;
    pq->size =0;}

3.销毁

voidQueueDestroy(Queue* pq){assert(pq);
    QNode* cur = pq->head;while(cur){
        QNode* del = cur;
        cur = cur->next;free(del);}
    pq->head = pq->tail =NULL;}

4.入队

voidQueuePush(Queue* pq, QDataType x){assert(pq);
    QNode* newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){perror("malloc fail");exit(-1);}else{
        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++;}

5.判断是否为空

bool QueueEmpty(Queue* pq){assert(pq);return pq->head ==NULL&& pq->tail ==NULL;}

6.出队

voidQueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));if(pq->head->next ==NULL){free(pq->head);
        pq->head = pq->tail =NULL;}else{
        QNode* del = pq->head;
        pq->head = pq->head->next;free(del);
        del =NULL;}
    pq->size--;}

7.队头元素

QDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}

8.队尾元素

QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}

9.元素个数

QDataType QueueSize(Queue* pq){assert(pq);
    QNode* cur = pq->head;/*int n = 0;
    while (cur)
    {
        ++n;
        cur = cur->next;
    }
    return n;*/return pq->size;}

完整代码

Queue.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefint QDataType;typedefstructQueueNode{structQueueNode* next;
    QDataType data;}QNode;typedefstructQueue{
    QNode* head;
    QNode* tail;int size;}Queue;voidQueueInit(Queue* pq);voidQueueDestroy(Queue* pq);voidQueuePush(Queue* pq,QDataType x);voidQueuePop(Queue* pq);

QDataType QueueFront(Queue* pq);

QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);

QDataType QueueSize(Queue* pq);

Queue.c

#include"Queue.h"voidQueueInit(Queue* pq){assert(pq);
    pq->head = pq->tail =NULL;
    pq->size =0;}voidQueueDestroy(Queue* pq){assert(pq);
    QNode* cur = pq->head;while(cur){
        QNode* del = cur;
        cur = cur->next;free(del);}
    pq->head = pq->tail =NULL;}voidQueuePush(Queue* pq, QDataType x){assert(pq);
    QNode* newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){perror("malloc fail");exit(-1);}else{
        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++;}voidQueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));if(pq->head->next ==NULL){free(pq->head);
        pq->head = pq->tail =NULL;}else{
        QNode* del = pq->head;
        pq->head = pq->head->next;free(del);
        del =NULL;}
    pq->size--;}

QDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}

QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}

bool QueueEmpty(Queue* pq){assert(pq);return pq->head ==NULL&& pq->tail ==NULL;}

QDataType QueueSize(Queue* pq){assert(pq);
    QNode* cur = pq->head;/*int n = 0;
    while (cur)
    {
        ++n;
        cur = cur->next;
    }
    return n;*/return pq->size;}

test.c

//test.c部分这里只是对上面的部分函数进行测试，如果有需要的话也可以自己设计成菜单界面

#include"Queue.h"voidTestQueue(){
    Queue q;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePush(&q,4);while(!QueueEmpty(&q)){printf("%d ",QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);}intmain(){TestQueue();return0;}

对于队列的实现并不难，下面，我们就来做几道有关队列的OJ题目把👇

队列OJ题

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（

push

、

top

、

pop

和 

empty

）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

题目的意思其实很简单：就是让你用两个队列去模拟实现一个栈

思路：思路其实很简单，我们知道队列是先进先出，而栈是后进先出，两个最大的不同在于顺序：

我们假设在队列入了1，2，3，4那么现在要在队列中出一个元素，那就是1
如果在栈中入了1，2，3，4那么现在要在栈中出一个元素，那就是4

我们该怎么改变这种顺序呢？很简单，让有元素队列把前n-1个导入到空的队列，此时取出剩下的元素就是符合栈顺序的元素，我们不妨来画个图：

image-20220805154451427

取出4之后,q1又变成了空队列。继续倒

image-20220805154814863

这道题的思路不难，但是实现起来比较麻烦，可能做的时候多多少少有有一些细节没注意到，导致编译出现错误，不过问题不是很大。话不多说直接搬上我们的代码：

#include<stdio.h>#include<assert.h>#include<stdlib.h>//直接手撸一个队列typedefint QDataType;typedefstructQueueNode{
    QDataType data;structQueueNode*next;}QNode;typedefstructQueue{
    QNode*head;
    QNode*tail;int size;}Queue;voidQueueInit(Queue*pq);voidQueueDestroy(Queue*pq);voidQueuePush(Queue*pq,QDataType x);voidQueuePop(Queue*pq);
QDataType QueueFront(Queue*pq);
QDataType QueueBack(Queue*pq);
bool QueueEmpty(Queue*pq);
QDataType QueueSize(Queue*pq);voidQueueInit(Queue*pq){assert(pq);
    pq->head = pq->tail =NULL;
    pq->size =0;}voidQueueDestroy(Queue*pq){assert(pq);
    QNode*cur = pq->head;while(cur){
        QNode*del = cur;
        cur = cur->next;free(del);}
    pq->head = pq->tail =NULL;}voidQueuePush(Queue*pq,QDataType x){assert(pq);
    QNode*newnode =(QNode*)malloc(sizeof(QNode));if(NULL== newnode){exit(-1);}else{
        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++;}voidQueuePop(Queue*pq){assert(pq);assert(!QueueEmpty(pq));if(pq->head->next ==NULL){free(pq->head);
        pq->head = pq->tail =NULL;}else{
        QNode*del = pq->head;
        pq->head = pq->head->next;free(del);
        del =NULL;}
    pq->size--;}
QDataType QueueFront(Queue*pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}
QDataType QueueBack(Queue*pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}
bool QueueEmpty(Queue*pq){assert(pq);return pq->head ==NULL&&pq->tail ==NULL;}
QDataType QueueSize(Queue*pq){return pq->size;}//定义了两个队列，一个为q1,另一个为q2typedefstruct{
    Queue q1;
    Queue q2;} MyStack;

MyStack*myStackCreate(){
    MyStack*obj =(MyStack*)malloc(sizeof(MyStack));if(NULL== obj){exit(-1);}QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;}voidmyStackPush(MyStack* obj,int x){//看哪个是否为空if(!QueueEmpty(&obj->q1)){//谁不为空就插入数据QueuePush(&obj->q1,x);}//q2可能为空或不为空else{QueuePush(&obj->q2,x);}}intmyStackPop(MyStack* obj){//删除栈顶的元素，先找出那个不为空的队列，在把数据导入
    Queue*empty =&obj->q1;
    Queue*nonEmpty =&obj->q2;if(!QueueEmpty(&obj->q1)){
        empty =&obj->q2;
        nonEmpty =&obj->q1;}//剩下一个元素while(QueueSize(nonEmpty)>1){//取队头数据存放到空的队列,最后剩下一个，这个就是栈顶的元素QueuePush(empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int top =QueueFront(nonEmpty);QueuePop(nonEmpty);return top;}intmyStackTop(MyStack* obj){//取栈的头相当于非空的队列的队尾if(!QueueEmpty(&obj->q1)){returnQueueBack(&obj->q1);}else{returnQueueBack(&obj->q2);}}

bool myStackEmpty(MyStack* obj){returnQueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}voidmyStackFree(MyStack* obj){QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);}/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

image-20220805160953150

一个队列实现栈

image-20220806133528269

还是上面那道题，我们用一个队列来试一试：

#include<stdio.h>#include<assert.h>#include<stdlib.h>typedefint QDataType;typedefstructQueueNode{
    QDataType data;structQueueNode*next;}QNode;typedefstructQueue{
    QNode*head;
    QNode*tail;int size;}Queue;voidQueueInit(Queue*pq);voidQueueDestroy(Queue*pq);voidQueuePush(Queue*pq,QDataType x);voidQueuePop(Queue*pq);
QDataType QueueFront(Queue*pq);
QDataType QueueBack(Queue*pq);
bool QueueEmpty(Queue*pq);
QDataType QueueSize(Queue*pq);voidQueueInit(Queue*pq){assert(pq);
    pq->head = pq->tail =NULL;
    pq->size =0;}voidQueueDestroy(Queue*pq){assert(pq);
    QNode*cur = pq->head;while(cur){
        QNode*del = cur;
        cur = cur->next;free(del);}
    pq->head = pq->tail =NULL;}voidQueuePush(Queue*pq,QDataType x){assert(pq);
    QNode*newnode =(QNode*)malloc(sizeof(QNode));if(NULL== newnode){exit(-1);}else{
        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++;}voidQueuePop(Queue*pq){assert(pq);assert(!QueueEmpty(pq));if(pq->head->next ==NULL){free(pq->head);
        pq->head = pq->tail =NULL;}else{
        QNode*del = pq->head;
        pq->head = pq->head->next;free(del);
        del =NULL;}
    pq->size--;}
QDataType QueueFront(Queue*pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}
QDataType QueueBack(Queue*pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}
bool QueueEmpty(Queue*pq){assert(pq);return pq->head ==NULL&&pq->tail ==NULL;}
QDataType QueueSize(Queue*pq){return pq->size;}//一个队列typedefstruct{
    Queue q;} MyStack;

MyStack*myStackCreate(){
   MyStack*obj =(MyStack*)malloc(sizeof(MyStack));QueueInit(&obj->q);return obj;}voidmyStackPush(MyStack* obj,int x){//先让数据入队QueuePush(&obj->q,x);int i =0;//1个元素就不用处理while(i<QueueSize(&obj->q)-1){int front =QueueFront(&obj->q);QueuePop(&obj->q);QueuePush(&obj->q,front);
        i++;}}intmyStackPop(MyStack* obj){int tmp =QueueFront(&obj->q);QueuePop(&obj->q);return tmp;}intmyStackTop(MyStack* obj){returnQueueFront(&obj->q);}

bool myStackEmpty(MyStack* obj){returnQueueEmpty(&obj->q);}voidmyStackFree(MyStack* obj){QueueDestroy(&obj->q);free(obj);}/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

image-20220806140732200

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

image-20220805165417440

这道题和上面的那道题是相反的，这里要让你用两个栈去实现队列，思路也是差不多的，但是对于两个栈来说，就存在一些差别了：我们还是以入栈1、2、3、4来举例子：

image-20220805170106089

image-20220805174555175

image-20220805180656441

所以两个栈我们可以一个为PopST进行出数据的操作，出空了，再去另一个栈PushST将数据倒过来，仔细琢磨琢磨

废话不多说：

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//手撸一个栈typedefint STDataType;typedefstructStack{
    STDataType*a;int top;int capacity;}ST;voidStackInit(ST* ps);voidStackDestory(ST* ps);voidStackPush(ST* ps,STDataType x);voidStackPop(ST* ps);

STDataType StackTop(ST* ps);

bool StackEmpty(ST*ps);intStackSize(ST* ps);voidStackInit(ST* ps){assert(ps);
    ps->a =NULL;
    ps->capacity = ps->top =0;}voidStackDestory(ST* ps){assert(ps);free(ps->a);
    ps->a =NULL;
    ps->capacity = ps->top =0;}voidStackPush(ST* ps, STDataType x){assert(ps);if(ps->top == ps->capacity){int newCapacity = ps->capacity ==0?4: ps->capacity *2;
        STDataType* tmp =(STDataType*)realloc(ps->a, newCapacity *sizeof(STDataType));if(NULL== tmp){perror("malloc fail");exit(-1);}
        ps->a = tmp;
        ps->capacity = newCapacity;}
    ps->a[ps->top]= x;
    ps->top++;}voidStackPop(ST* ps){assert(ps);assert(!StackEmpty(ps));
    ps->top--;}

STDataType StackTop(ST* ps){assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top -1];}

bool StackEmpty(ST* ps){assert(ps);return ps->top ==0;}intStackSize(ST* ps){assert(ps);return ps->top;}typedefstruct{
    ST pushST;
    ST popST;} MyQueue;

MyQueue*myQueueCreate(){
    MyQueue *obj =(MyQueue*)malloc(sizeof(MyQueue));StackInit(&obj->pushST);StackInit(&obj->popST);return obj;}//入队voidmyQueuePush(MyQueue* obj,int x){//有数据就直接进入PushST栈StackPush(&obj->pushST,x);}voidpushSTtopopST(MyQueue*obj){//先把popST栈的数据给出栈,如果没有数据就让pushST栈的数据进入if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}}//出队intmyQueuePop(MyQueue* obj){pushSTtopopST(obj);int front =StackTop(&obj->popST);StackPop(&obj->popST);return front;}//取队头元素intmyQueuePeek(MyQueue* obj){pushSTtopopST(obj);returnStackTop(&obj->popST);}

bool myQueueEmpty(MyQueue* obj){returnStackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);}voidmyQueueFree(MyQueue* obj){StackDestory(&obj->popST);StackDestory(&obj->pushST);}/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

image-20220805211324038

设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

循环队列没啥好说的（关键在于取模问题）。而且学校的考试题很喜欢考循环队列这一块，我们不妨来看一道选择题：

现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据，假设多给一个空间，实际空间大小为N)
A (rear - front + N) % N + 1
B (rear - front + N) % N
C ear - front) % (N + 1)
D (rear - front + N) % (N - 1)

解析：答案选B.

image-20220805234513460

下面我们来看一看上面的题目：

对于结构体的定义：我们需要一个数组存放数据，同时还有队头和队尾，以及空间的大小。

我们来区分一下如何判断是否为空和是否为满的情况：

空的时候，队头==队尾

满的时候，(队尾+1)%空间的大小==队头。后面一些细节的东西，我们直接来看代码：

对于这道题给的函数有一点坑：

我们去调用bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);都要去先进行函数的声明，这两个函数是放在下面，或者我们直接把这两个函数提前也可.

typedefstruct{int*a;int front;int back;int N;} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//记得要函数声明
bool myCircularQueueIsFull(MyCircularQueue* obj);//记得函数声明
MyCircularQueue*myCircularQueueCreate(int k){
    MyCircularQueue*obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多一个空间
    obj->a =(int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->back =0;
    obj->N = k+1;return obj;}//入队——往尾部入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj,int value){if(myCircularQueueIsFull(obj)){return false;}else{
        obj->a[obj->back]= value;
        obj->back++;//到尾
        obj->back %= obj->N;return true;}}//出队——头部出数据
bool myCircularQueueDeQueue(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){return false;}
    obj->front++;//到尾
    obj->front %= obj->N;return true;}//队头元素intmyCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){return-1;}else{return obj->a[obj->front];}}//队尾元素intmyCircularQueueRear(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){return-1;}//处理当obj->back = 0的时候else{return obj->a[(obj->back-1+obj->N)%obj->N];}}//判断是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj){return obj->front == obj->back;}//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj){//处理一下return(obj->back+1)%obj->N==obj->front;}//释放voidmyCircularQueueFree(MyCircularQueue* obj){free(obj->a);free(obj);}/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

image-20220806131643310

标签： 数据结构 链表 算法
本文转载自: https://blog.csdn.net/weixin_60478154/article/details/126194251
版权归原作者 平凡的人1 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【数据结构】队列”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航