【数据结构】栈和队列 + 经典算法题

目录

前言

一、栈

二、栈的实现

三、栈的循环遍历演示

四、栈的算法题

//

一、队列

二、队列的实现

三、使用演示

四、队列的算法题

总结

---

---

前言

        本文完整实现了栈和队列的数据结构，以及栈和队列的一些经典算法题，让我们更加清楚了解这两种数据结构特点，并熟悉运用。

---

一、栈

栈：⼀种特殊的线性表，其只允许在固定的一端进行插⼊和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（LastInFirstOut）的原则。

栈的特点：

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

     

                   

因为栈的特殊结构，所以对它的循环遍历也比较特殊。

栈 底层结构选型：

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。原因如下：

1. 首先数组搭配栈顶下标top，可以很方便找到栈顶元素。当然使用链表也可以，链表采用带头单向不循环链表，采用头插和头删也能实现栈的基本操作，而且时间复杂度都是O(1)
2. 不采用链表是因为栈的入栈和出栈操作频繁，链表需要不断开辟或者释放空间，而数组也采用动态开辟，使用2倍扩容能有效降低申请空间的频率。
3. 其次链表结构每个节点都需要有一个指针变量，指针占用4/8字节，可能比储存的数据都大，会占用大量空间，而数组开辟的空间仅用于存储数据。
4. 连续性空间比不连续空间访问速度快

---

二、栈的实现

1.栈的结构声明：

使用数组作为底层结构：

typedef int STDataType;
//定义栈结构
typedef struct Stack
{
    STDataType* arr;
    int capacity;//栈的空间大小
    int top;//栈顶
}ST;

与顺序表基本相同，只有第三个成员变量含义不同。本质都是表示有效元素个数。

---

2.Stack.h头文件

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

typedef int STDataType;
//定义栈结构
typedef struct Stack
{
STDataType* arr;
int capacity;//栈的空间大小
int top;//栈顶
}ST;

//初始化
void STInit(ST* ps);

//销毁
void STDesTroy(ST* ps);

//入栈
void StackPush(ST* ps, STDataType x);

//判空
bool StackEmpty(ST* ps);

//出栈
void StackPop(ST* ps);

//取栈顶元素
STDataType StackTop(ST* ps);

//获取栈中有效元素个数
int STSize(ST* ps);

栈的基本操作（函数）有：

1. 栈的初始化
2. 栈的销毁
3. 入栈（增加元素）
4. 出栈（删除元素）
5. 判空（判断栈是否为空栈）
6. 取栈顶元素（但不用出栈）
7. 获取栈中的元素个数

---

3.Stack.c 定义文件

注意看注释，与顺序表很像

#include "Stack.h"

//初始化
void STInit(ST* ps)
{
assert(ps);

//全初始化为空
ps->arr = NULL;
ps->capacity = ps->top = 0;
}

//销毁
void STDesTroy(ST* ps)
{
assert(ps);

//判断arr
if (ps->arr)
{
free(ps->arr);
}

//销毁后置空
ps->arr = NULL;
ps->capacity = ps->top = 0;
}

//入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);

//判断空间是否充足
if (ps->top == ps->capacity)
{
//使用三目操作符根据容量是否为0来选择如何给定新容量大小
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//1.如果容量为0，赋值4  2.如果容量不为零，进行二倍扩容

//申请新空间
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}

//修改参数
ps->arr = tmp;
ps->capacity = newCapacity;
}

//空间充足
ps->arr[ps->top++] = x;
}

//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}

//出栈
void StackPop(ST* ps)
{
assert(ps);
//判断栈容量是否为空
assert(!StackEmpty(ps));
//直接让栈顶下移一位即可
--ps->top;
}

//取栈顶元素
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));//判空
//直接返回栈顶元素
return ps->arr[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}

函数解析：

