用两个队列模拟一个栈

目录

大体思路：

代码实现：

运行结果：

栈和队列的问题在面试中经常会被问到，本篇文章教大家如何用两个对列模拟一个栈出来。

先来讲一下栈和队列的基本特点

栈：先进后出，只能在栈顶进行操作。

如：向栈内输入1，2，3，4，5，那么输出则为5，4，3，2，1。就好像一个电梯，先进去的人后出来，进和出都是在末尾操作。

队列：先进先出，队尾插入，队头删除。

如：向队内输入1，2，3，4，5，那么输出也为1，2，3，4，5。把入栈出栈比做出入电梯的话，入队出队更像是在排队，来的晚的人只能排在队伍的末尾。

大体思路：

第一步：定义两个队列，队列1和队列2。

让所有数据入队列1，这里举例为1，2，3，4，5。

此时队列1的内容为1，2，3，4，5，队列2为空。

第二步：让数据出队列1，入队列2，使队列1只留下一个数据。

此时队列1的内容为5，队列2的内容为1，2，3，4

然后让队列1的内容出队并打印，此时队列1为空。

第三步：让数据出队列2，入队列1，使队列2只留下一个数据

此时队列1的内容为1，2，3，队列2的内容为4

然后让队列2的内容出队并打印。此时队列2为空

第四步：循环步骤2和步骤3，直至两个队列都为空

代码实现：

#include <stdio.h>
#define N 6
typedef struct queue//定义一个队列
{
	int front;//队头下标
	int arr[N];
	int rear;//队尾下标

}Queue;
int main()
{
	Queue queue1,queue2;//定义队列1和队列2
	queue1.front=N-1;//初始化队列1的队头下标
	queue1.rear=N-1;//初始化队列1的队尾下标
	queue2.front=N-1;//初始化队列2的对头下标
	queue2.rear=N-1;//初始化队列2的队尾下标
	//rear==front时队列为空
	//1.将数据入队列1
	printf("请输入%d个数字\n",N-1);//循环队列需要空出一个元素的位置
	while(1)
	{
		queue1.rear=(queue1.rear+1)%N;
		scanf("%d",&queue1.arr[queue1.rear]);
		if((queue1.rear+1)%N==queue1.front)//队列为满停止入队
			break;
	}
	//4.循环步骤2，步骤3，直至两个队列都为空
	while(1)
	{
		//在两个循环前都加一个判断，两个队列都为空时就跳出循环
		if(queue1.front==queue1.rear&&queue2.front==queue2.rear)
			break;
		
		//2.让数据从队列1出队，入队列2，使队列1只留下一个数据
		while(1)
		{
			if((queue1.front+1)%N==queue1.rear)//此时队列1中只剩一个数据
			{
				queue1.front=(queue1.front+1)%N;//让队列1最后的那个数据出队
				printf("%d	",queue1.arr[queue1.front]);
				break;
			}
			queue1.front=(queue1.front+1)%N;
			queue2.rear=(queue2.rear+1)%N;
			queue2.arr[queue2.rear]=queue1.arr[queue1.front];//队列1出队入队列2
		}
		//此时队列2的内容为1，2，3，4，队列1为空

		//在两个循环前都加一个判断，两个队列都为空时就跳出循环
		if(queue1.front==queue1.rear&&queue2.front==queue2.rear)
			break;
		
		//3.让数据从队列2出队，入队列1，使队列2只留下一个数据
		while(1)
		{
			if((queue2.front+1)%N==queue2.rear)//此时队列2中只剩一个数据
			{
				queue2.front=(queue2.front+1)%N;//让队列2中最后的那个数据出队
				printf("%d	",queue2.arr[queue2.front]);
				break;
			}
			queue2.front=(queue2.front+1)%N;
			queue1.rear=(queue1.rear+1)%N;
			queue1.arr[queue1.rear]=queue2.arr[queue2.front];
		}
		//此时队列1的内容为1，2，3，队列2为空
	}
	printf("\n");
	return 0;
}

运行结果：

实现的方式可能有很多，这里只写了一个，如果文章有表述不清楚的地方欢迎大家指正