用栈实现队列（图示超详解哦）

引言

在上一篇文章中，我们了解了用两个队列实现栈。在这篇问章中将继续介绍用两个栈实现队列的OJ练习：
用栈实现队列OJ链接

在本文中可能会需要借鉴到栈与队列的实现：
戳我看栈详解哦
戳我看队列详解哦

用栈实现队列

题目介绍

题目描述很简单：
通过两个栈实现队列存储数据的特点，即先进先出：

我们需要实现基本的队列操作：push、pop、top、empty、free：
void push(int x) 将元素 x 推到队列的末尾；
int pop() 从队列的开头移除并返回元素；
int peek() 返回队列开头的元素；
bool empty() 如果队列为空，返回 true ；否则，返回 false。

思路简述

与上一道题相同，这道题的难点同样在于结构：
如何实现pop时移除栈底的元素。由于栈是先进后出，所以栈底的元素是无法直接移除的。

我们就可以使用第二个栈，将栈中的元素依次取出，存入第二个栈中。由于栈是先进后出，所以当将一个栈中的元素依次取出，放进另一个栈中时，数据的顺序就会颠倒，这时在栈顶的元素就是最先入栈的元素，将这个元素移除即可；
也就是说，这个栈中栈顶的元素永远是最先入栈的元素，所以在这个栈中的元素没有全部移除之前，是不能在这个栈中再插入元素了，只能在原来的那个栈中插入；
我们发现，用两个栈来实现队列时，有一个栈只用于插入元素，有一个栈只用于移除元素，所以我们可以直接将前一个栈命名为push，后一个命名为pop；
如果pop栈为空，又需要移除元素时，才需要将push栈中的元素倒到pop栈中：

实现

栈的部分

在用两个栈实现队列之前，我们首先需要实现栈的接口。在需要用到栈的操作时直接复用即可。于栈的实现这里就不再赘述了，在前面的文章中已经详细的介绍过了。这里直接把前面实现过的栈的各种接口拷贝过来，包括用于定义队列的结构体：

typedef int STDataType;typedef struct Stack //表示栈
{STDataType* a;int top;int capacity;
}ST;//栈的部分
//初始化栈
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(10 * sizeof(STDataType));assert(ps);ps->capacity = 10;ps->top = 0;
}
//判断栈是否为空
bool STEmpty(ST* ps)
{assert(ps);if (ps->top){return 0;}else{return 1;}
}
//压栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* ptr = (STDataType*)realloc(ps->a, (ps->capacity + 10) * sizeof(STDataType));assert(ptr);ps->a = ptr;ps->capacity += 10;}ps->a[ps->top] = x;ps->top++;
}
//出栈
void STPop(ST* ps)
{assert(ps && STEmpty(ps) == 0);ps->top--;
}
//计算栈中元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//访问栈顶元素
STDataType STTop(ST* ps)
{assert(ps && STEmpty(ps) == 0);return ps->a[ps->top - 1];
}
//销毁栈
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->capacity = 0;ps->top = 0;ps->a = NULL;
}

队列的部分

有了栈的实现后，我们首先应该创建两个栈：pushst与popst，用于插入与移除元素。并将这两个栈存放到一个结构体中，方便管理：

typedef struct //表示实现队列的两个栈
{ST pushst;ST popst;
} MyQueue;

创建队列

创建队列时，可以直接为前面声明的用于存放两个栈的结构体类型MyQueue动态开辟一块空间，然后再分别复用STInit初始化其中的两个栈即可：

//创建队列
MyQueue* myQueueCreate()
{MyQueue* pmq = (MyQueue*)malloc(sizeof(MyQueue));assert(pmq);STInit(&pmq->pushst);STInit(&pmq->popst);return pmq;
}

判断队列是否为空

队列为空，即两个栈均为空。
所以我们直接复用判断栈是否为空函数STEmpty，当两个栈均为空，即两个函数的返回值均为真时，返回真，否则返回假：

//判断队列是否为空：若为空返回true，非空返回false
bool myQueueEmpty(MyQueue* obj) 
{assert(obj);if (STEmpty(&obj->pushst) && STEmpty(&obj->popst))//当两个队列全为空即全为非0才为空，返回1；{return true;}else{return false;}
}

在队列尾入

任何时候插入元素时，在pushst栈中插入即可：

//在队列尾入
void myQueuePush(MyQueue* obj, int x) 
{assert(obj);STPush(&obj->pushst, x);
}

在队列头出

在队列头出时，永远从popst的栈顶移除即可，移除栈顶的元素时，复用STPop函数即可；
但是当popst为空时，就需要将pushst栈中的元素全部依次移动到popst栈中，我们可以通过复用STPush与STTop函数，将pushst栈顶的元素插入到popst中，然后再STPop移除pushst栈顶的元素即可。然后再pop掉popst的栈顶元素：

//从队列头出
int myQueuePop(MyQueue* obj) 
{assert(obj && myQueueEmpty(obj) == 0);STDataType ret = 0;if (STEmpty(&obj->popst))//当pop栈为空时，才将push栈中的元素转移过去{while (STEmpty(&obj->pushst) == 0){STPush(&obj->popst, STTop(&obj->pushst));STPop(&obj->pushst);}}ret = STTop(&obj->popst);STPop(&obj->popst);return ret;
}

访问队头元素

访问队头元素时只需要复用STTop函数，访问popst栈顶的元素即可；
但是当popst栈为空时，就需要将pushst中的元素全部倒过去后再访问：

//返回队列开头的元素
int myQueuePeek(MyQueue* obj) 
{assert(obj && myQueueEmpty(obj) == 0);//当pop为空时，只能转移后访问它；pop非空时可以直接访问pop的栈顶元素if (STEmpty(&obj->popst)){while (STEmpty(&obj->pushst) == 0){STPush(&obj->popst, STTop(&obj->pushst));STPop(&obj->pushst);}}return STTop(&obj->popst);
}

释放队列

释放队列时，分别释放两个栈即可。
当然，动态开辟的MyQueue型结构体也需要被释放：

//释放队列
void myQueueFree(MyQueue* obj) 
{STDestroy(&obj->pushst);STDestroy(&obj->popst);free(obj);
}

总结

到此，关于用两个栈实现队列的题目就介绍完了，相信通过这两道题目，大家对于栈与队列的结构都有了更好的理解
下一篇文章中将会介绍循环队列的实现，欢迎大家持续关注哦

如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题，欢迎大家在评论区提出

如果本文对你有帮助，希望一键三连哦

希望与大家共同进步哦