【初阶数据结构与算法】第六篇：栈和队列（各个功能实现+练习题包含多种方法）
⭐️本篇博客我要给大家分享一下算法中的双链表。希望对大家有所帮助。
⭐️ 博主码云gitee链接：码云主页
目录
前言
🌏一、栈
🍯1.栈的概念和结构
🍯2.栈的实现
🍍栈定义
🍍初始化
🍍销毁
🍍入栈
🍍出栈
🍍判断栈是或否为空
🍍栈存放数据数量
🍍当前栈顶的数据
🌏二、队列
🍯1.队列
🍯2.队列的特点
🍯3.队列的实现
🍍初始化
🍍判空
🍍入队
🍍出队
🍍获取队头元素和队尾元素
🍍计算队列元素数量
🍍销毁
🌏三、练习题
🍯1.有效的括号（传送门）
🍯2.用队列实现栈（传送门）
🍯3.用栈实现队列（传送门）
🍯4.（数组实现和链表实现）设计循环队列（传送门）
🍍数组实现
🍍链表实现
总结
前言
🌏一、栈
🍯1.栈的概念和结构
🍤栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
🍤压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
🍤出栈：栈的删除操作叫做出栈。出数据也在栈顶。
🍯2.栈的实现
🍍栈定义
typedef int STDataType;typedef struct Stack { STDataType* arr; //接收动态开辟的数组地址 int top; //栈的顶部 int capcity; //栈的容量}Stack;🍍初始化
🍤将指针置为NULL， 将空间都置为0
void StackInit(Stack* ps) { assert(ps); //传进来的地址一定不能为空 ps->arr = NULL; ps->capcity = ps->top = 0;}🍍销毁
🍤释放空间，将将空间置0
void StackDestory(Stack* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capcity = ps->top = 0;}🍍入栈
🍤当我们使一个元素入栈的之前，我们往往需要判断一下栈是否为满栈，防止发生上溢的情况。
🍤注意扩容操作要检查
void StackPush(Stack* ps, STDataType x) { assert(ps); //判断是否满了 if (ps->top == ps->capcity) { //capcity是空，则给四个整形，否则将原来空间扩大为原来的两倍 ps->capcity = ps->capcity == 0 ? 4 : sizeof(Stack) * 2; //扩容 ps->arr = (Stack*)realloc(ps->arr, sizeof(Stack)*ps->capcity); if (ps->arr == NULL) { printf("fail realloc: %s\n",strerror(errno)); exit(-1); } } ps->arr[ps->top++] = x;}🍍出栈
🍤注意非法访问
void StackPop(Stack* ps) { assert(ps); assert(ps->top > 0); ps->top--;}🍍判断栈是或否为空
🍤判断防溢出
bool StackEmpty(Stack* ps) { assert(ps); return ps->arr == NULL;}🍍栈存放数据数量
🍤直接返回ps->top
int StackSize(Stack* ps) { assert(ps); return ps->top;}🍍当前栈顶的数据
🍤直接返回ps->top-1
STDataType StackTop(Stack* ps) { assert(ps); //当没有数据的时候，不会指向空 aasert(ps->top > 0); return ps->arr[ps->top - 1];}🌏二、队列
🍯1.队列
🍤只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性
🍯2.队列的特点
- 队列是一种操作受限的线性表
- 队头(首)：允许删除的一端
- 队尾：允许插入的一端
- 空队列：没有元素的队列
- 删除操作叫做
出队,插入操作叫做入队
🍯3.队列的实现
🍍初始化
🍤直接初始化为NULL就好
void QueueInit(Queue* pq) { assert(pq); //先将两个结构体指针为空 pq->head = pq->tail = NULL;}🍍判空
🍤head和tail只要判断一个就可以了
bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL;}🍍入队
🍤链式结构不用检查空间是否满了，先创建一个节点，如果队列没有节点，就将节点赋值给head和tail，如果队列有节点，则将节点链接到tail后面
void QueuePush(Queue* pq, typedefData x) { assert(pq); //建立新的节点 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { printf("malloc fail: %s",strerror(errno)); exit(-1); } newnode->Data = x; newnode->next = NULL; //判断如果队尾为空，说明没有元素 if (pq->tail == NULL) { pq->head = pq->tail = newnode; }else { pq->tail->next = newnode; pq->tail = newnode; }}🍍出队
🍤出队前要判断队列是否还有元素，没有元素则直接将head链接到下一个节点同时释放上一个节点即可，但是如果队列里只有一个节点了，head移动到下一个节点时同时也要将tail置空
void QueuePop(Queue* pq) { assert(pq); //当首尾都为NULL时，说明队列没有元素，则不用删除 assert(pq->head != NULL && pq->tail != NULL); //当队列只有一个元素 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } //两个或两个以上元素 else { QueueNode* next = pq->head->next; free(pq->head); pq->head = next; }}🍍获取队头元素和队尾元素
🍤获取事前只需要判断队列里面是否还有元素即可
//获取队头元素typedefData QueueFront(Queue* pq) { assert(pq); //当head为空时，取head的值就没有意义了 assert(pq->head); return pq->head->Data;}//获取队尾元素typedefData QueueBack(Queue* pq) { assert(pq); //当head为空时，取tail的值就没有意义了 assert(pq->tail); return pq->tail->Data;}🍍计算队列元素数量
🍤依次遍历计数即可
int QueueSize(Queue* pq) { assert(pq); size_t size = 0; QueueNode* cur = pq->head; while (cur != NULL) { cur = cur->next; size++; } return size;}🍍销毁
🍤用cur来遍历逐个置空，完事后记得将head和tail也要置空
void QueueDestory(Queue* pq) { assert(pq); //把头节点给cur QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } //将所有节点释放完之后，再将两个队头和队尾指针释放 pq->head = pq->tail = NULL;}🌏三、练习题
🍯1.有效的括号（传送门）
🍤给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
🔑思路：
首先我们要知道，栈是适合这一类匹配问题的。
我们分析之后有三种情况，左方向括号多余，右方向括号多余，没有括号多余但是括号不匹配。所以我们遇到左括号就存放到栈中，遇到右括号就取出括号进行匹配，如果遍历完所有之后栈还为空则表示完全匹配。
/* 由于栈结构的特殊性。非常适合做匹配类问题*///上次博客中栈的定义typedef char STDatatype;typedef struct Stack{ STDatatype* a; int top; // 栈顶 int capacity;}ST; void StackInit(ST* ps);void StackDestroy(ST* ps);void StackPush(ST* ps, STDatatype x);void StackPop(ST* ps);bool StackEmpty(ST* ps);int StackSize(ST* ps);STDatatype StackTop(ST* ps); void StackInit(ST* ps){ assert(ps); ps->a = NULL; ps->top = 0; // -1 ps->capacity = 0;} void StackDestroy(ST* ps){ assert(ps); if (ps->a) { free(ps->a); } ps->a = NULL; ps->top = 0; ps->capacity = 0;} void StackPush(ST* ps, STDatatype x){ assert(ps); // 检查空间够不够，不够就增容 if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDatatype* tmp = realloc(ps->a, sizeof(STDatatype)*newcapacity); if (tmp == NULL) { printf("rellaoc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++;} void StackPop(ST* ps){ assert(ps); assert(!StackEmpty(ps)); --ps->top;} bool StackEmpty(ST* ps){ assert(ps); return ps->top == 0;} int StackSize(ST* ps){ assert(ps); return ps->top;} STDatatype StackTop(ST* ps){ assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1];}bool isValid(char * s){ //初始化栈，并且确定一个返回值 ST st; StackInit(&st); bool math = true; //一个一个判断s里面的字符 while(*s){ //符合则压栈 if(*s == '(' || *s == '{' || *s == '['){ StackPush(&st, *s); ++s; }else{ //判断是否为空 if(StackEmpty(&st)){ math = false; break; }else{ //从顶部取出一个数据 STDatatype ch = StackTop(&st); StackPop(&st); if(*s == ']' && ch != '[' || *s == '}' && ch != '{' || *s == ')' && ch != '('){ math = false; break; }else{ ++s; } } } } //只有一个元素的时候 if(math == true){ math = StackEmpty(&st); } StackDestroy(&st); return math;}🍯2.用队列实现栈（传送门）
🍤请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。实例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
🔑思路：
🍤用两个队列来实现栈，所以我们就定义一个包含两个队列的结构体，同时将两个队列初始化
//在MyStack这个结构体中定义两个队列typedef struct { Queue q1; Queue q2;} MyStack;MyStack* myStackCreate() { //创建pst（包含两个队列） MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); assert(pst); //注意传过去的是结构体的地址 QueueInit(&pst->q1); QueueInit(&pst->q2); //初始化完成，返回MyStack return pst;}🍤当要压栈的时候，当q1和q2都为空时，随便存放到哪一个队列都可以，当q1和q2中有一个不为空时，存入的元素放到不为空的队列当中。
如果q1是空则将数据存放到q2否则将数据存放到q1
void myStackPush(MyStack* obj, int x) { assert(obj); //两个队列，谁不是空就往谁里面存储数据 if(!QueueEmpty(&obj->q1)){ QueuePush(&obj->q1, x); }else{ QueuePush(&obj->q2, x); }}🍤当要出栈的时候，把两个队列中不为空的那一个中的元素，一个一个出队放到第二个队列中，直到第一个队列只剩下最后一个元素时，则将此元素删除即可完成出栈。
首先定义empty 和 notempty存放q1和q2中的空队列和非空队列，先假定q1为空，q2为非空，然后再进行判断确定，将非空队列中的元素一个一个从非空队列中转移到空队列中，直到非空队列只剩下一个元素，再将这个元素放到top后删除，返回top。
//实现后进先出int myStackPop(MyStack* obj) { assert(obj); //定义两个队列，将q1和q2中的空给empty，非空给notempty Queue* empty = &obj->q1; Queue* notempty = &obj->q2; if(!QueueEmpty(&obj->q1)){ empty = &obj->q2; notempty = &obj->q1; } //将非空的队列中的值一个一个放到另外一个队列中，直到找到非空队列中的最后一个元素为止 while(QueueSize(notempty) > 1){ int front = QueueFront(notempty); QueuePush(empty, front); QueuePop(notempty); } //此时非空队列中只剩下一个数据，将这个元素保存到top中，并且在非空队列中删除 int top = QueueFront(notempty); QueuePop(notempty); return top;}
🍤如果队列不是空，则返回此队列最后一个元素及是栈顶
//此时两个队列中只有一个队列有数据，此时我们找到不为空的队列，将它的队尾返回，及是栈顶int myStackTop(MyStack* obj) { assert(obj); if(!QueueEmpty(&obj->q1)){ return QueueBack(&obj->q1); }else{ return QueueBack(&obj->q2); }}🍤当q1和q2都为空的时候，才能判断MyStack是空
//两个队列都是空及这个栈就是空bool myStackEmpty(MyStack* obj) { assert(obj); return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}🍤不能直接free obj，因为没有将obj结构体所指向的链表不会free，会造成内存泄漏
void myStackFree(MyStack* obj) { assert(obj); //所以我们先将obj所指向的链表free QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj);}
#include typedef int typedefData;//定义队列节点typedef struct QueueNode { typedefData Data; struct QueueNode* next;}QueueNode;//定义队列typedef struct Queue { //注意队列的结构体指针的定义 QueueNode* head;//队头 QueueNode* tail;//队尾}Queue;//初始化void QueueInit(Queue* pq);//判空bool QueueEmpty(Queue* pq);//入队void QueuePush(Queue* pq, typedefData x);//出队void QueuePop(Queue* pq);//获取队头元素typedefData QueueFront(Queue* pq);//获取队尾元素typedefData QueueBack(Queue* pq);//计算队列元素数量int QueueSize(Queue* pq);//销毁void QueueDestory(Queue* pq);//初始化void QueueInit(Queue* pq) { assert(pq); //先将两个结构体指针为空 pq->head = pq->tail = NULL;}//销毁void QueueDestory(Queue* pq) { assert(pq); //把头节点给cur QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } //将所有节点释放完之后，再将两个队头和队尾指针释放 pq->head = pq->tail = NULL;}//入队void QueuePush(Queue* pq, typedefData x) { assert(pq); //建立新的节点 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { printf("malloc fail: %s",strerror(errno)); exit(-1); } newnode->Data = x; newnode->next = NULL; //判断如果队尾为空，说明没有元素 if (pq->tail == NULL) { pq->head = pq->tail = newnode; }else { pq->tail->next = newnode; pq->tail = newnode; }}//出队void QueuePop(Queue* pq) { assert(pq); assert(pq->head != NULL && pq->tail != NULL); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QueueNode* next = pq->head->next; free(pq->head); pq->head = next; }}//判空bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL;}//计算队列元素数量int QueueSize(Queue* pq) { assert(pq); size_t size = 0; QueueNode* cur = pq->head; while (cur != NULL) { cur = cur->next; size++; } return size;}//获取队头元素typedefData QueueFront(Queue* pq) { assert(pq); //当head为空时，取head的值就没有意义了 assert(pq->head); return pq->head->Data;}//获取队尾元素typedefData QueueBack(Queue* pq) { assert(pq); //当head为空时，取tail的值就没有意义了 assert(pq->tail); return pq->tail->Data;}//在MyStack这个结构体中定义两个队列typedef struct { Queue q1; Queue q2;} MyStack;MyStack* myStackCreate() { //创建pst（包含两个队列） MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); assert(pst); //注意传过去的是结构体的地址 QueueInit(&pst->q1); QueueInit(&pst->q2); //初始化完成，返回MyStack return pst;}void myStackPush(MyStack* obj, int x) { assert(obj); //两个队列，谁不是空就往谁里面存储数据 if(!QueueEmpty(&obj->q1)){ QueuePush(&obj->q1, x); }else{ QueuePush(&obj->q2, x); }}//实现后进先出int myStackPop(MyStack* obj) { assert(obj); //定义两个队列，将q1和q2中的空给empty，非空给notempty Queue* empty = &obj->q1; Queue* notempty = &obj->q2; if(!QueueEmpty(&obj->q1)){ empty = &obj->q2; notempty = &obj->q1; } //将非空的队列中的值一个一个放到另外一个队列中，直到找到非空队列中的最后一个元素为止 while(QueueSize(notempty) > 1){ int front = QueueFront(notempty); QueuePush(empty, front); QueuePop(notempty); } //此时非空队列中只剩下一个数据，将这个元素保存到top中，并且在非空队列中删除 int top = QueueFront(notempty); QueuePop(notempty); return top;}//此时两个队列中只有一个队列有数据，此时我们找到不为空的队列，将它的队尾返回，及是栈顶int myStackTop(MyStack* obj) { assert(obj); if(!QueueEmpty(&obj->q1)){ return QueueBack(&obj->q1); }else{ return QueueBack(&obj->q2); }}//两个队列都是空及这个栈就是空bool myStackEmpty(MyStack* obj) { assert(obj); return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}//不能直接free obj，因为没有将obj结构体所指向的链表不会free，会造成内存泄漏void myStackFree(MyStack* obj) { assert(obj); //所以我们先将obj所指向的链表free QueueDestory(&obj->q1); QueueDestory(&obj->q2); free(obj);}/** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj);*/🍯3.用栈实现队列（传送门）
🍤请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。实例：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
🔑思路：
🍤 用栈实现队列，需要两个栈一个存储数据push和一个删除数据pop
🍤初始化定义obj结构体，首先创造obj再将obj中的pop和push初始化
//初始化定义objMyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); assert(obj); StackInit(&obj->push); StackInit(&obj->pop); return obj;}🍤直接再push插入即可
//将元素 x 推到队列的末尾void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->push, x);}🍤删除一个数据要判断pop中是否有数据，当pop中有数据时，直接将pop栈顶删除即可，否则将push中元素一个一个移动到pop中，得到栈顶即是队列队头，将队头返回删除
//从队列的开头移除并返回元素int myQueuePop(MyQueue* obj) { assert(obj); int ret = 0; //判断pop是否为空，为空从push中依次移动数据到pop再删除pop栈顶元素 if(StackEmpty(&obj->pop)){ while(!StackEmpty(&obj->push)){ StackPush(&obj->pop, StackTop(&obj->push)); StackPop(&obj->push); } ret = StackTop(&obj->pop); StackPop(&obj->pop); //pop非空直接删除栈顶元素 }else{ ret = StackTop(&obj->pop); StackPop(&obj->pop); } return ret;}🍤查找队头数据不用删除队头，其他操作和删除队头一样
//获取队头数据，并返回int myQueuePeek(MyQueue* obj) { assert(obj); int ret = 0; //判断pop是否为空，为空从push中依次移动数据到pop再删除pop栈顶元素 if(StackEmpty(&obj->pop)){ while(!StackEmpty(&obj->push)){ StackPush(&obj->pop, StackTop(&obj->push)); StackPop(&obj->push); } ret = StackTop(&obj->pop); //pop非空直接删除栈顶元素 }else{ ret = StackTop(&obj->pop); } return ret;}🍤当pop和push都为空时，obj才为空
//如果队列为空，返回 true ；否则，返回 falsebool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pop) && StackEmpty(&obj->push);}🍤释放空间，要求首先释放pop和push再释放obj，否则找不到pop和push
//释放空间void myQueueFree(MyQueue* obj) { Stackdestroy(&obj->pop); Stackdestroy(&obj->push); free(obj);}
typedef int STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;void StackInit(ST* ps);void Stackdestroy(ST* ps);void StackPush(ST* ps, STDataType x);void StackPop(ST* ps);STDataType StackTop(ST* ps);int StackSize(ST* ps);bool StackEmpty(ST* ps);void StackInit(ST* ps){assert(ps);ps->a = NULL;ps->top = 0; // ps->top = -1;ps->capacity = 0;}void Stackdestroy(ST* ps){assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;}void StackPush(ST* ps, STDataType x){assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;}void StackPop(ST* ps){assert(ps);if(StackEmpty(ps)){ return; }ps->top--;}STDataType StackTop(ST* ps){assert(ps);if(StackEmpty(ps)){ return NULL; }return ps->a[ps->top - 1];}int StackSize(ST* ps){assert(ps);return ps->top;}bool StackEmpty(ST* ps){assert(ps);/*if (ps->top == 0){return true;}else{return false;}*/return ps->top == 0;}typedef struct { ST push; //插入 ST pop; //删除} MyQueue;//初始化定义objMyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); assert(obj); StackInit(&obj->push); StackInit(&obj->pop); return obj;}//将元素 x 推到队列的末尾void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->push, x);}//从队列的开头移除并返回元素int myQueuePop(MyQueue* obj) { assert(obj); int ret = 0; //判断pop是否为空，为空从push中依次移动数据到pop再删除pop栈顶元素 if(StackEmpty(&obj->pop)){ while(!StackEmpty(&obj->push)){ StackPush(&obj->pop, StackTop(&obj->push)); StackPop(&obj->push); } ret = StackTop(&obj->pop); StackPop(&obj->pop); //pop非空直接删除栈顶元素 }else{ ret = StackTop(&obj->pop); StackPop(&obj->pop); } return ret;}int myQueuePeek(MyQueue* obj) { assert(obj); int ret = 0; //判断pop是否为空，为空从push中依次移动数据到pop再删除pop栈顶元素 if(StackEmpty(&obj->pop)){ while(!StackEmpty(&obj->push)){ StackPush(&obj->pop, StackTop(&obj->push)); StackPop(&obj->push); } ret = StackTop(&obj->pop); //pop非空直接删除栈顶元素 }else{ ret = StackTop(&obj->pop); } return ret;}//如果队列为空，返回 true ；否则，返回 falsebool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pop) && StackEmpty(&obj->push);}//释放空间void myQueueFree(MyQueue* obj) { Stackdestroy(&obj->pop); Stackdestroy(&obj->push); free(obj);}/** * Your MyQueue struct will be instantiated and called as such: * MyQueue* obj = myQueueCreate(); * myQueuePush(obj, x); * int param_2 = myQueuePop(obj); * int param_3 = myQueuePeek(obj); * bool param_4 = myQueueEmpty(obj); * myQueueFree(obj);*/🍯4.（数组实现和链表实现）设计循环队列（传送门）
🍤设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。实例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
🍍数组实现
🔑思路：
🍤首先创建一个结构体，包含一个数组，数组长度，两个一个数组头下标一个数组尾下标，再给数组长度的时候，要多给一个空间，因为我们判断方法是，当front和tail相等时，表示数组中没有数据，当tail的下一个为front时表示数组满了，此时的ttail没有存储数据
typedef struct { int* a; //创建一个数组 int front; //队首 int tail; //依次遍历记录 int k; //队列的长度} MyCircularQueue;//创建一个循环队列结构体，队列长度为kMyCircularQueue* myCircularQueueCreate(int k) { //创建一个链表数组，包括一个数组 MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); assert(obj); //给数组创建开辟空间，注意要多开一个空间，因为要构建k个节点 //如果tail和front相等的话，表示队列为空，如果tail的下一个是front的话，表示队列满了 obj->a = (int*)malloc(sizeof(int)*(k+1)); //初始化 obj->front = obj->tail = 0; obj->k = k; return obj;}🍤插入一个数据前要判断是否满了。满了返回false，否则我们插入数据返回true，当插入数据时，如果tail位于最后一个位置时，记得将tail移动到0的位置，循环。
//插入一个元素，如果成功插入则返回真bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //如果满了，return false if(myCircularQueueIsFull(obj)){ return false; }else{ obj->a[obj->tail] = value; //如果满了，将tail放到第一个,否则继续 if(obj->tail == obj->k){ obj->tail = 0; }else{ obj->tail++; } } return true;}
🍤删除一个元素前要检查是否为空，之后删除一次元素九江front向后移动一位置，如果front移动到k的位置，则将front直接移动到下标0的位置
//删除一个元素，如果成功删除则返回真bool myCircularQueueDeQueue(MyCircularQueue* obj) { //如果队列为空 if(myCircularQueueIsEmpty(obj)){ return false; } //如果front指向最后一个元素则置为0，否则++ if(obj->front == obj->k){ obj->front = 0; }else{ obj->front++; } return true;}🍤从队首获取元素，判断结构体是否为空，然后直接返回front下标位置的元素即可
//从队首获取元素。如果队列为空，返回 -1int myCircularQueueFront(MyCircularQueue* obj) { //如果队列为空 if(myCircularQueueIsEmpty(obj)){ return -1; }else{ //front永远是队头的数据 return obj->a[obj->front]; }}🍤获取队尾元素时，判断结构体是否为空，正常情况直接返回tail上一个下标指向的元素即可，因为此时tail下标指向空间里没有存入新的元素，当tail==0时，队尾元素就是队列最后一个元素
typedef struct { int* a; //创建一个数组 int front; //队首 int tail; //依次遍历记录 int k; //队列的长度} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);bool myCircularQueueIsFull(MyCircularQueue* obj);//创建一个循环队列结构体，队列长度为kMyCircularQueue* myCircularQueueCreate(int k) { //创建一个链表数组，包括一个数组 MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); assert(obj); //给数组创建开辟空间，注意要多开一个空间，因为要构建k个节点 //如果tail和front相等的话，表示队列为空，如果tail的下一个是front的话，表示队列满了 obj->a = (int*)malloc(sizeof(int)*(k+1)); //初始化 obj->front = obj->tail = 0; obj->k = k; return obj;}//插入一个元素，如果成功插入则返回真bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //如果满了，return false if(myCircularQueueIsFull(obj)){ return false; }else{ obj->a[obj->tail] = value; //如果满了，将tail放到第一个,否则继续 if(obj->tail == obj->k){ obj->tail = 0; }else{ obj->tail++; } } return true;}//删除一个元素，如果成功删除则返回真bool myCircularQueueDeQueue(MyCircularQueue* obj) { //如果队列为空 if(myCircularQueueIsEmpty(obj)){ return false; } //如果front指向最后一个元素则置为0，否则++ if(obj->front == obj->k){ obj->front = 0; }else{ obj->front++; } return true;}//从队首获取元素。如果队列为空，返回 -1int myCircularQueueFront(MyCircularQueue* obj) { //如果队列为空 if(myCircularQueueIsEmpty(obj)){ return -1; }else{ //front永远是队头的数据 return obj->a[obj->front]; }}//获取队尾元素。如果队列为空，返回 -1 int myCircularQueueRear(MyCircularQueue* obj) { //如果队列为空 if(myCircularQueueIsEmpty(obj)){ return -1; }else if(obj->tail == 0){ //队尾的数据是在上一个位置 return obj->a[obj->k]; }else{ //返回tial-1位置数据 return obj->a[obj->tail-1]; }}//检查循环队列是否为空bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail;}//检查循环队列是否已满bool myCircularQueueIsFull(MyCircularQueue* obj) { //front在头，tail在尾 if(obj->front == 0 && obj->k == obj->tail){ return true; }else{ //front下标比tail大时 return obj->tail + 1 == obj->front; }}//释放空间，首先释放结构体内数组,再释放结构体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);*/🍤判断队列是否为空，tail和front相等队列就为空
//检查循环队列是否为空bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail;}🍤检查队列是否满了，正常情况当tail + 1 == front时队列满了，特殊情况，当tail为0，front是K时，队列也满了
//检查循环队列是否已满bool myCircularQueueIsFull(MyCircularQueue* obj) { //front在头，tail在尾 if(obj->front == 0 && obj->k == obj->tail){ return true; }else{ //front下标比tail大1时 return obj->tail + 1 == obj->front; }}🍤释放空间要求释放，结构体和结构体内数组，首先先释放数组
//释放空间，首先释放结构体内数组,再释放结构体void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj);}
typedef struct { int* a; //创建一个数组 int front; //数组头下标 int tail; //数组尾下标 int k; //队列的长度} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);bool myCircularQueueIsFull(MyCircularQueue* obj);//创建一个循环队列结构体，队列长度为kMyCircularQueue* myCircularQueueCreate(int k) { //创建一个链表数组，包括一个数组 MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); assert(obj); //给数组创建开辟空间，注意要多开一个空间，因为要构建k个节点 //如果tail和front相等的话，表示队列为空，如果tail的下一个是front的话，表示队列满了 obj->a = (int*)malloc(sizeof(int)*(k+1)); //初始化 obj->front = obj->tail = 0; obj->k = k; return obj;}//插入一个元素，如果成功插入则返回真bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //如果满了，return false if(myCircularQueueIsFull(obj)){ return false; }else{ obj->a[obj->tail] = value; //如果满了，将tail放到第一个,否则继续 if(obj->tail == obj->k){ obj->tail = 0; }else{ obj->tail++; } } return true;}//删除一个元素，如果成功删除则返回真bool myCircularQueueDeQueue(MyCircularQueue* obj) { //如果队列为空 if(myCircularQueueIsEmpty(obj)){ return false; } //如果front指向最后一个元素则置为0，否则++ if(obj->front == obj->k){ obj->front = 0; }else{ obj->front++; } return true;}//从队首获取元素。如果队列为空，返回 -1int myCircularQueueFront(MyCircularQueue* obj) { //如果队列为空 if(myCircularQueueIsEmpty(obj)){ return -1; }else{ //front永远是队头的数据 return obj->a[obj->front]; }}//获取队尾元素。如果队列为空，返回 -1 int myCircularQueueRear(MyCircularQueue* obj) { //如果队列为空 if(myCircularQueueIsEmpty(obj)){ return -1; }else if(obj->tail == 0){ //队尾的数据是在上一个位置 return obj->a[obj->k]; }else{ //返回tial-1位置数据 return obj->a[obj->tail-1]; }}//检查循环队列是否为空bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail;}//检查循环队列是否已满bool myCircularQueueIsFull(MyCircularQueue* obj) { //front在头，tail在尾 if(obj->front == 0 && obj->k == obj->tail){ return true; }else{ //front下标比tail大时 return obj->tail + 1 == obj->front; }}//释放空间，首先释放结构体内数组,再释放结构体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);*/🍍链表实现
🔑思路：
🍤创建MyCircularQueue包含两个指针head和tail，按照k要求的数量，依次创建节点并且将节点链接起来
//构造器，设置队列长度为 kMyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->head = NULL; obj->tail = NULL; //多创建一个链表节点,方便使用循环队列 k = k+1; while(k){ Node* node = (Node*)malloc(sizeof(Node)); if(obj->head == NULL && obj->tail == NULL){ obj->head = obj->tail = node; }else{ obj->tail->next = node; obj->tail = obj->tail->next; } k--; } //链接头和尾形成循环队列，再将head和tail在同一起跑线 obj->tail->next = obj->head; obj->tail = obj->head; return obj;}
🍤插入元素之前如果满了，返回false，没满插入元素
//向循环队列插入一个元素。如果成功插入则返回真bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //插入一个元素之前，检查是不是满了 if(myCircularQueueIsFull(obj)){ return false; }else{ obj->tail->Data = value; obj->tail = obj->tail->next; } return true;}🍤删除一个元素同理，检查是否为空，不为空的话直接把head往前移动即可
//从循环队列中删除一个元素。如果成功删除则返回真bool myCircularQueueDeQueue(MyCircularQueue* obj) { //删除一个元素之前，检查是否为空 if(myCircularQueueIsEmpty(obj)){ return false; }else{ obj->head = obj->head->next; } return true;}🍤获取队头元素时，判断是否为空
//从队首获取元素。如果队列为空，返回 -1int myCircularQueueFront(MyCircularQueue* obj) { //如果队列为空返回-1 if(myCircularQueueIsEmpty(obj)){ return -1; }else{ return obj->head->Data; }}🍤获取队尾元素同理，判断为空之后遍历寻找即可
//获取队尾元素。如果队列为空，返回 -1int myCircularQueueRear(MyCircularQueue* obj) { //如果队列为空返回-1 if(myCircularQueueIsEmpty(obj)){ return -1; }else{ Node* cur = obj->head; while(cur->next != obj->tail){ cur = cur->next; } return cur->Data; }}🍤当tail和head相等时，队列为空，当tail下一个指向head时，队列已满
//检查循环队列是否为空,空返回true非空返回falsebool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->tail == obj->head;}//检查循环队列是否已满,满了返回true没满返回falsebool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->tail->next == obj->head;}🍤释放空间先将head之后的节点释放最后释放head节点和obj
//释放队列空间，要求先释放head之后每一个链表节点空间，最后释放headvoid myCircularQueueFree(MyCircularQueue* obj) { Node* cur = obj->head; while(cur != obj->head){ Node* save = cur->next; free(cur); cur = save->next; } free(obj->head); free(obj);}
typedef int typdefData;//创建链表节点typedef struct Node{ typdefData Data; struct Node* next;}Node;//创建一头一尾的指针typedef struct { Node* head; Node* tail;} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);bool myCircularQueueIsFull(MyCircularQueue* obj);//构造器，设置队列长度为 kMyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->head = NULL; obj->tail = NULL; //多创建一个链表节点,方便使用循环队列 k = k+1; while(k){ Node* node = (Node*)malloc(sizeof(Node)); if(obj->head == NULL && obj->tail == NULL){ obj->head = obj->tail = node; }else{ obj->tail->next = node; obj->tail = obj->tail->next; } k--; } //链接头和尾形成循环队列，再将head和tail在同一起跑线 obj->tail->next = obj->head; obj->tail = obj->head; return obj;}//向循环队列插入一个元素。如果成功插入则返回真bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //插入一个元素之前，检查是不是满了 if(myCircularQueueIsFull(obj)){ return false; }else{ obj->tail->Data = value; obj->tail = obj->tail->next; } return true;}//从循环队列中删除一个元素。如果成功删除则返回真bool myCircularQueueDeQueue(MyCircularQueue* obj) { //删除一个元素之前，检查是否为空 if(myCircularQueueIsEmpty(obj)){ return false; }else{ obj->head = obj->head->next; } return true;}//从队首获取元素。如果队列为空，返回 -1int myCircularQueueFront(MyCircularQueue* obj) { //如果队列为空返回-1 if(myCircularQueueIsEmpty(obj)){ return -1; }else{ return obj->head->Data; }}//获取队尾元素。如果队列为空，返回 -1int myCircularQueueRear(MyCircularQueue* obj) { //如果队列为空返回-1 if(myCircularQueueIsEmpty(obj)){ return -1; }else{ Node* cur = obj->head; while(cur->next != obj->tail){ cur = cur->next; } return cur->Data; }}//检查循环队列是否为空,空返回true非空返回falsebool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->tail == obj->head;}//检查循环队列是否已满,满了返回true没满返回falsebool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->tail->next == obj->head;}//释放队列空间，要求先释放head之后每一个链表节点空间，最后释放headvoid myCircularQueueFree(MyCircularQueue* obj) { Node* cur = obj->head; while(cur != obj->head){ Node* save = cur->next; free(cur); cur = save->next; } free(obj->head); 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);*/总结
