数据结构：队列

文章目录

• 一、队列的基本概念
• 二、队列的链式存储
• • • LinkQueue.h
    • LinkQueue.c
    • test.c
• 三、队列的顺序存储
• • 1.题目描述
  • 2.题目链接
  • 3.题解报告

一、队列的基本概念

• 队列(queue)是一端插入另一端删除的线性表。因此，对队列来说，插入的那一端叫队尾，插入叫入队；删除的那一端叫队头，删除叫出队。队列中的数据元素遵循先进先出(FIFO First In First Out)的特性
• 一种入队顺序只对应一种出队顺序

二、队列的链式存储

LinkQueue.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;

//采用单链表实现队列，链表结点的定义
typedef struct LinkNode {
QDataType data;
struct LinkNode* next;
}QNode;

typedef struct {
QNode* front;
QNode* rear;
int size;
}LinkQueue;

//初始化队列
void QueueInit(LinkQueue* q);

//销毁队列
void QueueDestroy(LinkQueue* q);

//检测队列是否为空，空返回真，否则返回假
bool QueueEmpty(LinkQueue* q);

//获取队列中有效元素个数
int QueueSize(LinkQueue* q);

//获取队头元素
QDataType QueueFront(LinkQueue* q);

//x入队
void EnQueue(LinkQueue* q, QDataType x);

//出队并返回队头数据
QDataType DeQueue(LinkQueue* q);

LinkQueue.c

#include "LinkQueue.h"

//初始化队列
void QueueInit(LinkQueue* q) {
assert(q);

q->front = q->rear = (QNode*)malloc(sizeof(QNode));
if (q->front == NULL) {
printf("QueueInit:开辟结点失败！！！\\n");
exit(–1);
}

q->size = 0;
}

//销毁队列
void QueueDestroy(LinkQueue* q) {
assert(q);

QNode* cur = q->front;
while (cur) {
QNode* next = cur->next;
free(cur);
cur = next;
}

q->front = q->rear = NULL;
q->size = 0;
}

//检测队列是否为空，空返回真，否则返回假
bool QueueEmpty(LinkQueue* q) {
assert(q);

return q->size == 0;
}

//获取队列中有效元素个数
int QueueSize(LinkQueue* q) {
assert(q);

return q->size;
}

//获取队头元素
QDataType QueueFront(LinkQueue* q) {
assert(q);
assert(!QueueEmpty(q));

return q->front->next->data;
}

//x入队
void EnQueue(LinkQueue* q, QDataType x) {
assert(q);

QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL) {
printf("EnQueue:申请结点失败！！！\\n");
exit(–1);
}
newNode->data = x;
newNode->next = NULL;

q->rear->next = newNode;
q->rear = newNode;
q->size++;
}

//出队并返回队头数据
QDataType DeQueue(LinkQueue* q) {
assert(q);
assert(!QueueEmpty(q));

QNode* delNode = q->front->next;
QDataType x = delNode->data;

q->front->next = delNode->next;
free(delNode);
delNode = NULL;
q->size—;

if (q->front->next == NULL) {
q->rear = q->front;
}

return x;
}

test.c

#include "LinkQueue.h"

int main() {
LinkQueue* q;
LinkQueue s;
q = &s;

QueueInit(q);
EnQueue(q, 1);
EnQueue(q, 2);
EnQueue(q, 3);
EnQueue(q, 4);
EnQueue(q, 5);

printf("队列数据个数：%d\\n", QueueSize(q));
printf("队头元素为：%d\\n", QueueFront(q));
printf("出队%d\\n", DeQueue(q));
printf("出队%d\\n", DeQueue(q));

EnQueue(q, 6);
EnQueue(q, 7);

printf("队列数据个数：%d\\n", QueueSize(q));
printf("出队%d\\n", DeQueue(q));
printf("出队%d\\n", DeQueue(q));
printf("出队%d\\n", DeQueue(q));
printf("出队%d\\n", DeQueue(q));
printf("出队%d\\n", DeQueue(q));
printf("队列数据个数：%d\\n", QueueSize(q));

QueueDestroy(q);

return 0;
}

三、队列的顺序存储

通过LeetCode的一道题来实现

1.题目描述

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你的实现应该支持如下操作：

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

2.题目链接

LeetCode_622.设计循环队列

3.题解报告

顺序存储结构实现循环队列

• 定义一个数组，长度为k，然后通过front和rear指针来指向队头和队尾，每入队一个元素，rear++，每出队一个元素，front++
• 当出队时，front++，数组前面的空间就会空闲，为了不浪费这些空间，用它们继续存储数据，当rear指向数组末尾，数组末尾已经存满数据时，如果要继续入队，入队元素要存入到数组开头，也就是rear指向数组开头；当front指向数组末尾时，再继续移动就指向数组开头。

如此实现了循环队列，具体操作如下：

• 判空和判满 判空：rear == front 判满：为了和判空区别开来，会先存数据，再rear++，如此rear始终指向的是一个空闲的空间，如果rear再往右移动一格与front重叠，可判定已满，即(rear+1)%N == front。由于rear要单独占一个空间，因此要实现长度为k的队列，需要的数组大小为N = k + 1

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1) % obj->N == obj->front;
}

• 结构体定义及初始化 本题定义结构体时并不知道队列长度，所以结构体中的数组需要动态创建和释放；因为MyCircularQueue* myCircularQueueCreate(int k)函数要返回的类型是MyCircularQueue*，所以队列结构体变量也需要动态创建和释放。如果不动态创建和释放，而是在栈上创建，函数结束时，创建的结构体也会随之销毁，函数返回的指针就是野指针了。

typedef struct {
int* arr;
int front;
int rear;
int N;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->arr = malloc(sizeof(int) * (k + 1));
obj->front = obj->rear = 0;
obj->N = k + 1;
return obj;
}

• 入队和出队 入队：先判断队列是否已满，然后再入队，因为rear指向的是一个空的空间，所以要先存放数据，然后再rear++，此时要对N取模，保证rear在超出数组长度时有返回到数组开头 出队：先判断队列是否为空，然后直接fornt++，同理，也要取模。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
return false;

obj->arr[obj->rear++] = value;
obj->rear %= obj->N;
return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
return false;

obj->front++;
obj->front %= obj->N;
return true;
}

• 取队头和队尾数据 取队头数据很简单，front就指向头位置 取队尾数据数据相对麻烦一些，rear-1才是队尾数据

int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
return –1;

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

int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
return –1;
else {
return obj->arr[(obj->rear – 1 + obj->N ) % obj->N];
}
}

• 结构体释放

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