目錄

大體思路：

代碼實現：

運行結果：

棧和隊列的問題在面試中經常會被問到，本篇文章教大家如何用兩個對列模擬一個棧出來。

先來講一下棧和隊列的基本特點

棧：先進后出，只能在棧頂進行操作。

如：向棧內輸入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;
}

運行結果：

實現的方式可能有很多，這里只寫了一個，如果文章有表述不清楚的地方歡迎大家指正

?