0
0

数据结构之队列详解（包含例题）

一、队列的概念

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

二、模拟实现顺序队列

我们可以用单链表模拟实现顺序队列。

队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部（对应单链表的尾插），而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素（对应单链表的头删）。

对应的接口

注意又提供一种避免使用二级指针的方法，创建一个结构体变量，里面存储结点，当我们想要改变结构体里面的值，我们就用一级指针即可。

typedef int QDataType;
typedef struct QueueNode
{
    //用单链表模拟实现队列
    struct QueueNode* next;
    QDataType data;
}QNode;

//新的避免二级指针的结构体
typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int sz;
}Que;

void QueueInit(Que* pq);
void QueueDestory(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueeuPop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);

队列的初始化：

void QueueInit(Que* pq)
{
    assert(pq);
    pq->sz = 0;
    pq->head = pq->tail = NULL;
}

队列的销毁

注意free过后，也要指向空

void QueueDestroy(Que* pq)
{
    assert(pq);
    while (pq->sz > 0)
    {
        QNode* cur = pq->head->next;
        free(pq->head);
        pq->head = cur;
        pq->sz--;
    }
    pq->tail = pq->head = NULL;
}

队列的插入数据

也就是单链表的尾插，同时也要注意当队列为空时的特殊情况。

void QueuePush(Que* pq,QDataType x)
{
    //类似于尾插
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror(malloc);
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
        pq->sz++;
    }
    else
    {
        pq->sz++;
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}

队列的删除数据

也就是单链表的头删，同时也要注意只剩下一个结点删除后，尾结点指向空的情况


void QueeuPop(Que* pq)
{
    assert(pq);
    assert(pq->sz > 0);
    //头删
    //单独判断只剩下一个结点，头删后tail是野指针的情况
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
        pq->sz--;
    }
    else
    {
        QNode* cur = pq->head;
        pq->head = pq->head->next;
        free(cur);
        pq->sz--;
    }
    
}

返回队列头数据

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

返回队列尾数据

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

判断队列是否为空

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

返回队列的数据个数

int QueueSize(Que* pq)
{
    assert(pq);
    //assert(pq->head);
    return pq->sz;
}

三、模拟实现循环队列

  1. 设计循环队列 - 力扣（LeetCode）

这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。

注意本题结构较为复杂，必须要画图进行解决，这样就容易考虑到特殊情况，不容易出错。

本题用数组实现较为简单，如果用单链表实现，那么rear尾结点的前一个不好寻找。

那数组如何实现循环呢？

数组实现循环并不像单链表那样有一个next指针指向头结点，如果已经走向尾部，可以直接让头部的值等于尾部想要的值。

//如何用数组实现循环？
typedef struct {
    int* a;
    int front;
    int rear;
    int num;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cur = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //用k+1个数组空间，便于判断空和满的情况。
    cur->a = (int*)malloc(sizeof(int)*(k+1));
    cur->front = 0;
    cur->rear = 0;
    cur->num = k;
    return cur;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front == obj->rear)
        return true;
    else
        return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //两种情况都要考虑到！
    if(obj->front-obj->rear == 1 || obj->rear-obj->front == obj->num)
        return true;
    else
        return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //先判断是否已经满
    if(myCircularQueueIsFull(obj) == true)
        return false;
    //假设rear在队列的尾部
    if(obj->rear == obj->num)
    {
        obj->a[obj->rear] = value;
        obj->rear = 0;
    }
    else
    {
        obj->a[obj->rear] = value;
        obj->rear++;
    }
    //obj->a[obj->rear] = value;
    //obj->rear++;
    //obj->rear %= (obj->num+1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //先判断是否已经空了
    if(myCircularQueueIsEmpty(obj) == true)
    {
        return false;
    }
    //假设front在队列的尾部
    if(obj->front == obj->num)
        obj->front = 0;
    else
        obj->front++;
    //++obj->front;
    //obj->front %= (obj->num+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj) == true)
        return -1;
    else
        return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    //注意队尾的rear比数据提前一位数，所以是rear-1
    //但要考虑rear-1的情况
    if(myCircularQueueIsEmpty(obj) == true)
        return -1;
    if(obj->rear == 0)
    {
        //需要再创建一个临时变量，不能改变rear的值
        int tmp = obj->num;
        return obj->a[tmp];
    }
    // else
    //     return  obj->a[(obj->rear+obj->num)%(obj->num+1)];
    return obj->a[obj->rear-1];
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

