【c数据结构】队列详解！(模拟实现、OJ练习实操）

🕗 发布于 2024-10-11 14:18 数据结构

队列的概念

队列就像排队，先进先出，zz先到先得（队头的人先出去，队尾的人排在最后出去）

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

队尾：进⾏插⼊操作
队头：进⾏删除操作
队列的底层是链表（每一个数据是通过一个节点保存的，节点和节点之间是通过指针连接的）

队列的模拟实现

定义队列的结构

两个结构体，一个是其底层->链表的结构，另一个是对链表的优化，给其加上队尾和队头的限制——这就是队列。

//定义队列的结构


//为什么要两个链表呢?
//这是正常链表的结构
typedef int QDataType;
typedef struct QueueNode {
QDataType data;
QueueNode* next;
}QueueNode;
//对于链表的维护，给链表多一个队尾和队头的限制，这就是队列
typedef struct Queue {
 QueueNode* phead;//指向头节点的指针---队头--删除数据
     QueueNode* ptail;//指向尾节点的指针---队尾--插入数据
     int size;//保存队列有效个数
}Queue;

Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 


//定义队列的结构


//为什么要两个链表呢?
//这是正常链表的结构
typedef int QDataType;
typedef struct QueueNode {
    QDataType data;
    QueueNode* next;
}QueueNode;
//对于链表的维护，给链表多一个队尾和队头的限制，这就是队列
typedef struct Queue {
    QueueNode* phead;//指向头节点的指针---队头--删除数据
    QueueNode* ptail;//指向尾节点的指针---队尾--插入数据
    int size;//保存队列有效个数
}Queue;

 
 
//初始化
void QueueInit(Queue* pq);
 
//入队列，队尾   插入数据
void QueuePush(Queue* pq, QDataType x);
 
//出队列,队头    删除数据
void QueuePop(Queue* pq);
 
//判断队列是否为空
bool Queuempty(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;
}

//判断队列是否为空
bool Queuempty(Queue* pq) {
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
//是空，返回true
}

//入队列，队尾   插入数据
void QueuePush(Queue* pq, QDataType x) {
assert(pq);
//创建新结点并对其初始化
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode*));
if (newnode)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;

//判断队列是否为空
if (pq->phead == pq->ptail == NULL) {
//此时newnode既是头结点也是尾节点
pq->phead = pq->ptail = newnode;
}
else//不为空，队尾插入
{
//原尾结点指向新结点
pq->ptail->next = newnode;
//尾哨兵走到下一位（最后一结点）
pq->ptail = pq->ptail->next;
}
}

//出队列,队头    删除数据
void QueuePop(Queue* pq) {
assert(pq);
//注意空的队列没法删东西！
//——判断队列是否为空！
assert(!Queuempty(pq));

//只有一个结点时头结点没有下一位，需要另外处理
if (pq->ptail ==pq->ptail) //头尾哨兵指针指向相同，说明只有一个结点
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else//否则 多个结点
{
//创建临时的结点保存新头结点（头哨兵的下一位）的数据
QueueNode* pcur = pq->phead->next;
free(pq->phead);
pq->phead = pcur;
}
--pq->size;

}



//取队头数据
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(!Queuempty(pq));//队列不为空
return pq->phead->data;
}

//取队尾数据
QDataType QueueBack(Queue* pq) {
assert(pq);
assert(!Queuempty(pq));//队列不为空
return pq->ptail->data;
}

//队列有效元素个数
int QueueSize(Queue* pq) {
assert(pq);

return pq->size;
}

//队列的销毁
void QueueDestroy(Queue* pq) {
assert(pq);
assert(!Queuempty(pq));

//遍历pcur依次释放空间
QueueNode* pcur = pq->phead;
while (pcur) 
{
//销毁之前先把下个节点进行保存,防止丢失位置
QueueNode* Next = pcur->next;
free(pcur);
//将pcur销毁之后，之前保存的next就是新的头结点
pcur = Next;
}

pcur = pq->phead = pq->ptail = NULL;
pq->size = 0;
}

