这道题十分考验我们对队列的理解。
队列的介绍
队列是一种只允许在一段进行插入,在另一端进行删除的数据操作的特殊线性结构,,因此决定了他具有先入先出的特点,其中进行插入操作的一段叫做队尾,出队列的一端叫做队头。
队列的实现
队列可以使用链表或者数组进行实现,对于这两种实现方法,使用链表实现效果更好一点,两个指针中front为链表的头,即队列的队头,出数据的话只需要找到front的下一个假设为pre,将front销毁,front置为pre即可,如果是用数组的结构的话,出队列在数组头上出数据,效率会很低。
链表实现队列代码如下
Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;//头
QNode* tail;//尾
int size;//大小
}Que;
void QueueInit(Que* pq);//初始化
void QueuePush(Que* pq,QDataType);//入队列
void QueueDestroy(Que* pq);//销毁
void QueuePop(Que* pq);//出队列
QDataType QueueFront(Que* pq);//队头的数据
QDataType QueueBack(Que* pq);//队尾的数据
bool QueueEmpty(Que* pq);//检查是否为空
int QueueSize(Que* pq);//队列元素
Queue.c
#define _CRT_SECURE_NO_WARNINGS
#include "Queueh.h"
void QueueInit(Que* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueuePush(Que* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
newnode->next = NULL;
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
if (pq->tail == NULL)//这里要先进行判断
{
pq->head = pq->tail = newnode;//如果队列里没有一个元素
//那么head和tail都为空,将newnode设置为队头,当然也是队尾,毕竟只有一个元素。
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));//判空,避免引起不必要的错误。
if (pq->head->next != NULL)
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
else
{
free(pq->head);
pq->head = pq->tail = NULL;
}
pq->size--;
}
QDataType QueueFront(Que* pq)
{
assert(pq);
//判断是否为空
assert(!QueueEmpty(pq));
return pq->head->data;//队头位置
}
QDataType QueueBack(Que* pq)
{
assert(pq);
//判断是否为空
assert(!QueueEmpty(pq));
return pq->tail->data;//队尾位置
}
bool QueueEmpty(Que* pq)//判断是否为空,为空则返回true
{
if (pq->head == NULL)
{
return true;
}
else
{
return false;
}
}
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}
进入正题
链接:设计循环队列
前边的队列如果空间不够就会扩容,但是这里的循环队列大小是固定的,只可以保存k个元素,当然还是遵循先入先出的规则。
例如下边的环形队列,在pop掉队头数据后,这块空间不会被销毁的,可以继续存储值覆盖原来的值,假设k等于5,当入6个元素后,这个循环队列就满了,当出队列时,此时这个队列的首位置就可以继续存储数据。
数组的方法
结构体声明如下
typedef struct {
int* a;
int front;
int rear;//尾
int k;
} MyCircularQueue;
初始化函数如下
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//多开一个方便区分空和满
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->k=k;
obj->front=obj->rear=0;
return obj;
}
数组也面临一个同样的问题,如何判断是满还是空?
可以多开一块空间。k==5,开6块空间,最后一块空间浪费不用。
如果front等于tail就为空,在这里设置tail的值为0~5(要注意下标和位置有减一的关系),如果tail的下一个位置为front时,表示队列已满。
obj->tail%=(obj->k+1);//obj为循环队列变量
控制tail的值的变化范围,当tail等于6时置tail为0。
当然,在出队列过程中,front是会不断变化的。
我们看front变化的情况
pop一个数据后,向后移一位
判断是否队列已满的条件判断句如下
(obj->tail+1)%(obj->k+1 )==obj->front
前边已经说过了,tail的变化范围为0~5,此时tail被置为0,但front为1,不相等,就表示还有空余的位置,队列没有满,所以上边的判断语句在任何场景都是正常使用的。
判断是否已满函数如下(题目中tail被rear替换)
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear+1)%(obj->k+1 )==obj->front;
}
返回类型为布尔值,如果相等就返回true,不相等就返回false。
判断是否为空很简单,直接比较rear和front的值是否相等即可。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->rear;
}
置空函数
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
获取队头元素
很简单,返回front位置的元素即可
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
获取队尾元素
这里就要思考一下了
如果rear不在数组第一个空间上,直接返回数组rear-1处的值即可,当rear位于数组首元素,就要返回数组第k个元素。
代码如下
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
if(obj->rear==0)
{
return obj->a[obj->k];
}
else{
return obj->a[obj->rear-1];
}
//下边是综合写法
//return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}
}
出队列deQueue()
出队列只需要将front++即可,就算之前的数据不销毁,下次入队列操作也会覆盖他的数据。
代码如下
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
++obj->front;
obj->front%=(obj->k+1);
return true;
}
注意是要有返回值的,如果队列为空,就没有出数据,返回false,出数据成功就返回true。
入队列
代码如下:
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->rear]=value;
obj->rear++;
obj->rear%=(obj->k+1);
return true;
}
首先判断循环队列是否已满,如果已满就返回false,如果没有满就将rear位置的值改为value,然后rear++,判断是否超出范围,如果超出就置为0。最后入队列成功返回true。
到了这里这道题目就顺利解决了,如果使用双向链表来做这道题的话当然也可以,但是会稍微麻烦一点,有兴趣可以尝试尝试。
今天的内容就到这里啦,如果有错误欢迎各位指正哦!
综合上述代码后即可通过本题。
链表实现
链表实现就较为简单了,思路和前边数组实现的思路很像。
首先声明结构体
typedef struct listNode
{
struct listNode* next;
int val;
}LS;
typedef struct {
LS* head;
LS* tail;
int size;
int k;
} MyCircularQueue;
节点的结构体保存下一个结构体的指针,并且存储值val。
循环链表结构体有头结点,尾节点,size是队列中元素的个数,k为设定的循环队列的容量。
入队列时,获取一个初始化后新节点,并把之前的尾结点与这个节点连接起来。
获取新节点的函数如下
LS* buylistNode(int x)
{
LS*listnode =(LS*)malloc(sizeof(LS));
listnode ->next=NULL;
listnode ->val=x;
return listnode;
}
函数返回新造的节点。以供入队列函数使用。
至于判空判满函数我想就不用过多介绍,重要的是入队列和出队列。
出队列只需要头结点向后移,然后size–就好。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(obj->head==NULL)
{
return false;
}
else
{
obj->head=obj->head->next;
obj->size--;
return true;
}
}
入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))//如果已满,就返回false
{
return false;
}
LS*node=buylistNode(value);
if(obj->head==NULL)//第一次插入
{
obj->head=node;
obj->tail=node;
}
else
{
LS*tran=obj->tail;
obj->tail=node;
tran->next=obj->tail;
}
obj->size++;//注意size++
return true;
}
全部代码如下文章来源:https://www.toymoban.com/news/detail-744533.html
typedef struct listNode
{
struct listNode* next;
int val;
}LS;
typedef struct {
LS* head;
LS* tail;
int size;
int k;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->size==0;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->size==obj->k;
}
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->head=NULL;
obj->tail=NULL;
obj->size=0;
obj->k=k;
return obj;
}
LS* buylistNode(int x)
{
LS*listnode =(LS*)malloc(sizeof(LS));
listnode ->next=NULL;
listnode ->val=x;
return listnode;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
LS*node=buylistNode(value);
if(obj->head==NULL)
{
obj->head=node;
obj->tail=node;
}
else
{
LS*tran=obj->tail;
obj->tail=node;
tran->next=obj->tail;
}
obj->size++;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(obj->head==NULL)
{
return false;
}
else
{
obj->head=obj->head->next;
obj->size--;
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->head->val;
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->tail->val;
}
void myCircularQueueFree(MyCircularQueue* obj) {
while(obj->head!=NULL)
{
LS*a=obj->head->next;
free(obj->head);
obj->head=a;
}
free(obj);
}
这篇文章到这里就结束啦,如果有问题欢迎大家指出。文章来源地址https://www.toymoban.com/news/detail-744533.html
到了这里,关于Leetcode循环队列(数组实现及链表实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!