四、用队列实现栈

  1. 用队列实现栈 - 力扣（LeetCode）

本题要求用两个队列实现栈，两个队列我们就可以互相倒数据，来满足题目对栈的需求！

思路：

入队列：

入不为空的队列

出队列：

利用队列的性质将前n-1个数据放入另一个空的队列中，删除剩下一个数据，这样就完成栈的pop操作！

代码：

typedef struct {
    Que q1;
    Que q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* cur = (MyStack*)malloc(sizeof(MyStack));
    //不能忘记初始化
    QueueInit(&cur->q1);
    QueueInit(&cur->q2);
    return cur;
}

void myStackPush(MyStack* obj, int x) {
    //push到不为空的的队列中
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //先假设q1不为空，q2为空
    Que* empty = &obj->q1;
    Que* nonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        //如果假设失败，相反
        empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    while(QueueSize(nonEmpty)>1)
    {
        //开始用函数进行捯数据
        //从前往后的顺序是根据队列pop的顺序定的
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int top = QueueBack(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

int myStackTop(MyStack* obj) {
    Que* empty = &obj->q1;
    Que* nonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        //如果假设失败，相反
        empty = &obj->q2;
        nonEmpty = &obj->q1;
    }
    return QueueBack(nonEmpty);
}

bool myStackEmpty(MyStack* obj) {
    //判断两个队列
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    //先对两个队列中的链表进行free
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

五、用栈实现队列

  1. 用栈实现队列 - 力扣（LeetCode）

题目描述：

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

push

、

pop

、

peek

、

empty

）：

思路：

本题与上一题用队列实现栈有所差别，可以直接区分push栈和pop栈，如果pop栈为空，就将push栈全部捯到pop栈！

代码：

typedef struct 
{
    ST push;
    ST pop;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue* cur = (MyQueue*)malloc(sizeof(MyQueue));
    SLInit(&cur->push);
    SLInit(&cur->pop);
    return cur;
}

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

int myQueuePop(MyQueue* obj) {
    
    int ret = myQueuePeek(obj);
    STPop(&obj->pop);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    //出栈只能从后往前出
    //如果pop栈为空，就将push栈全部捯到pop栈！
    if(STEmpty(&obj->pop))
    {
        while(!STEmpty(&obj->push))
        {
            STPush(&obj->pop,STTop(&obj->push));
            STPop(&obj->push);
        }
    }
    int ret = STTop(&obj->pop);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    //用函数求解
    return STEmpty(&obj->push) && STEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
    SLDestroy(&obj->pop);
    SLDestroy(&obj->push);
    free(obj);
}
标签： 数据结构 c语言 队列
本文转载自: https://blog.csdn.net/hanwangyyds/article/details/132270690
版权归原作者 可涵不会debug 所有， 如有侵权，请联系我们删除。
登录后发布评论

“数据结构之队列详解（包含例题）”的评论:

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

安全见闻八：量子计算

【Linux】开发工具make/Makefile、进度条小程序

Linux下学【MySQL】表的必备操作（ 配实操图和SQL语句）

软件测试学习笔记丨Selenium学习笔记：常用页面信息对比方法expected_conditions

将 GitHub 关联到 Git 的详细教程

大数据新视界 -- 大数据大厂之 Impala 性能优化：融合人工智能预测的资源预分配秘籍（上）（29 / 30）

NAT的基本介绍

文章导航