相关OJ练习题实战

1. 用队列实现栈

/*
队列是先进先出
栈是先进后出
*/
 
/*思路：
出栈：找到不为空的队列，将size-1个数据导入到另一个队列中
入栈：往空队列中插入数据
取栈顶元素
 
 
*/
 
//定义队列结构
typedef int QDataType;
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
 
}QueueNode;
 
typedef struct Queue
{
    QueueNode*phead;//指向头节点的指针---队头--删除数据
    QueueNode*ptail;//指向尾节点的指针---队尾--插入数据
    int size;//保存队列有效个数
}Queue ;
 
//初始化
void QueueInit(Queue* pq)
{
    assert(pq);//传过来的不能是空指针 
 
    pq->phead = pq->ptail = NULL;//空的队列
    pq->size = 0;
}
 
//判断队列是否为空
bool Queuempty(Queue* pq)
{
    assert(pq);
 
    return pq->phead == NULL && pq->ptail == NULL;
    //如果后面的表达式成立，那么就是真，返回的是true
 
    //就是说如果这里的是空队列的话，那么就返回的是true
}
 
//入队列，队尾   插入数据
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
 
    //申请新节点
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//申请一个节点大小的空间
    if (newnode == NULL)
    {
        perror("malloc dail!");
        exit(1);
    }
    //对newnode进行初始化操作
    newnode->data = x;
    newnode->next = NULL;
    if (pq->phead == NULL)//说明队列为空
    {
        pq->phead = pq->ptail = newnode;//那么此时的newnode不仅是头结点也是尾节点
    }
    else//队列不为空
    {
        pq->ptail->next = newnode;
        //那么此时的newnode 就是新的ptail
        pq->ptail = newnode;
    }
    pq->size++;
}
 
//出队列,队头    删除数据    从头结点开始删除数据
void QueuePop(Queue* pq)
{
    assert(pq);
    //队列为空（不可删除数据，因为没有数据）
    //队列不为空（可删除数据）
 
    assert(!Queuempty(pq));//队列为空白的话就报错
 
    //处理只有一个节点的情况，避免ptail变成野指针
    //判断只有一个节点的情况
    if (pq->ptail == pq->phead)//头尾指针相同，说明只有一个节点
    {
        free(pq->phead);//随便释放
        pq->phead = pq->ptail = NULL;
    }
    else//处理多个节点的情况
    {
        //删除队头元素
    //那么我们现将下个节点的位置进行保存
        QueueNode* next = pq->phead->next;
        //存储好之后我们直接将头结点进行释放
        free(pq->phead);
        pq->phead = next;//那么之前存的next就是新的头结点了
    }
    pq->size--;
}
 
//取队头数据
QDataType QueueFront(Queue* pq)//返回队头数据
{
    assert(pq);
    assert(!Queuempty(pq));//队列不为空
 
    return pq->phead->data;//将队头里面的数据直接返回就行了
}
 
//取队尾数据
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!Queuempty(pq));//队列不为空
 
    return pq->ptail->data;
}
 
//队列有效元素个数
int QueueSize(Queue* pq)
{
    assert(pq);
    //下面这种遍历的话效率太低了
    //int size = 0;
    定义一个指针进行遍历
    //QueueNode* pcur = pq->phead;//指向队列的头结点
    //while (pcur)//pcur不为空就往后走
    //{
    //  size++;
    //  pcur = pcur->next;
    //}
    //return size;
    return pq->size;
}
 
