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 - 创建MyQueuemyQueuePush - 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的数据//定义MyQueuetypedef 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; pmq->st1 = (ST*)calloc(1, sizeof(ST)); pmq->st2 = (ST*)calloc(1, sizeof(ST)); STInit(pmq->st1); STInit(pmq->st2); return pmq;所以 myQueueCreate 函数就长这样
//创建MyQueueMyQueue* 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); }int ret = STTop(obj->st2);STPop(obj->st2); 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); }int ret = STTop(obj->st2); 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)--;}}//----------------------------------------------------------------------------------------------------//定义MyQueuetypedef struct { ST* st1; ST* st2;} MyQueue;//创建MyQueueMyQueue* 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)--;}}//----------------------------------------------------------------------------------------------------//定义MyQueuetypedef struct { ST* st1; ST* st2;} MyQueue;//创建MyQueueMyQueue* 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< !!!
放个卡密在这,感谢各位能看到这儿啦!
