前言：
本题目是关于栈和队列的OJ题目，需对栈和队列有一定了解再进行做题，若不了解可以根据我之前这篇文章进行学习：【数据结构】栈和队列-CSDN博客,题中需要的栈和队列的实现也在该文章中有源代码
目录
一.用队列实现栈
1.解题思路
栈和队列区别在于出数据时的不同，栈遵循“后入先出”，而队列遵循“先入先出”，但在入数据时并没有不同，因此在Push时只需要依照队列的Push即可，将数据进入一个队列。
而在出数据时就不能直接出该队列的数据了，因为此处是模拟栈，需要移除的是队列中的最后一位（最晚进）的数据，而队列只能对队首的数据进行出操作，那么此时第二个队列（此时为空）就有用处了，将第一个队列（有数据的队列）的队首数据插入到第二个队列中，再进行出队，直到第一个队列仅剩最后一个数据（这个数据就是出栈操作要移除的数据），移除该数据不进行插入到第二个队列，如此第一个队列为空，第二个队列就是进行出栈操作后的结果了。
下图大致能演示这个模拟出栈的过程
2.解题代码
队列的实现前言中有，这里不贴出来浪费篇幅了。明白了上图所示的思路，那么整道题就好解决了。关键在于将两个队列分为空队列和非空队列，入栈时与入队操作相同，直接对非空队列（都为空则默认一个）入队即可，出栈时进行两队列的数据交换，其余函数根据两队列性质来即可。
typedef struct {
Queue q1;
Queue q2;
} MyStack;
//初始化
MyStack* myStackCreate() {
MyStack* s = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&(s->q1));
QueueInit(&(s->q2));
return s;
}
//判断非空与否的条件就是两个队列是否都为空
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
//入栈，与入队是相同的操作，只需要向非空的队列入队即可
void myStackPush(MyStack* obj, int x) {
if(QueueEmpty(&obj->q1))
{
QueuePush(&obj->q2,x);
}
else
{
QueuePush(&obj->q1,x);
}
}
//出栈，找到非空队列和空队列进行转换
//注：返回值int是栈顶数据，也就是非空队列的队尾数据（移动后最后一个数据，同时也是队首）
int myStackPop(MyStack* obj) {
//找到空队列和非空队列
Queue* empty = &(obj->q1);
Queue* notempty = &(obj->q2);
if(QueueEmpty(&obj->q2))
{
empty = &obj->q2;
notempty = &obj->q1;
}
while(QueueSize(notempty)>1)
{
QueuePush(empty,QueueFront(notempty));
QueuePop(notempty);
}
int ret = QueueFront(notempty);
QueuePop(notempty);
return ret;
}
//栈顶数据就是非空队列的队尾数据
int myStackTop(MyStack* obj) {
if(QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q2);
}
else
{
return QueueBack(&obj->q1);
}
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
二.用栈实现队列
1.解题思路
与上道题同理，这次只是反了过来，用栈来实现队列，思路完全可以照搬，区别只在于用出栈模拟出队，不过有一点有差异，取出的栈顶元素（如图中4）插入到Stack2中顺序是相反的，因此需要来转换一下，这里我利用了数组下标进行转化的方法，具体实现方法在下文的方法一中。
不过这种方法比较麻烦，也不美观，破坏了封装性，不推荐。在这里给出另一个更为巧妙的方法，直接将两个Stack分为Pushst（插入）和Popst（删除）两个栈，分别对应插入删除，同样能实现。在需要 删除时将Pushst中的数据倒如Popst中即可。巧妙的点在于倒数据的过程中，恰巧使得顺序颠倒，而出栈正好就满足了出队的要求，就如下图所示，具体代码在下方法二。
2.解题代码
法一：
本方法与前一题的方法如出一辙，思路简单，但不推荐。
typedef struct {
ST s1;
ST s2;
} MyQueue;
//初始化
MyQueue* myQueueCreate() {
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&q->s1);
STInit(&q->s2);
return q;
}
//对非空栈进行入栈
void myQueuePush(MyQueue* obj, int x) {
if(STEmpty(&obj->s1))
{
STPush(&obj->s2,x);
}
else
{
STPush(&obj->s1,x);
}
}
//出栈
int myQueuePop(MyQueue* obj) {
//找出非空栈和空栈
ST* empty = &obj->s1;
ST* notempty = &obj->s2;
if(STEmpty(&obj->s2))
{
empty = &obj->s2;
notempty = &obj->s1;
}
//注意此处要用size保存，否则在后续循环内STPop时top变化会导致错误
int size = notempty->top;
//移入空栈（顺序是正确的）
for(int i = 1;i<size;i++)
{
STPush(empty,notempty->a[i]);
}
//得到返回的数据，并将原非空栈Pop为空
int ret = notempty->a[0];
for(int i = 0;i<size;i++)
{
STPop(notempty);
}
return ret;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->s1))
{
return obj->s2.a[0];
}
else
{
return obj->s1.a[0];
}
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->s1) && STEmpty(&obj->s2);
}
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->s1);
STDestroy(&obj->s2);
}法二：
推荐该方法，更为巧妙简单。
typedef struct {
ST Pushst;
ST Popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&q->Pushst);
STInit(&q->Popst);
return q;
}
//插入直接向Pushst插入即可
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->Pushst,x);
}
//取得队首数据，但位于栈底，需要倒数据到另一个栈
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->Popst))
{
//倒数据
while(!STEmpty(&obj->Pushst))
{
STPush(&obj->Popst,STTop(&obj->Pushst));
STPop(&obj->Pushst);
}
}
return STTop(&obj->Popst);
}
//需要取得队首，使用peek既可以倒数据，又能得到队首数据，一举两得
int myQueuePop(MyQueue* obj) {
int ret = myQueuePeek(obj);
STPop(&obj->Popst);
return ret;
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->Pushst) && STEmpty(&obj->Popst);
}
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->Pushst);
STDestroy(&obj->Popst);
}两种方法均能通过该题的全部样例。