//队列的销毁
void QueueDestroy(Queue* pq)
{
    assert(pq);
    //assert(!Queuempty(pq));//队列不为空
    //遍历
    QueueNode* pcur = pq->phead;
    while (pcur)
    {
        //销毁之前先把下个节点进行保存
        QueueNode* next = pcur -> next;
        free(pcur);
        //将Pcur销毁之后，那么之前保存的next就是新的头结点
        pcur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
 
 
 
//两个队列来实现栈
typedef struct 
{
    Queue q1;//队列1
    Queue q2;//队列2
} MyStack;
 
//STInit  栈的初始化
MyStack* myStackCreate()
{
    MyStack*pst=(MyStack*)malloc(sizeof(MyStack));//创建一个栈大小的空间
    QueueInit(&pst->q1);//调用初始化函数对q1进行初始化
    QueueInit(&pst->q2);
 
    return pst;
}
 
//那么到这里我们有一个空栈，栈里面有两个队列
 
//入数据
void myStackPush(MyStack* obj, int x)
{
    //往不为空的队列插入数据
    //第一步判断那个队列是非空队列
    if(!Queuempty(&obj->q1))//如果这个队列不是空的话，我们就我那个这个队列里面入数据
    {
        //往队列内插入数据
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
 
}
//出数据
int myStackPop(MyStack* obj)
{
    //找到不为空的队列
    Queue*empQ=&obj->q1;//假设q1是空的，创建指针指向q1
    Queue*noneQ=&obj->q2;//q2不为空，指针指向q2
 
    if(!Queuempty(&obj->q1))//如果q1不为空
    {
        //创建两个指针，noneQ指向的是非空队列，empQ指向的是空队列
        noneQ=&obj->q1;//那么这个非空指针就指向了q1
        empQ=&obj->q2;//那么空指针就指向q2了
    }
    //将不为空内的size-1个数据导入到另一个队列里面
    while(QueueSize(noneQ)>1)//循环条件是非空队列里面只剩下一个有效的数据了
    {
        int front=QueueFront(noneQ);//获取这个非空队列里面的队头数据
        QueuePush(empQ,front);//往空队列里面循环插入队头数据
        QueuePop(noneQ);//因为我们这个非空队列的队头数据已经拿出去了 ，那么我们就将非空队列进行删除数据操作
    }
    //非空队列中只剩下一个数据----那么这个数据就是要出栈的数据
    int pop=QueueFront(noneQ);//获取剩下的这个元素
    QueuePop(noneQ);//进行出数据操作
    return pop;//返回我们要的值
 
}
 
//取栈顶元素  假设插入1 2 3，那么栈顶就是3   这里是2两个队列
int myStackTop(MyStack* obj)   
{
    //找到不为空的队列，取队尾元素
    if(!Queuempty(&obj->q1))//如果第一个队列不为空的话
    {
        return QueueBack(&obj->q1);//直接将取到的队尾元素进行返回就行了
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
//判读栈是否为空
bool myStackEmpty(MyStack* obj)
{
    //两个队列如果都为空的话，那么这个栈就是空的
    return Queuempty(&obj->q1)  &&  Queuempty(&obj->q2);
}
//销毁
void myStackFree(MyStack* obj)
{
    //就是栈内的连个队列的销毁
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);//将我们之前申请的栈空间进行释放掉
    obj=NULL;
}
 
/**
 * 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);
*/

2. 用栈实现队列




//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
    STDataType* arr;
    int capacity;//栈的空间大小
    int top;//栈顶（插入数据和删除数据的位置）
}ST;
//初始化
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//传的是地址

//销毁
void STDestory(ST* ps)
{
assert(ps);
if (ps->arr != NULL)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->top = 0;
}

//栈顶-=--如数据、出数据

//栈的入数据操作
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//判断空间是否满了
if (ps->capacity == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}

//判断栈是否为空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
//栈的出数据操作
void StackPop(ST* ps)
{
assert(ps);
//判断是否为空
assert(!StackEmpty(ps));
--ps->top;
}

//取栈顶元素---循环打印栈顶的数据
//返回值是栈顶的元素
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top-1];
}



//获取栈中有效个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}


typedef struct {
ST STpop;
ST STpush;
} MyQueue;


MyQueue* myQueueCreate() {
MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&pst->STpop);
STInit(&pst->STpush);
return pst;
}

