两个队列实现一个栈 - JAVA

题目：用两个队列模拟一个栈，即用两个队列的出队和入队操作，来实现栈的出栈和入栈操作。

思路：稍微画下草图，便不难想出该题的解决方法，思路如下：

假设有两个队列Q1和Q2，当二者都为空时，入栈操作可以用入队操作来模拟，可以随便选一个空队列，假设选Q1进行入栈操作，现在假设a,b,c依次入栈了（即依次进入队列Q1），这时如果想模拟出栈操作，则需要将c出栈，因为在栈顶，这时候可以考虑用空队列Q2，将a，b依次从Q1中出队，而后进入队列Q2，将Q1的最后一个元素c出队即可，此时Q1变为了空队列，Q2中有两个元素，队头元素为a，队尾元素为b，接下来如果再执行入栈操作，则需要将元素进入到Q1和Q2中的非空队列，即进入Q2队列，出栈的话，就跟前面的一样，将Q2除最后一个元素外全部出队，并依次进入队列Q1，再将Q2的最后一个元素出队即可。

实现代码如下：

/*
用两个队列模拟入栈操作
*/
void push(PQUEUE pS1,PQUEUE pS2,int val)
{
	if(is_empty(pS2))
		en_queue(pS1, val);
	else
		en_queue(pS2, val);
}

/*
用两个队列模拟出栈操作
*/
bool pop(PQUEUE pS1,PQUEUE pS2,int *pData)
{
	if(is_empty(pS1) && is_empty(pS2))
		return false;

	int DelData;
	if(!is_empty(pS2))
	{
		int len = length(pS2);
		while(len-- > 1)
		{
			de_queue(pS2,&DelData);
			en_queue(pS1,DelData);
		}
		//将队列的最后一个元素出队，作为出栈元素
		de_queue(pS2,pData);
		return true;
	}
	if(!is_empty(pS1))
	{
		int len = length(pS1);
		while(len-- > 1)
		{
			de_queue(pS1,&DelData);
			en_queue(pS2,DelData);
		}
		//将队列的最后一个元素出队，作为出栈元素
		de_queue(pS1,pData);
		return true;
	}
}

完整的代码（用的以前写的链式队列）如下：

/*******************************************************************
题目：用两个队列模拟一个栈
*******************************************************************/

#include
  
   
#include
   
     typedef struct Node { int data; struct Node *pNext; }NODE,*PNODE; typedef struct Queue { PNODE front; //队头指针 PNODE rear; //队尾指针 }QUEUE,*PQUEUE; PQUEUE create_queue(); bool is_empty(PQUEUE); void en_queue(PQUEUE, int); bool de_queue(PQUEUE,int *); void destroy_queue(PQUEUE); void traverse_queue(PQUEUE); int length(PQUEUE); void push(PQUEUE,PQUEUE,int); bool pop(PQUEUE,PQUEUE,int *); int main() { int pData; //用来保存出队的元素值 //创建队列并进行入队测试 PQUEUE pS1 = create_queue(); PQUEUE pS2 = create_queue(); push(pS1,pS2,4); push(pS1,pS2,5); printf(the length of pS1: %d ,length(pS1)); printf(the length of pS2: %d ,length(pS2)); if(pop(pS1,pS2,&pData)) printf(%d is pop out ,pData); else printf(Stack is empty,can not pop ); printf(the length of pS1: %d ,length(pS1)); printf(the length of pS2: %d ,length(pS2)); push(pS1,pS2,6); printf(the length of pS1: %d ,length(pS1)); printf(the length of pS2: %d ,length(pS2)); push(pS1,pS2,7); printf(the length of pS1: %d ,length(pS1)); printf(the length of pS2: %d ,length(pS2)); if(pop(pS1,pS2,&pData)) printf(%d is pop out ,pData); else printf(Stack is empty,can not pop ); printf(the length of pS1: %d ,length(pS1)); printf(the length of pS2: %d ,length(pS2)); if(pop(pS1,pS2,&pData)) printf(%d is pop out ,pData); else printf(Stack is empty,can not pop ); printf(the length of pS1: %d ,length(pS1)); printf(the length of pS2: %d ,length(pS2)); if(pop(pS1,pS2,&pData)) printf(%d is pop out ,pData); else printf(Stack is empty,can not pop ); printf(the length of pS1: %d ,length(pS1)); printf(the length of pS2: %d ,length(pS2)); if(pop(pS1,pS2,&pData)) printf(%d is pop out ,pData); else printf(Stack is empty,can not pop ); return 0; } /* 创建一个空队列，队头指针和队尾指针都指向头结点， 头结点中不存放数据，只存放指针 */ PQUEUE create_queue() { PQUEUE pS = (PQUEUE)malloc(sizeof(Queue)); pS->front = (PNODE)malloc(sizeof(NODE)); if(!pS || !pS->front) { printf(pS or front malloc failed!!); exit(-1); } else { pS->rear = pS->front; pS->front->pNext = NULL; } return pS; } /* 判断队列是否为空 */ bool is_empty(PQUEUE pS) { if(pS->front == pS->rear) return true; else ret

两个队列实现一个栈(一)