栈和队列的4道面试题【详细解析】【代码实现】

news/2024/5/20 10:06:06

栈和队列的面试题

1.有效的括号（栈实现）

题目：

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

思路：

  1. 首先我们可以知道我们需要去比较字符串内的元素，并且我们需要用到后进先出的场景，因此这里我们考虑用栈来解决问题
  2. 我们将前括号放到栈内，s指针如果指向的是后括号，就让其和栈内的栈顶元素对比，如果匹配就将栈顶元素弹出，s继续遍历
  3. 一旦不匹配，或者栈空了，s还有后括号没有匹配，或者栈还有元素，s没有后括号匹配了就是无效字符串，返回false

代码实现：

由于我们是使用C语言写oj题，因此我们需要自己去编写栈的定义和栈的接口实现

如果是在leetcode上，头文件之类的自己会包含，我们不用去管

接口：
// 这里的栈我们用动态顺序表实现 (也可以用静态顺序表实现[不好扩容和定义空间大小])
# include<stdio.h>
# include<assert.h>
# include<stdlib.h>
# include<stdbool.h>typedef char SLDataType;
typedef struct Stack
{SLDataType* _a;int _top; // 栈顶下标 [规定栈顶下标：最后一个有效数据的下一个位置]int _capacity; // 数组的有效空间大小 
}Stack;// 栈的初始化
void StackInit(Stack* ps);// 栈的销毁
void StackDestory(Stack* ps);// 栈是能从栈顶  存数据或者取数据，因此不存在尾插头插之类的
// 入栈
void StackPush(Stack* ps, SLDataType x);// 出栈
void StackPop(Stack* ps);// 栈的数据个数获取
//int StackSize(Stack st); //其实理论上获取元素个数只需要传值调用就行 但是为了保持接口一致性，我们采用指针
int StackSize(Stack* ps);// 获取栈顶元素
SLDataType StackTop(Stack* ps);// 判断栈是否为空
int StackEmpty(Stack* ps); // 是空返回1  不是空的返回0// 栈的初始化
void StackInit(Stack* ps)
{assert(ps); // ps不能为NULL// 栈的初始化/*ps->_a = NULL;ps->_top = 0;ps->_capacity = 0;*/// 除了上面这种初始化。也可以这样初始化SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType) * 4); // 这样后面入栈时无需判断 空间是否为0 if (tmp == NULL){perror("StackInit():malloc()");return;}ps->_a = tmp;ps->_top = 0;ps->_capacity = 4;
}// 栈的销毁
void StackDestory(Stack* ps)
{assert(ps);free(ps->_a);ps->_a = NULL;ps->_top = ps->_capacity = 0;
}// 入栈
void StackPush(Stack* ps, SLDataType x)
{assert(ps);// 插入之前 判断栈的空间是否足够新的数据插入if (ps->_top == ps->_capacity) // 判断空间是否足够 {int newcapacity = ps->_capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->_a, sizeof(SLDataType) * newcapacity); // 增容if (tmp == NULL) // 判断是否增容成功{perror("StackPush():realloc()");return;}// 更新栈ps->_a = tmp;ps->_capacity = newcapacity;}ps->_a[ps->_top] = x; // 入栈ps->_top++; // 让top记录的是栈顶 也就是最后一个数据的下一个位置
}// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps->_top > 0); // 栈里面要有数据才能出栈ps->_top--; // 让top--就行 最后一个数据的下标是 top - 1
}// 栈的数据个数获取
int StackSize(Stack* ps)
{assert(ps);return ps->_top; // top代表栈顶下标，是最后的一个数据的下标 + 1  其实就是栈的数据个数
}// 获取栈顶元素
SLDataType StackTop(Stack* ps)
{assert(ps);assert(ps->_top > 0); // 没有数据还怎么获取return ps->_a[ps->_top - 1]; // top是栈顶下标，top - 1才是最后一个数据的下标
}// 判断栈是否为空
int StackEmpty(Stack* ps) // 是空返回1  不是空的返回0
{assert(ps);return ps->_top == 0 ? 1 : 0; // ps->pos只要为0就说明栈内没有数据了//return !ps->_top; // ps->top 为0 就返回1，为真就返回 0 ，除了0的数都是真
}
代码：
bool isValid(char* s)
{// 由于这道题需要用到后进先出的特性，因此我们使用栈来解决// 创建一个栈Stack st;StackInit(&st); // 初始化bool ret = true; // 用来判断字符串是否有效// 遍历字符串while (*s != '\0'){// 如果s指针指向的是前括号就入栈if (*s == '(' || *s == '[' || *s == '{'){StackPush(&st, *s);s++; // 让s往后走}else{// 走到这里有可能是s后括号多，栈内已经没有前括号了,那后面去取栈顶元素自然无法取出if (StackEmpty(&st))// 判断栈是否空了{// 走进来就说明栈内没有元素了，但是s还有后括号ret = false; // 无效字符串break;}// 判断s下一步指向的是否是后括号，是否匹配栈顶的前括号char top = StackTop(&st); // 取出栈顶元素// 每一种括号都要判断一下是否匹配到if (*s == ')' && top != '('){// 走到这里说明没有匹配上ret = false; // 无效字符串break; // 不在这里return false是因为会有内存泄漏问题，跳出循环去外面统一调用销毁函数}if (*s == ']' && top != '['){// 走到这里说明没有匹配上ret = false; // 无效字符串break;}if (*s == '}' && top != '{'){// 走到这里说明没有匹配上ret = false; // 无效字符串break;}// 走到这里说明有括号配对成功，让s继续往后遍历s++;// 栈顶元素匹配成功之后要弹出来，防止后面还有括号要配对StackPop(&st);}}// 走到这里，有可能是全部匹配完是true。 //也有可能是s字符串只有前括号比后括号多 退出循环时，栈内还有许多前括号if (!StackEmpty(&st)) // 判断栈是否为空ret = false; // 不是空的就是无效字符串StackDestory(&st); // 销毁栈if (ret == false)return false;// 走到这里就说明是有效字符串return true;
}