1. STInit函数：栈的初始化，需要传入栈的地址，将其 arr 初始化为空指针，capacity、top初始化为0。（assert是断言，一般的操作栈不能为空）
2. STDesTroy函数：栈的销毁，传入栈的地址，栈的 arr 空间是由 realloc 申请的，因此需要free 释放，释放时应先判断 arr 是否申请了空间。释放后将栈的成员置空。
3. StackPush函数：入栈，传入栈的地址和需要添加的元素。入栈之前需要先判断栈空间是否充足，通过栈结构的成员变量 capacity容量 和 top栈顶 是否相等来判断栈是否满了。因为我们初始化时并没有开辟空间，所以第一次入栈这里一定是需要开辟空间的，因此我们使用3目操作符对新容量大小进行赋值，如果容量为0那么就是第一次开辟空间，赋值4。如果不为0那么就进行2倍扩容。随后使用 realloc 开辟空间，判断成功开辟后，将新空间地址赋值给栈成员 arr，将新容量大小赋值给栈成员 capacity。
4. StackEmpty函数：判空，传入栈的地址，如果栈顶下标都为0，那么栈就为空。
5. StackPop函数：出栈，传入栈的地址，出栈需要判断栈是否为空，用写好的上一个函数判断即可，出栈操作只需要将栈顶下标减1，因为每次入栈也是在栈顶，下次入栈就会覆盖旧数据
6. StackTop函数：取栈顶元素，传入栈的地址，先判断栈是否为空，然后直接返回栈顶元素即可。注意top的下标是下一个入栈的位置，因此栈顶元素需要-1。
7. STSize函数：获取栈中有效元素个数，直接返回栈顶下标即可。

---

三、栈的循环遍历演示

#include "Stack.h"

void StackTest1()
{
//创建一个栈
ST st;

//初始化
STInit(&st);

//压入4个数据
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);

//循环遍历
while (!StackEmpty(&st))//栈顶元素为空才停止
{
//取栈顶元素并打印
printf("%d ", StackTop(&st));
//出栈
StackPop(&st);
}

//销毁
STDesTroy(&st);
}

int main()
{
StackTest1();

return 0;
}

运行结果：

解析：

1. 为什么只能这样遍历栈？
2. 答：因为这样才符合栈的特性，栈是不支持随机访问的，它只能从栈顶开始访问。如果想访问下一个数据，那么上一个数据必须出栈才行。

---

四、栈的算法题

题目出处：

20. 有效的括号 - 力扣（LeetCode）

题目解析：

1. 首先题目意思是判断一组括号是否符合语法规定，比如：{ [（）] }，当然题目中并没有规定括号优先级问题，所以小括号也能包住大括号
2. 我们发现如果一开始是左括号，一旦遇到右括号，那么这个右括号如果是正确的，那么它一定和最近的左括号匹配
3. 如何使用栈的特性来解决，栈是“先进后出”，如果我们让左括号先进栈，遇到右括号时，先取栈顶元素与右括号匹配，如果匹配，我们让左括号出栈。如此循环，左括号进栈，右括号判断，一旦匹配失败就说明括号字符串不符合规定。
4. 如图：
5. 

题解：

bool isValid(char* s)
{
//创建一个栈
ST st;
STInit(&st);

//新建一个指针
char* ps = s;

//循环遍历
while (*ps != '\0')
{
if (*ps == '(' || *ps == '[' || *ps == '{')
{
//入栈
StackPush(&st, *ps);
}
else
{
//假如栈中无数据，一开始就是右括号
if (StackEmpty(&st))
{
//直接销毁栈，并返回否
STDesTroy(&st);
return false;
}

//如果栈中有数据,先取栈顶元素，然后与右括号进行判断
char ch = StackTop(&st);
if (*ps == ')' && ch == '('
|| *ps == ']' && ch == '['
|| *ps == '}' && ch == '{')
{
//匹配正确,出栈
StackPop(&st);
}
else
{
//匹配失败
STDesTroy(&st);
return false;
}
}
++ps;
}

//如果栈中还有数据，证明左括号多了
if (!StackEmpty(&st))
{
STDesTroy(&st);
return false;
}

//一切正常
STDesTroy(&st);
return true;
}

注意：答题时需要将栈的完整代码也加上去

---

///

---

一、队列

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

特性：“先进先出” 或者 “后进后出”

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

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

与栈的异同：

1. 不同：栈是一端进行进出数据操作，队列是两端，一端进数据，一端出数据
2. 相同：都是在端点操作

