首页 > 代码库 > 两个队列实现栈

两个队列实现栈

2024-07-13 05:46:03   237人阅读

原理：
假设有两个队列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的最后一个元素出队即可。

实现：

/**********************************
两个队列实现栈
by Rowandjj
2014/7/21
**********************************/
#include<iostream>
using namespace std;
typedef struct _NODE_
{
	int data;
	struct _NODE_ *next;
}Node,*pNode;
typedef struct _QUEUE_
{
	pNode pHead;
	pNode pTail;
	int size;
}Queue,*pQueue;
typedef struct _STACK_
{
	Queue q1;
	Queue q2;
}Stack,*pStack;
void InitQueue(pQueue pq)
{
	pq->pHead = pq->pTail = (pNode)malloc(sizeof(Node));
	if(!pq->pHead)
	{
		exit(-1);
	}
	pq->pHead->next = NULL;
	pq->size = 0;
}
void Enqueue(pQueue pq,int data)
{
	if(pq == NULL)
	{
		return;
	}
	pNode pNew = (pNode)malloc(sizeof(Node));
	if(!pNew)
	{
		exit(-1);
	}
	pNew->data = http://www.mamicode.com/data;>


联系
我们