2.用队列实现栈

题目：

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：

  1. 我们知道栈是后进先出的，队列是先进先出的
  2. 插入数据（入栈），找到队列的队尾然后插入数据就行
  3. 弹出数据（出栈），就需要我们另想办法了
  4. 这里我们创建两个队列，在弹出队列的时候我们获取队尾的数据，把剩下的数据放到另外一个空的队列，然后让队尾的数据从队头出去。这样可以实现后进先出的效果。

image-20240507151334488

代码实现：

队列的接口：
// 这里的队列的底层数据结构是单链表
// 定义节点的结构体typedef int QDataType;
typedef struct QueueNode
{QDataType _data;struct QueueNode* _next;
}QueueNode;// 和单链表不一样的是队列最好要有指向第一个节点和尾节点的指针
typedef struct Queue
{QueueNode* _head;QueueNode* _tail;
}Queue;// 队列的接口（也就是函数） 
// 为什么这里的接口和单链表的时候不一样，不需要传二级指针呢，因为我们把指针放到了结构体内部，传的是结构体指针
// 通过结构体指针找到结构体，再从结构体内部拿到节点的指针，再从这个节点指针找到节点，这里起到的作用就类似于二级指针// 队列的初始化
void QueueInit(Queue* pq);// 队列的销毁
void QueueDestory(Queue* pq);// 入队
void QueuePush(Queue* pq, QDataType x);// 出队
void QueuePop(Queue* pq);// 获取队头的数据
QDataType QueueFront(Queue* pq);// 获取队尾的数据
QDataType QueueBack(Queue* pq);// 判断队列是否为空  [返回1就是空，返回0就是非空]
int QueueEmpty(Queue* pq);// 获取队列的数据个数
int QueueSize(Queue* pq);// 队列的打印
void QueuePrint(Queue* pq);// 队列的初始化
void QueueInit(Queue* pq)
{assert(pq);//pq不能为NULL// 初始化pq->_head = NULL;pq->_tail = NULL;}// 队列的销毁
void QueueDestory(Queue* pq)
{assert(pq);// 遍历队列，删除每一个节点QueueNode* cur = pq->_head;while (cur) {QueueNode* next = cur->_next;free(cur);cur = next;}pq->_head = pq->_tail = NULL;
}// 入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);// 入队其实就是让新节点尾插到链表中QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("QueuePush():malloc()");exit(-1);}newnode->_data = x;newnode->_next = NULL;// 判断列队是否为空if (pq->_head == NULL){pq->_head = pq->_tail = newnode;}else{// 尾插pq->_tail->_next = newnode;pq->_tail = newnode;}}// 出队
void QueuePop(Queue* pq)
{assert(pq);assert(pq->_head); // 队列是空的怎么出队// 头删QueueNode* next = pq->_head->_next; // 把第一个节点的下一个节点存储起来free(pq->_head);pq->_head = next;// 这里有个问题，当最后一个节点删除完之后，pq->_head = NULL// 但是pq->_tail 就变成野指针了if (pq->_head == NULL){pq->_tail = NULL;}}// 获取队头的数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->_head);// 队列为空怎么获取队头数据return pq->_head->_data;
}// 获取队尾的数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->_tail); // 等价于assert(pq->_head); 头为空，尾也肯定为空，return pq->_tail->_data;
}// 判断队列是否为空 [返回1就是空，返回0就是非空]
int QueueEmpty(Queue* pq)
{assert(pq);return pq->_head == NULL ? 1 : 0;
}// 获取队列的数据个数
int QueueSize(Queue* pq)
{assert(pq);// 遍历队列统计数据个数QueueNode* cur = pq->_head;int size = 0;while (cur){size++;cur = cur->_next;}return size;
}// 队列的打印
void QueuePrint(Queue* pq)
{assert(pq);assert(pq->_head);while (!QueueEmpty(pq)){printf("%d ", QueueFront(pq));QueuePop(pq); // 从队头拿出一个数据要将其删除}printf("\n");}
代码：
// 这个栈由两个队列实现
typedef struct 
{Queue _q1;Queue _q2;
} MyStack;MyStack* myStackCreate() 
{// 创建我们的栈// MyStack st; // 局部变量的生命周期只存在函数，这样创建的st无法传递给外部使用MyStack* st = (MyStack*)malloc(sizeof(MyStack));QueueInit(&st->_q1);QueueInit(&st->_q2);return st;
}void myStackPush(MyStack* obj, int x)
{//  为了实现栈的先进后出，我们创建了两个队列，一个队列是空的，一个队列存储数据if(!QueueEmpty(&obj->_q1)) // 判断q1队列是否 不为空{// 如果q1队列不是空的就插入到q1队列QueuePush(&obj->_q1, x);}else // 如果两个队列都是空，会走到这里{// q2队列不是空的就插入q2队列QueuePush(&obj->_q2, x);}
}int myStackPop(MyStack* obj) 
{// 实现后进先出，让有数据的队列除了队尾元素，剩下的移动到空队列，然后在弹出剩下的队尾元素即可//这里我们假设 q1是空的，q2不是空的Queue* empty = &obj->_q1;Queue* noempty = &obj->_q2;// 判断q2是否为空if(QueueEmpty(&obj->_q2)) {// q2是空的，说明前面的假设错误，更正empty = &obj->_q2;noempty = &obj->_q1;}// 让有数据的队列 除了队尾元素，全部都转移到空队列while(QueueSize(noempty) > 1) // 只转移队尾元素之前的元素{// 让有数据的队列的队头尾插到空队列QueuePush(empty, QueueFront(noempty));QueuePop(noempty); // 把有数据队列的队头元素弹出，这样队头才能更新}// 走到这里 有数据队列就剩下一个数据了int top = QueueBack(noempty);QueuePop(noempty); // 出栈return top;
}int myStackTop(MyStack* obj) 
{// 找到有数据的队列的队尾if(!QueueEmpty(&obj->_q1)){return QueueBack(&obj->_q1);}else // 题目说了每次调用 pop 和 top 都保证栈不为空 因此这里无需对两个队列为空的情况做处理{return QueueBack(&obj->_q2);}}bool myStackEmpty(MyStack* obj) 
{// 两个队列都为空，栈才为空return QueueEmpty(&obj->_q1) && QueueEmpty(&obj->_q2);
}void myStackFree(MyStack* obj) 
{QueueDestory(&obj->_q1);QueueDestory(&obj->_q2);free(obj);obj = NULL;
}

3.用栈实现队列

题目：

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路：

  1. 要通过两个栈实现先进先出的队列，我们要思考数据转移的特性

  2. 我们发现，我们把栈的数据转移到另外一个栈的时候，数据的顺序会倒转

  3. image-20240507223619789

  4. image-20240507223635988

  5. 然后我们发现，这样就是先进先出了，1，2， 3， 4压进去，出来也是从栈顶出来，1, 2, 3, 4。 也就是说 第一个栈的栈顶就是队列的队尾，第二个栈的栈顶就是队列的队头。

    • 那我们给这个队列插入数据时候，要从队尾插入，也就是要把数据从第二个栈全部转移到第一个栈。
    • 队列导出数据的时候，也就是从队头出，那就要把数据从第一个栈全部转移到第二个栈。

代码实现：

接口：
// 这里的栈我们用动态顺序表实现 (也可以用静态顺序表实现[不好扩容和定义空间大小])typedef int SLDataType;
typedef struct Stack
{SLDataType* _a;int _top; // 栈顶下标 [规定栈顶下标：最后一个有效数据的下一个位置]int _capacity; // 数组的有效空间大小 
}Stack;// 栈的初始化
void StackInit(Stack* ps);// 栈的销毁
void StackDestory(Stack* ps);// 栈是能从栈顶  存数据或者取数据，因此不存在尾插头插之类的
// 入栈
void StackPush(Stack* ps, SLDataType x);// 出栈
void StackPop(Stack* ps);// 栈的数据个数获取
//int StackSize(Stack st); //其实理论上获取元素个数只需要传值调用就行 但是为了保持接口一致性，我们采用指针
int StackSize(Stack* ps);// 获取栈顶元素
SLDataType StackTop(Stack* ps);// 判断栈是否为空
int StackEmpty(Stack* ps); // 是空返回1  不是空的返回0// 栈的初始化
void StackInit(Stack* ps)
{assert(ps); // ps不能为NULL// 栈的初始化/*ps->_a = NULL;ps->_top = 0;ps->_capacity = 0;*/// 除了上面这种初始化。也可以这样初始化SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType) * 4); // 这样后面入栈时无需判断 空间是否为0 if (tmp == NULL){perror("StackInit():malloc()");return;}ps->_a = tmp;ps->_top = 0;ps->_capacity = 4;
}// 栈的销毁
void StackDestory(Stack* ps)
{assert(ps);free(ps->_a);ps->_a = NULL;ps->_top = ps->_capacity = 0;
}// 入栈
void StackPush(Stack* ps, SLDataType x)
{assert(ps);// 插入之前 判断栈的空间是否足够新的数据插入if (ps->_top == ps->_capacity) // 判断空间是否足够 {int newcapacity = ps->_capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->_a, sizeof(SLDataType) * newcapacity); // 增容if (tmp == NULL) // 判断是否增容成功{perror("StackPush():realloc()");return;}// 更新栈ps->_a = tmp;ps->_capacity = newcapacity;}ps->_a[ps->_top] = x; // 入栈ps->_top++; // 让top记录的是栈顶 也就是最后一个数据的下一个位置
}// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps->_top > 0); // 栈里面要有数据才能出栈ps->_top--; // 让top--就行 最后一个数据的下标是 top - 1
}// 栈的数据个数获取
int StackSize(Stack* ps)
{assert(ps);return ps->_top; // top代表栈顶下标，是最后的一个数据的下标 + 1  其实就是栈的数据个数
}// 获取栈顶元素
SLDataType StackTop(Stack* ps)
{assert(ps);assert(ps->_top > 0); // 没有数据还怎么获取return ps->_a[ps->_top - 1]; // top是栈顶下标，top - 1才是最后一个数据的下标
}// 判断栈是否为空
int StackEmpty(Stack* ps) // 是空返回1  不是空的返回0
{assert(ps);return ps->_top == 0 ? 1 : 0; // ps->pos只要为0就说明栈内没有数据了//return !ps->_top; // ps->top 为0 就返回1，为真就返回 0 ，除了0的数都是真
}
代码（自己实现的版本）：
typedef struct 
{Stack _s1;Stack _s2;    
} MyQueue;MyQueue* myQueueCreate() 
{// 创建栈MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pq->_s1);StackInit(&pq->_s2);return pq;
}void myQueuePush(MyQueue* obj, int x) 
{// 给队列插入元素，要在第一个栈插入// 如果第二个栈有数据，要将其全部转移到第一个栈if(!StackEmpty(&obj->_s2)){// 第二个栈的数据有数据，将其全部转移到第一个栈while(StackSize(&obj->_s2) > 0){// 转移StackPush(&obj->_s1, StackTop(&obj->_s2));// 让第二个栈的数据出栈StackPop(&obj->_s2);}}// 走到这里，如果第二个栈有数据，也全部转移到第一个栈// 如果第二个栈没有数据，那就直接在第一个栈插入数据就好StackPush(&obj->_s1, x);    
}int myQueuePop(MyQueue* obj) 
{// 要找到队头（队列开头的元素）就要把全部数据都放在第二个栈，栈顶的数据就是队头if(!StackEmpty(&obj->_s1)) {// 第一个栈的数据有数据，将其全部转移到第二个栈while(StackSize(&obj->_s1) > 0){// 转移StackPush(&obj->_s2, StackTop(&obj->_s1));// 让第一个栈的数据出栈StackPop(&obj->_s1);}}// 由于题目说了一个空的队列不会调用 pop 或者 peek 操作// 因此这里不用判断两个栈是否为空// 走到这里数据一定在第二个栈int ret = StackTop(&obj->_s2);StackPop(&obj->_s2); // 移除元素return ret;
}int myQueuePeek(MyQueue* obj) 
{// 要找到队头（队列开头的元素）就要把全部数据都放在第二个栈，栈顶的数据就是队头if(!StackEmpty(&obj->_s1)){// 第一个栈的数据有数据，将其全部转移到第二个栈while(StackSize(&obj->_s1) > 0){// 转移StackPush(&obj->_s2, StackTop(&obj->_s1));// 让第一个栈的数据出栈StackPop(&obj->_s1);}}// 由于题目说了一个空的队列不会调用 pop 或者 peek 操作// 因此这里不用判断两个栈是否为空// 返回队头，也就是第二个栈的栈顶数据return StackTop(&obj->_s2);
}bool myQueueEmpty(MyQueue* obj) 
{// 如果两个栈都为空，队列才是空return StackEmpty(&obj->_s1) && StackEmpty(&obj->_s2);
}void myQueueFree(MyQueue* obj) 
{StackDestory(&obj->_s1);StackDestory(&obj->_s2);free(obj);obj = NULL;
}
优化后的代码：
typedef struct 
{Stack _pushST; // 用于插入数据Stack _popST; // 用于出数据
} MyQueue;MyQueue* myQueueCreate() 
{// 创建栈MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pq->_pushST);StackInit(&pq->_popST);return pq;
}void myQueuePush(MyQueue* obj, int x) 
{// 直接把数据插入到pushST栈内StackPush(&obj->_pushST, x);
}int myQueuePop(MyQueue* obj) 
{// 这个函数的功能和peek函数的功能就多了一个要移除，也就是让队头数据弹出// 那我们就考虑让代码复用int ret = myQueuePeek(obj);StackPop(&obj->_popST); // 代码复用return ret;
}int myQueuePeek(MyQueue* obj) 
{// 要找到队头 也就是popST的栈顶数据// 要分两种情况，//1.如果popST栈没有数据，那就把pushST栈的数据转移到popST栈内//2.如果popST有数据，直接返回栈顶的数据，这个数据就是队头if(!StackEmpty(&obj->_popST)){// popST有数据，直接返回栈顶数据，就是队头return StackTop(&obj->_popST);}else{// popST为空，将pushST栈的数据转移到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->_pushST) && StackEmpty(&obj->_popST);
}void myQueueFree(MyQueue* obj) 
{StackDestory(&obj->_popST);StackDestory(&obj->_pushST);free(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

思路：

这里的队列我们底层使用数组实现。

  1. 由于是循环队列，队头出数据，队尾入数据，首尾要相连。因此我们才用两个指针来实现数据的弹出和插入。
  2. 但是需要注意的是，我们要给数组留一个空间，是空的，不能使用的，不然的话我们无法判断该队列是空的还是满的

image-20240508103624619

image-20240508105626453

如图所示，当头和尾指针在一起的时候无法判断队列是空的还是满的。

  1. 为了解决这个问题，我们再数组中留一个空间不使用，当rear尾指针指向空的时候，队列就是满的。当front和rear再一起的时候，队列就是空的

image-20240508105925701

image-20240508105934563

  1. 但是这个空的空间是会变动的，我们如何去判断，rear此时刚好指向的是front前一个的空间呢（这个空间就是空的）.。我们通过一个公式 (rear+1) % (k + 1) == front。 只要满足这个公式，就说明rear此时在front的前一个空间，就说明此时rear指向空的空间，就说明此时队列已经满了

image-20240508111546237

  1. 当front == rear的时候，队列就是空的

image-20240508111919779

代码实现：

题目中有很多函数接口要实现，这里我们先完成一些简单的，方便我们后面进行函数复用。

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。

要想完成其他函数功能的实现，我们要先有一个循环队列的构造

MyCircularQueue* myCircularQueueCreate(int k) 
{// 给结构体申请空间MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));// 给结构体内的数组申请空间q->_a = malloc(sizeof(int) * (k + 1)); // 要多申请一个空间q->_front = 0;q->_rear = 0;
}

代码中的k+1 为了给数组多申请一个空间，前面我们的思路说了，这个空间是不插入数据的，一旦rear指针走到这个空间就代表队列满了。

  • isEmpty(): 检查循环队列是否为空。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{// 只要两个指针走到一起就说明队列满了return obj->_front == obj->_rear;
}
  • isFull(): 检查循环队列是否已满。
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{// 只要rear指针走到了front指针的前一个空间，也就是我们留着不插入数据的空间。就说明队列满了return obj->_front == (obj->_rear + 1) % (k + 1);}

代码中的(obj->_rear + 1) % (k + 1)是为了应对多种情况，大部分情况下，队列满了，rear+1 就是front，但是如果rear刚好在数组最后一个空间，这个时候+1就越界了。如图所示：

image-20240508150943220

因此让其% 上 数组空间个数，可以处理全部清弃情况。

  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{// 插入元素之前，要判断该队列是否满了if(myCircularQueueIsFull(obj))return false; // 满了直接返回false// 走到这里就是没满，那就插入obj->_a[obj->_rear] = value;obj->_rear++; // rear下标指向的是队尾数据的下一个空间// 这里要注意 如果rear已经指向最后一个空间了，此时+1会越界obj->_rear %= (k + 1); // 如果越界了就会回到0，不越界没有影响return true;
}

代码中要注意obj->_rear %= (k + 1);的处理。没有这个处理在下图的情况会报错。

image-20240508150943220

  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{// 删除元素之前要看看队列是不是空的if(myCircularQueueIsEmpty(obj))return false;// 走到这里就说明不是空的obj->_front++; //直接让队头往后移动// 这里同样要考虑front是否会越界的问题obj->_front %= (k + 1); return true;
}

越界的情况如下图：

front一直要++到rear才能删除干净，但是front会越界，因此需要处理。

image-20240508145324746

  • Front: 从队首获取元素。如果队列为空，返回 -1 。
int myCircularQueueFront(MyCircularQueue* obj) 
{// 获取队头数据之前，要判断队列是否为空if(myCircularQueueIsEmpty(obj))return -1;// 获取队头int head = obj->_a[obj->_front];return head;
}
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
int myCircularQueueRear(MyCircularQueue* obj)
{// 要获取队尾的数据，同样要判断队列是否为空if(myCircularQueueIsEmpty(obj))return -1;// 获取队尾int tail = obj->_rear - 1;// 要注意rear指针越界的情况if(tail == -1)tail = obj->_k;// 一共有k + 1个空间，最后一个下标就是kreturn obj->_a[tail];
}

image-20240508153543022

最后的全部代码：

typedef struct 
{int* _a; // 不知道数组空间要开多大，给个指针int _front; // 对头int _rear; // 队尾int _k; // 队列长度为 k 
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) 
{// 给结构体申请空间MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));// 给结构体内的数组申请空间q->_a = (int*)malloc(sizeof(int) * (k + 1)); // 要多申请一个空间q->_front = 0;q->_rear = 0;q->_k = k;return q;
}// 手动加两个声明，才能使用让我们的函数复用。也可以自己去调换一下函数的定义顺序
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{// 插入元素之前，要判断该队列是否满了if(myCircularQueueIsFull(obj))return false; // 满了直接返回false// 走到这里就是没满，那就插入obj->_a[obj->_rear] = value;obj->_rear++; // rear下标指向的是队尾数据的下一个空间// 这里要注意 如果rear已经指向最后一个空间了，此时+1会越界obj->_rear %= (obj->_k + 1); // 如果越界了就会回到0，不越界没有影响return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{// 删除元素之前要看看队列是不是空的if(myCircularQueueIsEmpty(obj))return false;// 走到这里就说明不是空的obj->_front++; //直接让队头往后移动// 这里同样要考虑front是否会越界的问题obj->_front %= (obj->_k + 1); return true;
}int myCircularQueueFront(MyCircularQueue* obj) 
{// 获取队头数据之前，要判断队列是否为空if(myCircularQueueIsEmpty(obj))return -1;// 获取队头int head = obj->_a[obj->_front];return head;
}int myCircularQueueRear(MyCircularQueue* obj)
{// 要获取队尾的数据，同样要判断队列是否为空if(myCircularQueueIsEmpty(obj))return -1;// 获取队尾int tail = obj->_rear - 1;// 要注意rear指针越界的情况if(tail == -1)tail = obj->_k;// 一共有k + 1个空间，最后一个下标就是kreturn obj->_a[tail];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{// 只要两个指针走到一起就说明队列满了return obj->_front == obj->_rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{// 只要rear指针走到了front指针的前一个空间，也就是我们留着不插入数据的空间。就说明队列满了return (obj->_rear + 1) % (obj->_k + 1) == obj->_front;}void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->_a);free(obj);
}

在使用函数复用的时候要注意函数的声明问题

手动加两个声明，才能使用让我们的函数复用。也可以自己去调换一下函数的定义顺序

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);obj->_front++; //直接让队头往后移动// 这里同样要考虑front是否会越界的问题obj->_front %= (obj->_k + 1); return true;
}int myCircularQueueFront(MyCircularQueue* obj) 
{// 获取队头数据之前，要判断队列是否为空if(myCircularQueueIsEmpty(obj))return -1;// 获取队头int head = obj->_a[obj->_front];return head;
}int myCircularQueueRear(MyCircularQueue* obj)
{// 要获取队尾的数据，同样要判断队列是否为空if(myCircularQueueIsEmpty(obj))return -1;// 获取队尾int tail = obj->_rear - 1;// 要注意rear指针越界的情况if(tail == -1)tail = obj->_k;// 一共有k + 1个空间，最后一个下标就是kreturn obj->_a[tail];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{// 只要两个指针走到一起就说明队列满了return obj->_front == obj->_rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{// 只要rear指针走到了front指针的前一个空间，也就是我们留着不插入数据的空间。就说明队列满了return (obj->_rear + 1) % (obj->_k + 1) == obj->_front;}void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->_a);free(obj);
}

在使用函数复用的时候要注意函数的声明问题

手动加两个声明，才能使用让我们的函数复用。也可以自己去调换一下函数的定义顺序

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

http://www.mrgr.cn/p/78423358

相关文章

紧跟生成式AI暴雨发布新时代推理服务器

紧跟生成式AI暴雨发布新时代推理服务器

近日&#xff0c;暴雨发布最新训推一体AI服务器&#xff0c;以大容量内存和灵活的高速互连选项满足各种AI应用场景&#xff0c;最大可能支持扩展插槽&#xff0c;从而大幅提升智能算力性能&#xff0c;以最优的性能和成本为企业的模型训练推理落地应用提供更好的通用算力。 AIG…
阅读更多...
Java里的String使用

Java里的String使用

1.Java WinForm项目 public static void main(String[] args) {String testString"22";String testString2"1096";String testString3"22";Student studentnew Student();student.Age"22";Test(student.Age);Test2(student.Age); }pu…
阅读更多...
【Qt QML】QLibrary加载共享库中的类

【Qt QML】QLibrary加载共享库中的类

QLibrary是一个用于加载动态链接库&#xff08;或称为共享库&#xff09;的类。它提供了一种独立于平台的方式来访问库中的功能。 在QLibrary中&#xff0c;可以通过构造函数或setFileName()方法设置要加载的库文件名。当加载库文件时&#xff0c;QLibrary会搜索所有平台特定的…
阅读更多...
trunk聚合

trunk聚合

Eth-Trunk又叫以太网链路聚合Eth-Trunk，它通过将多条以太网物理链路捆绑在一起成为一条逻辑链路。达到增加链路带宽的目的。在实现增大带宽目的的同时，Eth-Trunk采用备份链路的机制，可以有效的提高设备之间链路的可靠性。每个聚合组唯一对应着一个逻辑接口，这个逻辑接口称之…
阅读更多...
buuctf-pwn-[OGeek2019]babyrop

buuctf-pwn-[OGeek2019]babyrop

查看一下保护情况丢进ida里分析主函数调用了一个含有alarm的函数，这个函数会设置一个定时器，到时间自动退出程序 为了方便调试，我们直接patch掉这个函数 接着分析，主函数读入了一个随机数，并将其传入sub_804871F函数 sub_804871F函数读取输入，并检查输入的是否和随机数相…
阅读更多...
Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】

Go 语言基础之指针、复合类型【数组、切片、指针、map、struct】

1、数组 特别需要注意的是&#xff1a;在 Go 语言中&#xff0c;数组长度也是数组类型的一部分&#xff01;所以尽管元素类型相同但是长度不同的两个数组&#xff0c;它们的类型并不相同。 1.1、数组的初始化 1.1.1、通过初始化列表{}来设置值 var arr [3]int // int类型的数…
阅读更多...
团队作业4——项目冲刺 第 2篇 Scrum 冲刺博客

团队作业4——项目冲刺 第 2篇 Scrum 冲刺博客

这个作业属于哪个课程 软件工程这个作业要求在哪里 团队作业4——项目冲刺这个作业的目标 团队完成任务的分配，明确团队每个人在接下来七天敏捷冲刺的目标其他参考文献这个作业所属团队 SuperNewCode团队成员 张楠 曾琳备 黄铭涛 张小宇 周广1.每日举行站立时会议2.燃尽图3.每…
阅读更多...
WordPress MasterStudy LMS插件 SQL注入漏洞复现(CVE-2024-1512)

WordPress MasterStudy LMS插件 SQL注入漏洞复现(CVE-2024-1512)

0x01 产品简介 WordPress和WordPress plugin都是WordPress基金会的产品。WordPress是一套使用PHP语言开发的博客平台。该平台支持在PHP和MySQL的服务器上架设个人博客网站。WordPress plugin是一个应用插件。 0x02 漏洞概述 WordPress Plugin MasterStudy LMS 3.2.5 版本及之…
阅读更多...
【北京迅为】《iTOP-3588开发板快速烧写手册》-第8章 TF启动

【北京迅为】《iTOP-3588开发板快速烧写手册》-第8章 TF启动

RK3588是一款低功耗、高性能的处理器&#xff0c;适用于基于arm的PC和Edge计算设备、个人移动互联网设备等数字多媒体应用&#xff0c;RK3588支持8K视频编解码&#xff0c;内置GPU可以完全兼容OpenGLES 1.1、2.0和3.2。RK3588引入了新一代完全基于硬件的最大4800万像素ISP&…
阅读更多...
vue案例

vue案例

任务清单（单文件） <!DOCTYPE html> <html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><title>模板</title><sc…
阅读更多...
【C++】滑动窗口：最大连续1的个数

【C++】滑动窗口：最大连续1的个数

1.题目 2.算法思路 其实在做这道题的时候并不需要真的把0翻转成1&#xff0c;只需要找到最长的子数组且该子数组中0的个数不大于K&#xff0c;就可以了&#xff01; 当然我们首先想到的是暴力穷举法&#xff1a; 找到所有符合题意的子数组&#xff0c;跳出最长的那个就可以了…
阅读更多...
s7netplus二次应用

s7netplus二次应用

1. 安装这是个基于S7协议的开源协议2. 引用 using S7.Net;3. 创建PLC对象internal class s7net_lib{//idenfy basic link paramsprivate string plc_ip;private CpuType plc_type;private short plc_rack, plc_slot;public Plc my_plc;//constructor，含参构造函数 public s7ne…
阅读更多...
MySQL-09.性能分析工具的使用

MySQL-09.性能分析工具的使用

1.数据库服务器的优化步骤当遇到数据库调优问题时，思考的流程如下图。 整个流程划分成了观察(Show status)和行动(Action)两个部分。字母S的部分代表观察(会使用相应的分析工具)，字母A代表的部分是行动(对应分析可以采取的行动)。上图，就是数据库调优的思路。如果发现执行SQ…
阅读更多...
JENKINS 安装，学习运维从这里开始

JENKINS 安装，学习运维从这里开始

Download and deployJenkins – an open source automation server which enables developers around the world to reliably build, test, and deploy their softwarehttps://www.jenkins.io/download/首先点击上面。下载Jenkins 为了学习&#xff0c;从windows开始&#x…
阅读更多...
Tkinter组件：Checkbutton

Tkinter组件：Checkbutton

Tkinter组件&#xff1a;Checkbutton Checkbutton&#xff08;多选按钮&#xff09;组件用于实现确定是否选择的按钮。Checkbutton 组件可以包含文本或图像&#xff0c;你可以将一个 Python 的函数或方法与之相关联&#xff0c;当按钮被按下时&#xff0c;对应的函数或方法将被…
阅读更多...
9种HTTP请求方法

9种HTTP请求方法

阅读更多...
英语学习笔记7——Are you a teacher?

英语学习笔记7——Are you a teacher?

Are you a teacher? 你是教师吗&#xff1f; 词汇 Vocabulary name /neɪm/ n. 名字&#xff0c;名声 英文名字构成&#xff1a; 名 字 姓 　　　　 given name family name 　也叫做&#xff1a;first name last name 　　　　 例&#xff1a;Yanyan Gao 例句&#xff1…
阅读更多...
3本TOP期刊上线！5月刊源表已更新！

3本TOP期刊上线！5月刊源表已更新！

本周投稿推荐 SSCI • 2/4区经管类&#xff0c;2.5-3.0&#xff08;录用率99%&#xff09; SCIE&#xff08;CCF推荐&#xff09; • 计算机类&#xff0c;2.0-3.0&#xff08;最快18天录用&#xff09; SCIE&#xff08;CCF-C类&#xff09; • IEEE旗下&#xff0c;1/2…
阅读更多...
获取系统时间

获取系统时间

获取当前系统时间，把时间转换为特定格式”yy年mm月dd日 星期x tt:mm:ss”，并每隔1s写入到本地磁盘中一个叫做log.txt的文本中，如果文本不存在则创建。 /*************************************************** file name:GetCurTime.c* author :momolyl@126.com* dat…
阅读更多...
Jetpack Compose三：主题和基础控件的使用

Jetpack Compose三：主题和基础控件的使用

设置主题 与Android View的主题定义方式不同&#xff0c;Jetpack Compose中的主题由许多较低级别的结构体和相关API组成&#xff0c;它们包括颜色、排版和形状属性。 Theme.kt控制工程的主题&#xff0c;它是一个可组合的Compose函数 最后主题函数ComposeStudyTheme的相关设置…
阅读更多...
推荐文章

Copyright @ 2022~2023