队列 底层结构选型：

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

---

二、队列的实现

1.队列的结构声明

typedef int QDatatype;

//定义队列节点的类型结构
typedef struct QueueNode
{
QDatatype data;
struct QueueNode* next;
}QueueNode;

//定义队列
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
int size; //保存队列有效元素个数
}Queue;

队列的结构比较特殊：

1. 因为队列采用单链表作为底层结构，因此需要定义队列的存储数据类型，也就是定义每个数据的节点类型。
2. 所以第一个结构体只是定义队列的元素类型，第二个结构体才是队列，队列仅需要两个指针，一个指针指向对头，一个指针指向队尾。因为这两指针类型都是元素节点的类型，所以要先定义元素类型
3. 队列中的 size 成员是储存队列有效元素个数，因为如果想知道队列的元素个数，循环遍历队列效率低，因此队列多加一个成员变量储存元素个数。

---

2.Queue.h头文件

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

typedef int QDatatype;

//定义队列节点的类型结构
typedef struct QueueNode
{
QDatatype 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);

//判空
bool QueueEmpty(Queue* pq);

//出队列
void QueuePop(Queue* pq);

//取队头数据
QDatatype QueueFront(Queue* pq);

//取队尾数据
QDatatype QueueBack(Queue* pq);

//队列有效元素个数
int QueueSize(Queue* pq);

//销毁
void QueueDesTroy(Queue* pq);

队列的常用操作：

1. 队列的初始化
2. 入队（插入元素）
3. 出队（删除元素）
4. 判空（判断队列是否为空）
5. 取对头元素
6. 取队尾元素
7. 获取队列有效元素个数
8. 队列的销毁

---

3.Queue.c定义文件

#include "Queue.h"

//初始化
void QueueInit(Queue* pq)
{
assert(pq);
//初始化为空指针和0
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;

if (pq->phead == NULL)
{
//如果队列为空
pq->phead = pq->ptail = newnode;
}
else
{
//栈不为空
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
//元素个数加一
pq->size++;
}

//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);

return pq->phead == NULL && 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);

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;
}

函数解析：

1. QueueInit函数：队列的初始化，传入队列的地址，将其头指针和尾指针都初始化为NULL，size 初始化为0。
2. QueuePush函数：入队，传入队列的地址和需要插入的数据，首先申请新节点，将需要出入的数据赋值给新节点，并将其 next 指针初始化为空。然后从队尾插入队列，在插入队列之前需要先判断队列是否为空（可以将判空函数提前），因为如果队列为空，那么它的头尾指针都应是新节点，如果队列不为空，那么从队尾插入，先将队尾指针的 next 指针指向新节点，然后更新队尾指针为新节点，最后不要忘了让 size++。
3. QueueEmpty函数：判空，直接返回头指针与空指针的判断结果，判不判断尾节点都行
4. QueuePop函数：出队，出队列需要先判空，另外还需要注意，如果队列只有一个元素，那么尾指针和头指针都需要变为空指针。如果队列元素多于一个元素，那么只改变头指针即可，先保存头指针的 next 节点，然后释放头指针节点，再跟新头指针，最后记得让 size--。
5. QueueFront函数：取对头元素，有头指针存在，判空后，直接返回头指针指向的节点数据
6. QueueBack函数：取队尾元素，同理，返回尾指针指向的节点数据即可
7. QueueSize函数：获取队列有效元素个数，返回队列结构成员 size 即可
8. QueueDesTroy函数：队列的销毁，判空可不写，先保存头指针，然后循环遍历释放各节点，如果不判空这里不受影响，因为空队列那么头指针也为空，就不会进入循环，最后将指针和 size 都置空或置0。

---

三、使用演示

#include "Queue.h"

void QueueTest1()
{
//创建队列
Queue q;

//初始化
QueueInit(&q);

//入队
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);

//循环出队列并打印
while (!QueueEmpty(&q))
{
//取队头元素
printf("%d ", QueueFront(&q));

//出队列
QueuePop(&q);
}

//销毁
QueueDesTroy(&q);
}