void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->STpush,x);
}

int myQueuePop(MyQueue* obj) {
//1.检查popST是否为空
   //1)不为空直接 出
   //2)为空，pushST导入到popST,在出数据
if (StackEmpty(&obj->STpop))
{
while (!StackEmpty(&obj->STpush))
{
StackPush(&obj->STpop, StackTop(&obj->STpush));
StackPop(&obj->STpush);
}
}
int tmp = StackTop(&obj->STpop);
StackPop(&obj->STpop);
return tmp;
}

int myQueuePeek(MyQueue* obj) {
//判断pop栈是否为空
if (StackEmpty(&obj->STpop))
{
//为空，将push的数据全部导入pop
while (!StackEmpty(&obj->STpush))
{
//每次取push的栈顶元素
StackPush(&obj->STpop, StackTop(&obj->STpush));
//为保证能取下一个栈顶，记得先删除原栈顶
StackPop(&obj->STpush);
}
}
return StackTop(&obj->STpop);
}

bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->STpush) && StackEmpty(&obj->STpop);
}

void myQueueFree(MyQueue* obj) {
STDestory(&obj->STpop);
STDestory(&obj->STpush);
free(obj);
obj = NULL;
}

3. 设计循环队列

/*
//循环队列的容量大小是k
我们用数组作底层，数组大小为k+1，最后一个数组元素不存储数据，单纯占位置
假设我们需要4个大小的数组，那么就申请5个空间
0 1 2 3 4 这是数组下标
一开始front和rear都指向下标为0的位置，每插入一个元素，rear++
直至rear到下标为4的位置，说明空间满了
因为循环rear又应该会回到front位置

判断空间是否满了 (rear+1) % (k+1) ==  (front)
判断空间是否为空 rear == front
*/


typedef struct {
    int* arr;//动态数组的指针，因为不知道数组具体大小
    int front;
    int rear;
    int capacity;//这个是保存数组空间大小k
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    //创建新队列
    MyCircularQueue* pst =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));

    //队列里的内容初始化

    //因为队列的底层空间是数组
    //所以动态数组开辟一个空间
    pst->arr = (int*)malloc(sizeof(int)*(k+1));//我们给数组申请K+1个整型大小的空间
    pst->front = pst->rear = 0;
    pst->capacity = k;
    return pst;
}

//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->rear == obj->front;
}

//判断队列是否满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //capacity+1是数组的容量大小，多出的1是用来占位置的
    return (obj->rear+1) % (obj->capacity+1) == obj->front;
}


//向循环队列里面插入数据，如果成功插入就返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //先判断队列是否满了，容量满了无法插入数据
    if(myCircularQueueIsFull(obj))
    return false;

    //走到这里说明没满，可以插入数据
    obj->arr[obj->rear++]=value;
    //由于是循环，rear只会在容量大小范围内的数组中插入元素
    //即为了保证循环的效果
    /*
    假设我们的rear此时在占位置的那个位置，就是多出来的1的那个位置
    为了保证循环，我们要让rear回到数组的第一个位置 */
    obj->rear = (obj->rear) % (obj->capacity+1); //求余使得rear只会在k的范围内
    //求余结果赋给rear

     //插入完成我们就返回true
    return true;
}


//从循环队列中删除一个元素，成功删除就返回true
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //删除元素，则队列不可为空
    if(myCircularQueueIsEmpty(obj))
    return false;//为空，返回false

    //不为空，可以删除操作
    //front换位置了，原先front的数据可被覆盖
    obj->front++;
    //同样，为了保证只在容量范围内增删数据，取余操作
    obj->front %= (obj->capacity+1);

    return true;
}

