栈和队列的相互转换

• 栈：压栈和出栈都是再栈顶进行，所以栈遵守先进后出FILO。
• 队列：队头出队，队尾入队，队列遵守先进先出FIFO。

栈和队列的函数实现都相应的遵守本身数据结构的特点。

具体见(217条消息) C/C++【数据结构笔记】(栈和队列)_Answer-2296的博客-CSDN博客

所谓的栈和队列的相互转换就是，用栈的数据结构来实现队列数据的先进先出，用队列的数据结构来实现栈的先进后出。

用栈实现队列

• **保证最先入栈的数据在栈顶，最后入栈的数据压在栈底。**这样出栈就能模拟队列先进先出了（改变进栈）

为了保证这样的数据存放方式，我们会用两个栈来模拟实现队列。新元素入栈前，先将栈中的所有的数据压入辅助栈，再将新元素压入栈底，再将辅助栈的所有数据压会原来的栈中（同样的方式进出栈两次，栈中数据先后顺序不变）

完整代码实现：（实现前先引入栈的源代码！）具体见前面提及的博客。

void ImitateQueuePush(Stack* ps, STDataType data)
{
	Stack assit;
	StackInit(&assit);
	STDataType temp;//临时存放数据
	while (!StackEmpty(ps))//压入辅助栈
	{
		temp = StackTop(ps);
		StackPop(ps);
		StackPush(&assit, temp);
	}
	StackPush(ps, data);//新元素压入栈底
	while (!StackEmpty(&assit))//压回原栈
	{
		temp = StackTop(&assit);
		StackPop(&assit);
		StackPush(ps, temp);
	}
	StackDestory(&assit);
}

具体测试：

用队列实现栈

• 出队前将队尾前所有的结点逐个出队并入队，这样最终队尾元素就到了队头，这时出队的结点就是最后入队的结点，成功模拟栈的先进后出。（改变获取队头的方式）

完整代码实现：（实现前先引入队列的源代码！）

QDataType ImitateStackFront(Queue* qp)
{
	assert(qp);//判断是否是空指针
	assert(qp->tail);//判断是否是空队列
	QueueNode* last = qp->tail;//记录下最后一个结点
	QDataType temp;//临时存储结点
	do
	{
		temp = qp->head->data;
		QueuePop(qp);
		QueuePush(qp, temp);
	} while (qp->head != last);
	return qp->head->data;
}

具体测试：