【LeetCode例232】【C语言】用栈实现队列~动画超详细解读!
0 技术需求
了解并实现栈和队列,熟悉栈和队列的基本逻辑
这里挂上链接
1 题目介绍
1.1 看题
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作**（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。
这里挂上题目链接: 232.用栈实现队列
1.2 分析
这道题目其实就是让我们用栈的基本功能以及函数实现队列的基本功能及函数
- myQueueCreate - 创建MyQueue
- myQueuePush - MyQueue入队
- myQueuePop - MyQueue出队
- myQueuePeek - MyQueue取队头
- myQueueEmpty - MyQueue判空
- myQueueFree - myQueue释放
比较重要的一点就是我们使用C实现,所以我们需要先手搓一遍栈的函数才能写这道题(当然完全理解过栈和队列的话CV一下也不是不行(doge))
2 解题思路
2.1 基本思想
我们都知道,如果给一串数据,全部入栈之后再出栈,出栈的数据的顺序会反过来,而题目要求我们使用两个栈实现队列,我们就可以利用上进栈再出栈会逆置的特性
2.2 实现思路1(非最优解)
2.2.1 定义MyQueue
这里我们在 MyQueue 结构体里定义两个分别指向 栈st1 和 栈st2 的指针
- st1: 用于先存放入"队列"的数据
- st2: 用于逆置st1的数据
//定义MyQueue typedef struct { ST* st1; ST* st2; } MyQueue;2.2.2 myQueue的初始化
- 题目要求在函数内部创建 MyQueue ,所以我们只能把内存开辟在堆区上才能把空间保留下来,如果放在栈区上,函数一结束 MyQueue 就被自动销毁了( st1 和 st2 都是指针,开辟完别忘了初始化,虽然这里用的 calloc 但还是自己再初始化一遍保险保险)
MyQueue* pmq = (MyQueue*)calloc(1, sizeof(MyQueue)); pmq->st1 = NULL; pmq->st2 = NULL;
- 既然 st1 和 st2 都是指针,所以也需要初始化一下这俩栈,直接调用现成的函数就行
pmq->st1 = (ST*)calloc(1, sizeof(ST)); pmq->st2 = (ST*)calloc(1, sizeof(ST)); STInit(pmq->st1); STInit(pmq->st2);- 别忘了返回创建的MyQueue
return pmq;
所以 myQueueCreate 函数就长这样
//创建MyQueue MyQueue* myQueueCreate() { MyQueue* pmq = (MyQueue*)calloc(1, sizeof(MyQueue)); pmq->st1 = NULL; pmq->st2 = NULL; pmq->st1 = (ST*)calloc(1, sizeof(ST)); pmq->st2 = (ST*)calloc(1, sizeof(ST)); STInit(pmq->st1); STInit(pmq->st2); return pmq; }2.2.3 myQueue 的入"队列"
- 我们说 st1 只负责接收入"队列",要出"队列"再通过 st2 逆置一下,所以我们直接把数据无脑放进 st1 就行
//MyQueue入队 void myQueuePush(MyQueue* obj, int x) { STPush(obj->st1, x); }2.2.4 myQueue 的出"队列"
- 我们知道出队列需要把 st1 的所有数据再入一遍 栈st2 把整个数据逆序一遍才能"出队"一个数据,所以这里只要 st1 不是空,我们就不断往 st2 输出数据
while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); }- 因为题目要求要有返回值,此时 栈st2 的栈顶作为出"队列"的"队头",我们把"队头"的值暂时存到 ret 里,方便返回其值
int ret = STTop(obj->st2);
- 然后让 st2 出栈一个值,也就是栈顶那个值,即"出队"一次
STPop(obj->st2);
- 最后把 st2 剩余的值重新放回 st1 中暂存,并返回 ret
while(!STEmpty(obj->st2)) { STPush(obj->st1, STTop(obj->st2)); STPop(obj->st2); } return ret;那么这就是 MyQueue 的一次完整的"出队"了
//MyQueue出队 int myQueuePop(MyQueue* obj) { while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); } int ret = STTop(obj->st2); STPop(obj->st2); while(!STEmpty(obj->st2)) { STPush(obj->st1, STTop(obj->st2)); STPop(obj->st2); } return ret; }2.2.5 MyQueue取队头
-
"取队头"的步骤其实和"出队"差不多,只是中间少了一步让 st2 栈顶出栈的内容,也就导致我只是取了 st2栈顶 的值而已, 取完值之后 st2 里的内容全都原封不动地还给 st1 了
-
一样的把 st1 的所有值入一遍 st2
while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); }- 一样的把"队头"的值给临时变量 ret
int ret = STTop(obj->st2);
- 最后又是一样的把 st2 的所有值还给 st1 并且返回 ret
while(!STEmpty(obj->st2)) { STPush(obj->st1, STTop(obj->st2)); STPop(obj->st2); } return ret;以下是MyQueue取队头的完整代码
//MyQueue取队头 int myQueuePeek(MyQueue* obj) { while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); } int ret = STTop(obj->st2); while(!STEmpty(obj->st2)) { STPush(obj->st1, STTop(obj->st2)); STPop(obj->st2); } return ret; }2.2.6 MyQueue判空
- 我们所有的数据全部存在 st1 里,除了需要逆置的时候, st2 里头一般都是没有任何内容的,所以我们只需要单纯的给 st1 判空就行了
//MyQueue判空 bool myQueueEmpty(MyQueue* obj) { return STEmpty(obj->st1); }2.2.7 MyQueue的销毁
- 这里我们需先把 st1 和 st2 先销毁,再销毁 MyQueue(obj) 的空间,如果先销毁 MyQueue 的话,我们就找不到 st1 和 st2 了,也就销毁不了这俩栈了
//MyQueue释放 void myQueueFree(MyQueue* obj) { STDestroy(obj->st1); STDestroy(obj->st2); obj->st1 = NULL; obj->st2 = NULL; free(obj); }2.2.8 完整动画
2.3 实现思路2(最优解)
- 区别于思路1,思路2不需要频繁让数据在 st1 和 st2 之间来回跳
- 一样的让 st1 专注"入队", st2 专注"出队",区别在于要等 st2 "出队"完才向其补充数据
- 其他的函数就如法炮制就行了,这里着重讲取"队头"和"出队"
2.3.1 MyQueue取队头
- 这里取完队头之后不把 st2 的数据挪回 st1 里,方便下次挪动或者删除
//MyQueue取队头 int myQueuePeek(MyQueue* obj) { if(STEmpty(obj->st2))//判断 st2 有没有数据,有数据就不动,没数据就把 st1 的数据挪过来 { while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); } } int ret = STTop(obj->st2); return ret; }2.3.2 MyQueue出队
- 同样的,出队之后不把 st2 的数据挪回 st1 里
- 注意:这里动画先执行了三次出队,然后执行了一次入队,最后执行了三次出队
//MyQueue出队 int myQueuePop(MyQueue* obj) { if(STEmpty(obj->st2))//判断 st2 有没有数据,有数据就不动,没数据就把 st1 的数据挪过来 { while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); } } int ret = STTop(obj->st2); STPop(obj->st2); return ret; }2.3.3 完整动画
3 完整实现代码
因为这里是用C写这道题,所以代码前面一定得加上栈的所有内容哦
3.1 方法1
//类型定义 typedef int DataType; typedef struct stack { DataType* pdata; int top; int capa; }ST; //函数定义 //栈的扩容 void CheckCapa(ST* pst); //获取栈顶数据 DataType STTop(ST* pst); //栈的判空 bool STEmpty(ST* pst); //查看数据量 int STSize(ST* pst); //栈的初始化 void STInit(ST* pst); //栈的删除 void STDestroy(ST* pst); //压栈 void STPush(ST* pst, DataType data); //出栈 void STPop(ST* pst); //函数定义 //栈的扩容 void CheckCapa(ST* pst) { assert(pst); if (pst->top + 1 == pst->capa) { DataType* tmp = (DataType*)realloc(pst->pdata, 2 * pst->capa * sizeof(DataType)); if (tmp == NULL) { perror("CheckCapa::realloc"); exit(1); } else { pst->pdata = tmp; } pst->capa = 2 * pst->capa; } } //获取栈顶数据 DataType STTop(ST* pst) { assert(pst); return pst->pdata[pst->top]; } //栈的判空 bool STEmpty(ST* pst) { assert(pst); return pst->top + 1 == 0; } //查看数据量 int STSize(ST* pst) { assert(pst); return pst->top + 1; } //栈的初始化 void STInit(ST* pst) { assert(pst); pst->pdata = (DataType*)calloc(4, sizeof(DataType)); if (pst->pdata == NULL) { perror("STInit::calloc"); exit(1); } pst->top = -1; pst->capa = 4; } //栈的删除 void STDestroy(ST* pst) { free(pst->pdata); pst->pdata = NULL; pst->capa = 0; pst->top = -1; } //压栈 void STPush(ST* pst, DataType data) { CheckCapa(pst); (pst->top)++; pst->pdata[pst->top] = data; } //出栈 void STPop(ST* pst) { if (STEmpty(pst)) { return; } else { (pst->top)--; } } //---------------------------------------------------------------------------------------------------- //定义MyQueue typedef struct { ST* st1; ST* st2; } MyQueue; //创建MyQueue MyQueue* myQueueCreate() { MyQueue* pmq = (MyQueue*)calloc(1, sizeof(MyQueue)); pmq->st1 = NULL; pmq->st2 = NULL; pmq->st1 = (ST*)calloc(1, sizeof(ST)); pmq->st2 = (ST*)calloc(1, sizeof(ST)); STInit(pmq->st1); STInit(pmq->st2); return pmq; } //MyQueue入队 void myQueuePush(MyQueue* obj, int x) { STPush(obj->st1, x); } //MyQueue出队 int myQueuePop(MyQueue* obj) { while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); } int ret = STTop(obj->st2); STPop(obj->st2); while(!STEmpty(obj->st2)) { STPush(obj->st1, STTop(obj->st2)); STPop(obj->st2); } return ret; } //MyQueue取队头 int myQueuePeek(MyQueue* obj) { while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); } int ret = STTop(obj->st2); while(!STEmpty(obj->st2)) { STPush(obj->st1, STTop(obj->st2)); STPop(obj->st2); } return ret; } //MyQueue判空 bool myQueueEmpty(MyQueue* obj) { return STEmpty(obj->st1); } //MyQueue释放 void myQueueFree(MyQueue* obj) { STDestroy(obj->st1); STDestroy(obj->st2); obj->st1 = NULL; obj->st2 = NULL; free(obj); }3.1 方法2
typedef int DataType; typedef struct stack { DataType* pdata; int top; int capa; }ST; //函数定义 //栈的扩容 void CheckCapa(ST* pst); //获取栈顶数据 DataType STTop(ST* pst); //栈的判空 bool STEmpty(ST* pst); //查看数据量 int STSize(ST* pst); //栈的初始化 void STInit(ST* pst); //栈的删除 void STDestroy(ST* pst); //压栈 void STPush(ST* pst, DataType data); //出栈 void STPop(ST* pst); //函数定义 //栈的扩容 void CheckCapa(ST* pst) { assert(pst); if (pst->top + 1 == pst->capa) { DataType* tmp = (DataType*)realloc(pst->pdata, 2 * pst->capa * sizeof(DataType)); if (tmp == NULL) { perror("CheckCapa::realloc"); exit(1); } else { pst->pdata = tmp; } pst->capa = 2 * pst->capa; } } //获取栈顶数据 DataType STTop(ST* pst) { assert(pst); return pst->pdata[pst->top]; } //栈的判空 bool STEmpty(ST* pst) { assert(pst); return pst->top + 1 == 0; } //查看数据量 int STSize(ST* pst) { assert(pst); return pst->top + 1; } //栈的初始化 void STInit(ST* pst) { assert(pst); pst->pdata = (DataType*)calloc(4, sizeof(DataType)); if (pst->pdata == NULL) { perror("STInit::calloc"); exit(1); } pst->top = -1; pst->capa = 4; } //栈的删除 void STDestroy(ST* pst) { free(pst->pdata); pst->pdata = NULL; pst->capa = 0; pst->top = -1; } //压栈 void STPush(ST* pst, DataType data) { CheckCapa(pst); (pst->top)++; pst->pdata[pst->top] = data; } //出栈 void STPop(ST* pst) { if (STEmpty(pst)) { return; } else { (pst->top)--; } } //---------------------------------------------------------------------------------------------------- //定义MyQueue typedef struct { ST* st1; ST* st2; } MyQueue; //创建MyQueue MyQueue* myQueueCreate() { MyQueue* pmq = (MyQueue*)calloc(1, sizeof(MyQueue)); pmq->st1 = NULL; pmq->st2 = NULL; pmq->st1 = (ST*)calloc(1, sizeof(ST)); pmq->st2 = (ST*)calloc(1, sizeof(ST)); STInit(pmq->st1); STInit(pmq->st2); return pmq; } //MyQueue入队 void myQueuePush(MyQueue* obj, int x) { STPush(obj->st1, x); } //MyQueue出队 int myQueuePop(MyQueue* obj) { if(STEmpty(obj->st2)) { while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); } } int ret = STTop(obj->st2); STPop(obj->st2); return ret; } //MyQueue取队头 int myQueuePeek(MyQueue* obj) { if(STEmpty(obj->st2)) { while(!STEmpty(obj->st1)) { STPush(obj->st2, STTop(obj->st1)); STPop(obj->st1); } } int ret = STTop(obj->st2); return ret; } //MyQueue判空 bool myQueueEmpty(MyQueue* obj) { return (STEmpty(obj->st1) && STEmpty(obj->st2)); } //MyQueue释放 void myQueueFree(MyQueue* obj) { STDestroy(obj->st1); STDestroy(obj->st2); obj->st1 = NULL; obj->st2 = NULL; free(obj); }佬!都看到这了,如果觉得有帮助的话一定要点赞啊佬 >v
放个卡密在这,感谢各位能看到这儿啦!
- 注意:这里动画先执行了三次出队,然后执行了一次入队,最后执行了三次出队
- 同样的,出队之后不把 st2 的数据挪回 st1 里
- 这里取完队头之后不把 st2 的数据挪回 st1 里,方便下次挪动或者删除
- 这里我们需先把 st1 和 st2 先销毁,再销毁 MyQueue(obj) 的空间,如果先销毁 MyQueue 的话,我们就找不到 st1 和 st2 了,也就销毁不了这俩栈了
- 我们所有的数据全部存在 st1 里,除了需要逆置的时候, st2 里头一般都是没有任何内容的,所以我们只需要单纯的给 st1 判空就行了
- 最后又是一样的把 st2 的所有值还给 st1 并且返回 ret
- 一样的把"队头"的值给临时变量 ret
-
- 最后把 st2 剩余的值重新放回 st1 中暂存,并返回 ret
- 然后让 st2 出栈一个值,也就是栈顶那个值,即"出队"一次
- 因为题目要求要有返回值,此时 栈st2 的栈顶作为出"队列"的"队头",我们把"队头"的值暂时存到 ret 里,方便返回其值
- 我们知道出队列需要把 st1 的所有数据再入一遍 栈st2 把整个数据逆序一遍才能"出队"一个数据,所以这里只要 st1 不是空,我们就不断往 st2 输出数据
- 我们说 st1 只负责接收入"队列",要出"队列"再通过 st2 逆置一下,所以我们直接把数据无脑放进 st1 就行
- 别忘了返回创建的MyQueue
- 既然 st1 和 st2 都是指针,所以也需要初始化一下这俩栈,直接调用现成的函数就行
- 题目要求在函数内部创建 MyQueue ,所以我们只能把内存开辟在堆区上才能把空间保留下来,如果放在栈区上,函数一结束 MyQueue 就被自动销毁了( st1 和 st2 都是指针,开辟完别忘了初始化,虽然这里用的 calloc 但还是自己再初始化一遍保险保险)
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
