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

2024-10-10 07:04:45

目录

前言

一、栈

二、栈的实现

三、栈的循环遍历演示

四、栈的算法题

//

一、队列

二、队列的实现

三、使用演示

四、队列的算法题

总结

前言

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

一、栈

栈：⼀种特殊的线性表，其只允许在固定的一端进行插⼊和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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. 如图：

题解：

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种基本操作
  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. 与上一题相反，这题需要使用两个栈来实现队列结构
  3. 有了上一题的经验，这一题同样也是使用来回导数据的方式。
  4. 如我们现在需要入队数据 1、2、3，我们将其插入栈1中，栈是“先进后出”，当我们需要出队时，我们直接将栈1的数据出栈并插入栈2，此时栈2中的数据为 3、2、1，而栈顶元素 1 就是我们需要出队的数据，也就是对头元素。接下来如果我们还需要出队，那么直接让栈2元素出栈即可，如果需要入队元素，直接插入到栈1
  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 的下标推导，因为循环队列中下标走到头了后需要回到对头，所以使用取余来更新计算下标，推出以下公式
  6. 能够判断队列状态后，我们就可以进行入队和出队操作了。
  7. 入队操作：首先根据公式判断队列是否满了，满了直接返回 false，没满，在 rear 处插入数据，然后 rear++ 往后走一位，这时候就需要注意了，rear 不能越界，走到数组末尾了，如果队列还有空间，需要更新 rear 的下标，所以 rear = rear % (capacit+1)，保证下标循环走动
  8. 出队操作：需要先判空，判空后如果队列不为空，直接让 front++，使原数据无效即可，这里front 的下标同样不能越界，需要通过取余来保证其在队列中循环走动，front %= capacity+1
  9. 获取对头和对尾元素中，对头元素获取简单，判空后直接返回 front 下标位置处的数据即可，而队尾就有所不同，判空后，不能直接返回 rear 下标处的数据，因为 rear 下标指向的是下一个元素插入的位置，取队尾元素时需减1，因此有一种特殊情况：
  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;
}

总结

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

上一篇：Docsify搭建个人博客-安装到本地


下一篇：GC9118S替代TMI8118的优势分析，可应用在牙刷，电子锁，医疗设备等产品中