数据结构之队列

Mr_Xuhhh 2024-08-26 12:05:03 阅读 63

队列

概念

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

⼊队列：进⾏插⼊操作的⼀端称为队尾

出队列：进⾏删除操作的⼀端称为队头

在这里插入图片描述

队列底层结构选型

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

原因如下：

在这里插入图片描述

结构

<code>//定义队列节点结构

structQueueNode

{

int data;

struct QueueNode*next;

}

struct Queue

{

struct QueueNode*phead;

struct QueueNode*tail;

}

队列的底层是链表，但是这里和单链表不同的是要写两个结构体，因为一个是确认底层的，还有一个是确定队列的结构的，因为队列要有队头和队尾

入队列

需要进行分类讨论：队列不为空和队列为空两种情况

在这里插入图片描述

如果队列不为空我们需要尾插一个新元素，然后让ptail指向新元素，如果队列为空，让phead=ptail指向新的元素

代码如下：

<code>// ⼊队列，队尾

void QueuePush(Queue* pq, QDataType x)

{

assert(pq);

//申请新节点

QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));

if (newnode == NULL)

{

perror("malloc fail!");

exit(1);

}

newnode->data = x;

newnode->next = NULL;

//ptail newnode

if (pq->phead == NULL)

{

//队列为空

pq->phead = pq->ptail = newnode;

}

else

{

//队列不为空

pq->ptail->next = newnode;

pq->ptail = newnode;

}

pq->size++;

}

出队列

和栈出数据非常的相似都需要判断队列是否为空队列为空，不可出队列；队列不为空，可以出队列

但是这里也需要注意两种情况

有多个节点的情况下只有一个节点的情况下

在这里插入图片描述

当队列不为空的时候采取头删的方式，然后将phead移向下一节点，如果为空，释放phead

代码如下：

<code>//队列判空

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->phead && pq->ptail == NULL;

}

// 出队列，队头

void QueuePop(Queue* pq)

{

assert(pq);

assert(!QueueEmpty(pq));

//只有一个节点的情况,避免ptail变成野指针

if (pq->phead == pq->ptail)

{

free(pq->phead);

pq->phead = pq->ptail = NULL;

}

else

{

//删除队头元素

QueueNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

}

--pq->size;

}

求有效元素个数

// ⼊队列，队尾

pq->size++;

// 出队列，队头

--pq->size;

元素个数，作为下标的话，指向的是最后一个有效元素的下一个位置

源码

Queue.h

#pragma once

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

#include <stdbool.h>

//定义队列结构

typedef intQDataType;

typedef struct QueueNode

{

int data;

struct 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 QueueEmpty(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;

}

// ⼊队列，队尾

void QueuePush(Queue* pq, QDataType x)

{

assert(pq);

//申请新节点

QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));

if (newnode == NULL)

{

perror("malloc fail!");

exit(1);

}

newnode->data = x;

newnode->next = NULL;

//ptail newnode

if (pq->phead == NULL)

{

//队列为空

pq->phead = pq->ptail = newnode;

}

else

{

//队列不为空

pq->ptail->next = newnode;

pq->ptail = newnode;

}

pq->size++;

}

//队列判空

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->phead && pq->ptail == NULL;

}

// 出队列，队头

void QueuePop(Queue* pq)

{

assert(pq);

assert(!QueueEmpty(pq));

//只有一个节点的情况,避免ptail变成野指针

if (pq->phead == pq->ptail)

{

free(pq->phead);

pq->phead = pq->ptail = NULL;

}

else

{

//删除队头元素

QueueNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

}

--pq->size;

}

//取队头数据

QDataType QueueFront(Queue* pq)

{

assert(pq);

assert(!QueueEmpty(pq));

return pq->phead->data;

}

//取队尾数据

QDataType QueueBack(Queue* pq)

{

assert(pq);

assert(!QueueEmpty(pq));

return pq->ptail->data;

}

//队列有效元素个数

int QueueSize(Queue* pq)

{

assert(pq);

/*int size = 0;

QueueNode* pcur = pq->phead;

while (pcur)

{

size++;

pcur = pcur->next;

}

return size;*/

return pq->size;

}

//销毁队列

void QueueDestroy(Queue* pq)

{

assert(pq);

assert(!QueueEmpty(pq));

QueueNode* pcur = pq->phead;

while (pcur)

{

QueueNode* next = pcur->next;

free(pcur);

pcur = next;

}

pq->phead = pq->ptail = NULL;

pq->size = 0;

}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Queue.h"

void QueueTest01()

{

Queue q;

QueueInit(&q);

QueuePush(&q, 1);

QueuePush(&q, 2);

QueuePush(&q, 3);

QueuePush(&q, 4);

//QueuePop(&q);

//printf("head:%d\n", QueueFront(&q));

//printf("tail:%d\n", QueueBack(&q));

printf("size:%d\n", QueueSize(&q));

QueueDestroy(&q);

}

int main()

{

QueueTest01();

return 0;

}

栈VS队列

在这里插入图片描述

栈的结构图

栈的特性：先进后出（后进先出）

栈的底层结构是数组