int main()
{
QueueTest1();

return 0;
}

运行结果：

注意：将销毁队列中的判空注释掉，不然会报错

---

四、队列的算法题

1.双队列实现栈

题目出处：225. 用队列实现栈 - 力扣（LeetCode）

题目解析：

1. 题目是让我们使用两个队列来实现栈，满足栈的“先进后出”，实现6种基本操作
2. 
3. 如何实现，队列的特性是“先进先出”，一端进数据，一端出数据，那么假如我们将数据 1、2、3 插入队列1，我们需要出栈，那么只能出数据3，而队列只能在对头出数据，因此我们先将数据 1、2 出队列并插入队列2，此时队列2中为数据 1、2，队列1中数据为 3。此时我们再将队列1中的3出队列，此时就完成了出栈的操作。
4. 所以我们使用将数据在两个队列中来回导的方法，实现栈的操作方法。
5. 那么这里面的关键就是，每一次操作后只有一个队列中有数据，另一个队列为空。
6. 入栈操作：我们往不为空的队列中插入数据。
7. 出栈操作：找到不为空的队列，把不为空队列中的 size-1 个数据导到空队列中，最后将不为空队列中的最后一个数据出队列
8. 注意取栈顶元素操作不能模仿出栈操作，因为取栈顶元素不会出栈，来回导会造成两个队列都不为空的情况

题解：

注意：在答题时需将队列的完整代码写上去

typedef struct
{
    //栈结构使用两个队列
Queue q1;
Queue q2;
} MyStack;


//初始化
MyStack* myStackCreate()
{
    动态开辟栈的空间
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));

    //两个队列使用队列初始化函数完成初始化
QueueInit(&pst->q1);
QueueInit(&pst->q2);

return pst;
}

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

//出栈
int myStackPop(MyStack* obj)
{
//首先找不为空的队列
Queue* empQ = &obj->q1;
Queue* noneQ = &obj->q2;
if (!QueueEmpty(&obj->q1))
{
empQ = &obj->q2;
noneQ = &obj->q1;
}

//将不为空的队列中的size-1个数据导入到空队列
while (QueueSize(noneQ) > 1)
{
int Front = QueueFront(noneQ);
QueuePush(empQ, Front);
QueuePop(noneQ);
}

//非空队列剩下的一个数据就是需出栈的数据
int pop = QueueFront(noneQ);
QueuePop(noneQ);
return pop;
}

//取栈顶元素
int myStackTop(MyStack* obj)
{
    //找到不为空的队列，返回队尾元素即可
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}

//判空
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

//销毁
void myStackFree(MyStack* obj)
{
QueueDesTroy(&obj->q1);
QueueDesTroy(&obj->q2);
free(obj);
obj = NULL;
}

---

2.双栈实现队列

题目出处：232. 用栈实现队列 - 力扣（LeetCode）

题目解析：

1. 与上一题相反，这题需要使用两个栈来实现队列结构
2. 
3. 有了上一题的经验，这一题同样也是使用来回导数据的方式。
4. 如我们现在需要入队数据 1、2、3，我们将其插入栈1中，栈是“先进后出”，当我们需要出队时，我们直接将栈1的数据出栈并插入栈2，此时栈2中的数据为 3、2、1，而栈顶元素 1 就是我们需要出队的数据，也就是对头元素。接下来如果我们还需要出队，那么直接让栈2元素出栈即可，如果需要入队元素，直接插入到栈1
5. 
6. 因此，与上一题不同的是，这次我们不用保证有一个容器为空，我们让栈1专门存放入队元素，让栈2专门用来出对。这样也就符合了队列的“先进先出”特性

题解：

typedef struct
{
ST pushST;//用于入队
ST popST;//用于出队
} MyQueue;

//初始化
MyQueue* myQueueCreate()
{
MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));

    //调用栈自己的初始化函数
STInit(&pq->popST);
STInit(&pq->pushST);

return pq;
}

//入队
void myQueuePush(MyQueue* obj, int x)
{
    //直接往push栈中插入元素
StackPush(&obj->pushST, x);
}

