【Leedcode】栈和队列必备的面试题（第四期）
【Leedcode】栈和队列必备的面试题（第四期）
文章目录
- 【Leedcode】栈和队列必备的面试题（第四期）
- 一、题目
- 二、思路+图解
- 1.声明结构体
- 2.循环链表开辟动态结构体空间
- 3.向循环队列插入一个元素
- 4.循环队列中删除一个元素
- 5. 从队首获取元素
- 6. 获取队尾元素
- 7.检查循环队列是否为空
- 8.检查循环队列是否已满
- 9.释放循环链表
- 三、可能遇到的问题
- 四、整体源代码
- 总结
一、题目
Leedcode链接
这几个接口使我们需要实现的我会一 一实现并讲解！
二、思路+图解
1.声明结构体
代码如下（示例）：
typedef struct {int *a;int front;int tail;int k;
} MyCircularQueue;
2.循环链表开辟动态结构体空间
代码如下（示例）：
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cp->a = (int*)malloc(sizeof(int)*(k+1));cp->front = cp->tail = 0;cp->k = k;return cp;
}
3.向循环队列插入一个元素
代码如下（示例）：
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->a[obj->tail] = value;obj->tail++;obj->tail %= (obj->k+1);return true;
}
4.循环队列中删除一个元素
直接++obj->front即可，要注意：front走的是循环链表，可以：obj->front %= (obj->k+1);
代码如下（示例）：
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->front++;obj->front %= (obj->k+1);return true;
}
5. 从队首获取元素
直接返回 obj->a[obj->front]，别忘了题目要求找不到返回 -1
代码如下（示例）：
int myCircularQueueFront(MyCircularQueue* obj) {//取首元素数据if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];
}
6. 获取队尾元素
代码如下（示例）：
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}if(obj->tail == 0){return obj->a[obj->k];}else{return obj->a[obj->tail-1];}
}
7.检查循环队列是否为空
剩下的几个接口相对来说很简单，直接上代码！
代码如下（示例）：
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{return obj->front == obj->tail;
}
8.检查循环队列是否已满
不论是判空还是判满，都要开 k+1 个空间，这是这道题的精髓!!!
代码如下（示例）：
bool myCircularQueueIsFull(MyCircularQueue* obj)
{return (obj->tail+1)%(obj->k+1) == obj->front;
}
9.释放循环链表
两次依次释放空间即可！
代码如下（示例）：
void myCircularQueueFree(MyCircularQueue* obj)
{free(obj->a);free(obj);
}
三、可能遇到的问题
此时我们提交代码，会出现以下问题！
这里表明我们在接口中定义的两个函数 myCircularQueueIsEmpty 和 myCircularQueueIsFull 需要声明一下！
四、整体源代码
代码如下（示例）：
//声明结构体
typedef struct {int *a;int front;int tail;int k;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {//开辟动态结构体空间，用指针p维护MyCircularQueue* cp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//一次性动态开辟好数组cp->a = (int*)malloc(sizeof(int)*(k+1));//初始化值cp->front = cp->tail = 0;cp->k = k;//函数要求返回指针 指针的类型是MyCircularQueuereturn cp;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//如果数组是满的返回 falseif(myCircularQueueIsFull(obj))//注意在这里调用了下面的自定义函数 所以要在前面提前声明函数{return false;}//如果数组没满来到这里 进行导入输入 并修改tail的值 obj->a[obj->tail] = value;obj->tail++;obj->tail %= (obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//注意在这里调用了下面的自定义函数 所以要在前面提前声明函数{return false;}obj->front++;obj->front %= (obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {//取首元素数据if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {//取尾元素数据if(myCircularQueueIsEmpty(obj)){//当数组为空 则返回-1return -1;}//数组不为空来到这 tail指向的地址的值肯定是空的 所以需要找tail后面的一个元素（tail-1）//但是由于是环形数组当tail是0下标的时候 0-1 = -1 可实际情况我们是要找数组的最后一个下标 数组最后一个下标不可能是-1//那么特殊情况 特殊对待做if else判断if(obj->tail == 0){return obj->a[obj->k];}else{return obj->a[obj->tail-1];}//其实下面还有一种运算方法 套用tail=0 我们可以发现 i就等于了数组最后一个元素的下标k //因为数组实质开辟空间是开辟的k+1个元素 那么k就是数组的尾元素下标//int i = (obj->tail+obj->k)%(obj->k+1);//return obj->a[i];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//判断数组是否为空return obj->front == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//判断数组是否为满return (obj->tail+1)%(obj->k+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);
*/
总结
以上就是今天要讲的内容，本文介绍了【Leedcode】中栈和队列必备的面试题（第四期）
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！
