【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. 获取队尾元素

![在这里插入图片描述](https://img-blog.csdnimg.cn/2ae4e685ecae47c3aacbd8cbc565b768.pn

代码如下（示例）：

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】中栈和队列必备的面试题（第四期）
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！