逻辑结构：线性的

物理结构：线性的

在这里插入图片描述

队列的结构图

队列的底层结构是单链表

逻辑结构：线性的

物理结构：不一定是线性的

算法题：用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（<code>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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：

["MyStack", "push", "push", "top", "pop", "empty"]

[[], [1], [2], [], [], []]

输出：

[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // 返回 2

myStack.pop(); // 返回 2

myStack.empty(); // 返回 False

提示：

1 <= x <= 9最多调用100 次 push、pop、top 和 empty每次调用 pop 和 top 都保证栈不为空

思路：

首先要想到队列的性质：先进先出和栈的性质：先进后出

接下来来好好看这道题的思路

创建两个队列Q1,Q2

在这里插入图片描述

我们举个例子：

拿1，2，3，4这四个数字举例子

出栈：找不为空的队列，将size-1个数据导入到另一个队列中

入栈：往不为空队列中插入数据

取栈顶元素：找不为空的队列，取队尾元素（不出栈）

步骤如下：

插入1，2，3出栈一次插入4全部出栈

必须保证其中至少一个队列为空

代码如下：

在这里插入图片描述

算法题：用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（<code>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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

输出：

[null, null, null, 1, 1, false]

解释：

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

myQueue.peek(); // return 1

myQueue.pop(); // return 1, queue is [2]

myQueue.empty(); // return false

提示：

1 <= x <= 9最多调用 100 次 push、pop、peek 和 empty假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

思路：

创建两个栈 pushST,popST

在这里插入图片描述

入队：往pushST中插入数据

出队：判断popST是否为空，不为空直接出数据（pop）；为空的话，将pushST中的数据导入到popST中再pop出去

取队头元素：跟出队一样，但是这里只取数据不pop出去

代码如下：

在这里插入图片描述

算法题：设计循环队列（非常硬核）

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

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

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

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

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3

circularQueue.enQueue(1); // 返回 true

circularQueue.enQueue(2); // 返回 true

circularQueue.enQueue(3); // 返回 true

circularQueue.enQueue(4); // 返回 false，队列已满

circularQueue.Rear(); // 返回 3

circularQueue.isFull(); // 返回 true

circularQueue.deQueue(); // 返回 true

circularQueue.enQueue(4); // 返回 true

circularQueue.Rear(); // 返回 4

提示：

所有的值都在 0 至 1000 的范围内；操作数将在 1 至 1000 的范围内；请不要使用内置的队列库。

思路：

我们知道队列的底层结构是链表，但是也是可以通过数组的形式实现的。

假设用链表来解决问题

在这里插入图片描述

如果数据满了，我们需要删除数据会比较繁琐，要先保留头节点的下一节点，然后phead向后走，最前面置空；链表还存在指针的消耗

如果用数组解决问题

在这里插入图片描述

因为插入数据：循环队列满了，就不能插入数据了

优点在于空间固定，更推荐底层结构为数组

创建两个变量，front表示开头的位置，rear表示最后的位置，但是front==rear 无法判断究竟是空间已经满了还是说空了

在这里插入图片描述

多申请出来的一块空间是用来占位置的，来判断是否满了。

这样子做有什么好处呢？不用去额外申请一个结构体变量去计算有效元素个数，提高程序的效率

代码如下：

<code>//定义循环队列的结构

typedef struct {

int* arr;//大小不确定，所以要动态开辟

int front;//头

int rear;//尾

int capacity;

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {

MyCircularQueue* pst = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

pst->arr = (int*)malloc(sizeof(int) * (k + 1));

pst->front = pst->rear = 0;

pst->capacity = k;

return pst;

}

bool myCircularQueueIsFull(MyCircularQueue* obj)

{

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;

obj->rear %= obj->capacity + 1;//obj->rear=obj->rear%(obj->capacity+1);

return true;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)

{

return obj->rear == obj->front;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

//队列不为空

if (myCircularQueueIsEmpty(obj))

{

return false;

}

//队列不为空

obj->front++;

obj->front %= obj->capacity + 1;

return true;

}

int myCircularQueueFront(MyCircularQueue* obj) {

if (myCircularQueueIsEmpty(obj))

{

return -1;

}

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

}

int myCircularQueueRear(MyCircularQueue* obj) {

if (myCircularQueueIsEmpty(obj))

{

return -1;

}

int prev = obj->rear - 1;//这里创建变量是为了防止rear=0的时候再-1导致越界

if (obj->rear == 0)

{

prev = obj->capacity;//此时prev走的相当于是数组大小

}

return obj->arr[prev];

}

void myCircularQueueFree(MyCircularQueue* obj) {

free(obj->arr);

free(obj);

obj = NULL;//和销毁顺序表相似，顺序表底层是数组

}

/**

* 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);

*/

感谢还能看到这里的你，祝你天天开心，每天有所进步！！！

在这里插入图片描述

上一篇： Go最新【Go语言入门教程】Go语言简介，原理+实战讲解

下一篇：华为OD机试E卷 - 斗地主之顺子（Java & Python& JS & C++ & C ）

本文标签

数据结构之队列

声明

本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。