用队列实现栈
题目解读
本题的要求是要用两个队列来实现一个先进后出的栈，并且要有以下功能：
1.将元素压入栈中
2.移除栈顶元素并且返回他
3.返回栈顶元素
4.判断栈是否为空
题目构思和代码实现
我们首先要做的就是将实现队列的代码导入该题（也可以自己写）
下面我们来进行题目的构思：
我们知道，栈的增加和删除元素都是从栈顶进行操作的，并且遵循先进后后出的原则，但是队列是遵循先进先出的规则，增加元素从队尾增加，删除元素从队首删除。
怎么解决呢？
其实题目已经给了我们提示：用两个队列！
我们可以这样，先构造两个队列，一个用来删除栈的元素，一个用来增加栈的元素。
所以我们就可以开辟两个队列，一个叫pop，一个叫push
typedef struct { Queue push; Queue pop; } MyStack; MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); if(obj==NULL) { return NULL; } QueueInit(&obj->push); QueueInit(&obj->pop); return obj; }
我们需要将元素压入栈中是就看哪一个队列不为空就压入到那个队列中
我们用之前队列写的判断队列 是否为空来增加代码的可读性
void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->push)) { QueuePush(&obj->push,x); } else { QueuePush(&obj->pop,x); } }
移除栈中的元素就要看情况了：
我们首先假设push队列为空，pop队列不为空，然后再用一个if语句进行判断，如果push不为空就交换
然后我们将不为空的那个队列里面的除了队尾元素的所有元素都统统放入为空的那个队列里面，知道不为空队列里面只剩下一个元素，先存储这个元素，然后就直接将他删除，最后返回这个元素
int myStackPop(MyStack* obj) { Queue* empty=&obj->push; Queue* nonempty=&obj->pop; if(!QueueEmpty(&obj->push)) { empty=&obj->pop; nonempty=&obj->push; } while(QueueSize(nonempty)>1) { QueuePush(empty,QueueFront(nonempty)); QueuePop(nonempty); } int top=QueueFront(nonempty); QueuePop(nonempty); return top; }
返回栈顶元素就直接返回非空队列的队尾元素即可
nt myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->push)) { return QueueBack(&obj->push); } else { return QueueBack(&obj->pop); } }
栈为空时两个队列都为空
bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->pop)&&QueueEmpty(&obj->push); }
完整代码如下：
typedef struct { Queue push; Queue pop; } MyStack; MyStack* myStackCreate() { MyStack* obj=(MyStack*)malloc(sizeof(MyStack)); if(obj==NULL) { return NULL; } QueueInit(&obj->push); QueueInit(&obj->pop); return obj; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->push)) { QueuePush(&obj->push,x); } else { QueuePush(&obj->pop,x); } } int myStackPop(MyStack* obj) { Queue* empty=&obj->push; Queue* nonempty=&obj->pop; if(!QueueEmpty(&obj->push)) { empty=&obj->pop; nonempty=&obj->push; } while(QueueSize(nonempty)>1) { QueuePush(empty,QueueFront(nonempty)); QueuePop(nonempty); } int top=QueueFront(nonempty); QueuePop(nonempty); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->push)) { return QueueBack(&obj->push); } else { return QueueBack(&obj->pop); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->pop)&&QueueEmpty(&obj->push); }
用栈实现队列
题目解读
题目的意思和上一题大同小异，要实现的功能都大差不差的，这里我就不做过多的解读，直接开始构思：
题目构思和代码实现
要想实现队列，我们用两个栈如何实现呢？
首先，栈时遵循先进后出的原则，但是队列时先进先出，难不成也像上一题一样，一个栈用来增加数据，另一个栈用来删除数据？
typedef struct { Stack pushstack; Stack popstack; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); if(obj==NULL) { perror("malloc"); return NULL; } StackInit(&obj->pushstack); StackInit(&obj->popstack); return obj; }
其实我们可以这样：
当你要增加元素，就将这个元素压入pushstack也就是专门存储增加队列的增加的元素的
删除元素时就有点麻烦咯
当需要删除时，我们要删除的是最先进入队列的元素，也就是pushstack的栈底元素，那么如何将他删除呢？
我们可以将pushstack的栈顶元素逐个压入到popstack中，然后删除掉pushstack中的栈底元素即可
这里题目中的查找队首元素也可以搭配使用，当pop栈为空时，队首元素就是push栈的栈底元素，pop栈不为空时，就是pop栈的栈顶元素
int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popstack)) { while(!StackEmpty(&obj->pushstack)) { StackPush(&obj->popstack,StackTop(&obj->pushstack)); StackPop(&obj->pushstack); } } return StackTop(&obj->popstack); }
增加和删除元素代码如下：
void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushstack,x); } int myQueuePop(MyQueue* obj) { int front=myQueuePeek(obj); StackPop(&obj->popstack); return front; }
队列的销毁要注意，free掉obj的同时要记得销毁两个栈：
void myQueueFree(MyQueue* obj) { StackDestroy(&obj->popstack); StackDestroy(&obj->pushstack); free(obj); }
完整代码如下：
typedef struct { Stack pushstack; Stack popstack; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); if(obj==NULL) { perror("malloc"); return NULL; } StackInit(&obj->pushstack); StackInit(&obj->popstack); return obj; } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->popstack)&&StackEmpty(&obj->pushstack); } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushstack,x); } int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popstack)) { while(!StackEmpty(&obj->pushstack)) { StackPush(&obj->popstack,StackTop(&obj->pushstack)); StackPop(&obj->pushstack); } } return StackTop(&obj->popstack); } int myQueuePop(MyQueue* obj) { int front=myQueuePeek(obj); StackPop(&obj->popstack); return front; } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->popstack); StackDestroy(&obj->pushstack); free(obj); }
好了，今天的分享到这里就结束了，谢谢大家的支持！
