队列的实现及循环队列

一、队列的概念及结构

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

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

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

二、队列的实现（单链表实现）

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 val;
}QNode;
//队列的结构
//多个参数可以封装成结构体，方便传参，否则下面传二级指针
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//队尾插入
void QueuePush(Queue* pq, QDataType x);
//队头删除
void QueuePop(Queue* pq);
//获取队头数据
QDataType QueueFront(Queue* pq);
//获取队尾数据
QDataType QueueBack(Queue* pq);
//获取队列中有效元素个数
void QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

Queue.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->front = NULL;pq->rear = NULL;pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->front;while (cur){Queue* next = cur->next;free(cur);cur = next;}pq->front = pq->rear = NULL;pq->size = 0;
}
//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail!");return;}newnode->next = NULL;newnode->val = x;if (pq->rear == NULL){pq->front = pq->rear = newnode;}else{pq->rear->next = newnode;pq->rear = newnode;}pq->size++;
}
//队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size > 0);if (pq->front == pq->rear){free(pq->front);pq->front = pq->rear = NULL;}else{QNode* next = pq->front->next;free(pq->front);pq->front = next;}pq->size--;
}
//获取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->front);return pq->front->val;
}
//获取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->rear);return pq->rear->val;
}
//获取队列中有效元素个数
void QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->size == 0){return 1;}else{return 0;}
}

Test文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePop(&q);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");return 0;
}

三、设计循环队列

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

方法：额外多开一个空间

代码：

typedef struct {int* a;int head;int tail;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多开一个解决假溢出问题obj->a = (int*)malloc(sizeof(int)*(k+1));obj->head = 0;obj->tail = 0;obj-> k = k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1) % (obj->k+1) == obj->head;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->tail] = value;obj->tail++;obj->tail %= (obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;++obj->head;obj->head %= (obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->tail + obj->k) % (obj->k+1)]; 
}void myCircularQueueFree(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);
*/