//取对首元素，返回对应值
int myCircularQueueFront(MyCircularQueue* obj) {
    //队列为空取个啥
    if(myCircularQueueIsEmpty(obj))//按题目要求，队列为空返回-1
    return -1;

    return obj->arr[obj->front];
}


//取对尾元素，返回对应值
int myCircularQueueRear(MyCircularQueue* obj) {
    //队列为空取个啥
    if(myCircularQueueIsEmpty(obj))//按题目要求，队列为空返回-1
    return -1;

    //正常情况你肯定以为这么写return obj->arr[obj->rear];
    //但是若rear在下标为0呢？返回数组下标为-1的值？不纯纯搞笑吗

    //定义一个指针来指向rear-1
    int prev = obj->rear-1;
    if(obj->rear == 0)
    {
        //保证循环效果，rear下标为0的时候rear-1在最后一个下标处
        prev = obj->capacity;
    }
    return obj->arr[prev];
}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
    obj=NULL;
}

希望对你有帮助

原文地址：https://blog.csdn.net/2301_80038570/article/details/142555465

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：spring boot的发展历程
下一篇：【策略】第二十三期：为什么90%的回测没什么卵用？

Golang Slice扩容机制及注意事项
在 Go语言中，Slice（切片）是一种非常灵活且强大的数据结构，它是对数组的抽象，提供了动态数组的功能。Slice 的扩容机制是自动的，但了解其背后的原理对于编写高效、可预测的 Go 程序至关重要。
阅读更多2024-10-13
【更新】A股上市公司企业网络安全治理数据集（2007-2023年）
参考C刊《金融评论》王辉（2024）老师的做法，安全治理种子词的选取主要依托于《中华人民共和国网络安全法》、《中华人民共和国数据安全法》、《关键信息基础设施安全保护条例》等法律法规文件与《网络安全审查
阅读更多2024-10-13
Go 语言中的格式化占位符
在 Go 语言中，fmt包提供了大量的格式化占位符，用于格式化输出不同类型的数据。选择合适的占位符，可以确保输出的内容格式正确、清晰易懂。
阅读更多2024-10-13
【力扣150&Golang】分发糖果
n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。1请你给每个孩子分发糖果，计算并返回需要准备的。5你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。4你可以分别给第一
阅读更多2024-10-13
jenkins 插件Publish Over SSH (sskey) 同步文件夹
目标：/root/images2。将ssh免密登录的私钥新建到。二、添加sshkey。
阅读更多2024-10-13
kali linux 允许 root 用户登录安装过程中不能创建 root 根用户密码之后不能以根用户直接登录即使是正确的管理员密码也无法登录
打开终端。输入命令并按回车键。系统会提示您输入新的 UNIX 密码，输入您想要设置的密码并按回车键。再次输入相同的密码进行确认。如果密码设置成功，会显示 “passwd: password updat
阅读更多2024-10-13
矫平机：工业制造中的平整专家
矫平机以其高效、精准的矫正能力，已经成为现代工业制造中不可或缺的设备。它不仅提高了生产效率，保证了产品质量，还符合了环保节能的未来趋势。随着技术的不断进步，矫平机将继续在工业制造领域发挥其重要作用。
阅读更多2024-10-13
「漏洞复现」同望OA tooneAssistantAttachement.jsp 任意文件读取漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-13
NVM（Node Version Manager）：简介、安装
NVM（Node Version Manager）是一个用于在同一台机器上安装、管理和切换多个Node.js版本的工具。它解决了开发者在处理具有不同Node.js版本依赖关系的项目时所面临的难题。通过
阅读更多2024-10-13
SpringBoot框架下购物推荐系统的架构与实现
在概念模式的设计中，E-R模型法是最常见的设计方法。B/S架构的运行方式是在远程的服务器上把开发的软件系统部署在远程的服务器上，在部署好软件系统之后就可以实现在任何接入互联网的电脑上访问部署好的软件系
阅读更多2024-10-13