使用两个栈来实现队列

使用两个栈来实现队列

要求

问题描述：假设有两个长度相同的栈 S1，S2，已知以下入栈、出栈、判栈满和判栈空操作：

bool push(S, e);
bool pop(S, e);
bool isfull(S); 
bool isempty(S); 

现用这两个栈构成一个队列，实现入队列、出队列操作的算法：

bool EnQueue(Q, x);
int DeQueue(Q, x);

思路

这里两个栈，设为S1、S2，S1用来存储输入，S2用来存储输出。

输入元素时，当S2为空，S1满的时候，就可以把S1的内容出栈到S2中，但是只要S2中有元素，就不能把S1里面的内容输出到S2中。

输出元素时，S2中的元素出栈，如果S2中没有元素，那么需要把S1中的元素全部出栈到S2中，然后再从S2中出栈。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int stack_size=2;
const int increment=100;
const int inf=0x3f3f3f3f;
struct Sqstack 
{
	int *base;
	int *top;
	int size;
};
struct Queue
{
	Sqstack S1, S2;	
	//S1表示插入，S2表示输出 
};
bool init(Sqstack &S)
{
	S.base=(int*) malloc(stack_size*sizeof(int));
	if(S.base==NULL)
		return false;
	S.top=S.base;
	S.size=stack_size;
	return true;
}
bool isempty(Sqstack &S)
{
	if(S.base==S.top)
		return true;
	else return false;
}
bool isfull(Sqstack &S)
{
	if(S.top-S.base>=S.size)
		return true;
	else return false;
}
bool push(Sqstack &S, int e) //第二个元素是要进栈的元素 
{
	if(S.top-S.base >= S.size)//栈满 
		return false;
	*S.top=e;
	S.top++;
	return true;
}
bool pop(Sqstack &S, int &e) 
{
	if(S.top<=S.base)
		 return false; 
	S.top--;
	e=*S.top;
	return true;
}
bool clear(Sqstack &S)
{
	if(S.base!=NULL)
		free(S.base);
	S.base=NULL;
	S.top=NULL;
	return true;
}
bool enQueue(Queue &Q, int x)
{
	if(isfull(Q.S1)) //S1满 
	{
		if(!isempty(Q.S2)) //S2非空 
			return false;
		else 
		{
			int e;
			while(pop(Q.S1, e)) //把S1里面的所有内容放到S2中 
				push(Q.S2, e);
			push(Q.S1, x);//最后把需要进队的元素压到S1中 
		} 
	}
	else 
		push(Q.S1, x);
	return true;
}
bool deQueue(Queue &Q, int &x)
{
	if(isempty(Q.S2)) 
	{
		if(isempty(Q.S1))
			return false;
		else //S1不为空 
		{
			int e;
			while(pop(Q.S1, e)) //把S1里面的所有元素全部压到S2中 
				push(Q.S2, e);
			pop(Q.S2, x);
		}
	}
	else 
		pop(Q.S2, x);
	return true;
}
/*
	产生n个[min, max]的随机数。可能会有重复值。
*/
void initRandomize(int *arr, int n, int min, int max)
{
    int i = 0;
    srand(time(0));  			/*设置种子,并生成伪随机序列*/
    for (i = 0; i < n; ++i) {
        arr[i] = rand() % (max - min + 1) + min;  /*得到从[min, max]之间的随机数*/
        printf("%d ", arr[i]);
    }
    printf("

");
}
int main()
{
	int num[100];
	Queue Q;
	if(init(Q.S1) && init(Q.S2))
		cout<<"队列初始化成功
";
	else 
		cout<<"队列初始化失败
";
	cout<<"随机数如下:
";
	initRandomize(num, 15, 0, 100);
	int op, e;
	while(1)
	{
		cout<<endl;
		cout<<"1:元素进队列
";
		cout<<"2:元素出队列
";
		cout<<"0:退出
";
		cout<<"输出需要进行的操作:";
		cin>>op;
		if(op==0) break;
		else if(op==1)
		{
			cout<<"输入需要进队的元素:";
			cin>>e;
			if(!enQueue(Q, e))
				cout<<"队列已满,进队列失败
";
		}
		else if(op==2)
		{
			if(deQueue(Q, e))
				cout<<"出队列元素为:"<<e<<endl;
			else 
				cout<<"队列为空, 出队列失败
";	
		}
		else cout<<"输出代码错误
";
	}
	if(clear(Q.S1) && clear(Q.S2))
		cout<<"释放队列成功
";
	else 
		cout<<"释放队列失败
";
	return 0;
 }