//出队
int myQueuePop(MyQueue* obj)
{
    //先判断pop栈是否为空
if (StackEmpty(&obj->popST))
{
//为空，导数据
while (!StackEmpty(&obj->pushST))
{
            //将push栈中元素全导入pop栈
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}

    //先储存出队元素，出栈后返回
int pop = StackTop(&obj->popST);
StackPop(&obj->popST);
return pop;
}

//取对头元素
int myQueuePeek(MyQueue* obj)
{
    //前面与出队操作一致
if (StackEmpty(&obj->popST))
{
//导数据
while (!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
    
    //最后不用出栈，直接返回栈顶元素
return StackTop(&obj->popST);
}

//判空
bool myQueueEmpty(MyQueue* obj)
{
return StackEmpty(&obj->popST) && StackEmpty(&obj->pushST);
}

//销毁
void myQueueFree(MyQueue* obj)
{
STDesTroy(&obj->popST);
STDesTroy(&obj->pushST);
free(obj);
obj = NULL;
}

---

3.设计循环队列

题目出处：622. 设计循环队列 - 力扣（LeetCode）

题目解析·：

1. 题目是让我们设计一个循环队列，那么什么是循环队列，根据题目我们了解循环队列依旧遵循“先进先出”特性，结构上是队列的尾指针与头指针相连，并且重要的是循环队列的空间的固定的。
2. 如何设计呢，既然循环队列空间是一定的，那我们可以采取数组作为底层结构，当然链表也行，不过数组更为方便，能一次性开辟完空间。除了底层结构，我们知道队列是有两个指针指向队头和对尾的，那么我们就可以设置两个下标 front 和 rear 来分别指向循环队列的对头和队尾。
3. 循环队列还有插入和删除操作，执行这两个操作时我们需要判断循环队列是否满了或者空了，那么我们怎么判断呢，假如我们将 front 和 rear 都初始化为0，那么当它俩相等时，我们可以确定队列为空，可是队列满了它们俩也相等。怎么解决这个问题呢
4. 直接说结论吧，我们选择多开辟一个空间，也就是数组的最后一位，最后一个空间不存储数据，当 rear 走到这个位置时，那么此时循环队列就满了，而 front 和 rear 下标也就不相同。这样就可以通过下标来区分循环队列是空是满。满了的公式由 rear+1 等于 front 的下标推导，因为循环队列中下标走到头了后需要回到对头，所以使用取余来更新计算下标，推出以下公式
5. 
6. 能够判断队列状态后，我们就可以进行入队和出队操作了。
7. 入队操作：首先根据公式判断队列是否满了，满了直接返回 false，没满，在 rear 处插入数据，然后 rear++ 往后走一位，这时候就需要注意了，rear 不能越界，走到数组末尾了，如果队列还有空间，需要更新 rear 的下标，所以 rear = rear % (capacit+1)，保证下标循环走动
8. 出队操作：需要先判空，判空后如果队列不为空，直接让 front++，使原数据无效即可，这里front 的下标同样不能越界，需要通过取余来保证其在队列中循环走动，front %= capacity+1
9. 获取对头和对尾元素中，对头元素获取简单，判空后直接返回 front 下标位置处的数据即可，而队尾就有所不同，判空后，不能直接返回 rear 下标处的数据，因为 rear 下标指向的是下一个元素插入的位置，取队尾元素时需减1，因此有一种特殊情况：
10. 
11. 即当 rear 刚好处于下标为0处的位置，这时候返回队尾元素 3 时，不能直接返回 rear-1 处下标的元素，而是另外创建一个 prev 指针，让其指向 rear-1 处的下标，并判断如果 rear 刚好处于下标为0的位置时，让 prev 等于 capacity ，也就是下标为5的位置。

题解：

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;

return true;
}

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

//删除数据
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;
if (obj->rear == 0)
{
prev = obj->capacity;
}
return obj->arr[prev];
}

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

扩展：计算循环队列有效元素个数

公式：循环队列有效元素个数 = ( rear - front + capacity +1 ) % ( capacity + 1 )

---

总结

        以上就是本文的全部内容，感谢支持！

原文地址：https://blog.csdn.net/x_p96484685433/article/details/142683346

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！