第2章第2节练习题2 使用栈模拟队列操作
最后更新于：2022-04-01 19:51:45
## 问题描述
利用两个栈S1，S2来模拟一个队列，已知栈的4的运算定义如下：
Push(S,x); 元素x入栈S
Pop(S,x); S出栈并将出栈的值赋给x
StackEmpty(S); 判断栈是否为空
StackOverflow(S); 判断栈是否满
Enqueue; 将元素x入队
Dequeue; 出队，并将出队元素存储在x中
QueueEmpty; 判断队列是否为空
那么如何利用栈的运算实现该队列的3个运算？
## 算法思想
由于栈先进后出的特性，使用两个栈便可完成两次先进先出的过程，即相当于先进先出。
我们设置两个栈S1，S2。
对S2的出栈操作用作出队，若S2为空，则现将S1中所有元素送入S2；
对S1的入栈操作用作入队，若S1为满，必须先保证S2为空，才能将S1中的元素全部插入S2中；
## 算法描述
~~~
//入队
int EnQueue(SqStack *S1,SqStack *S2,ElemType x)
{
if(StackOverflow(S1)!=0){
Push(S1,x);
return 0;
}
if(StackOverflow(S1)==0&&StackEmpty(S2)!=0){
printf("The Queue is full!\n");
return -1;
}
if(StackOverflow(S1)==0&&StackEmpty(S2)==0){
while(StackEmpty(S1)!=0){
Pop(S1,&x);
Push(S2,x);
}
return 0;
}
return -1;
}
//出队
int DeQueue(SqStack *S1,SqStack *S2, ElemType* x)
{
if(StackEmpty(S2)!=0){
Pop(S2,x);
}else if(StackEmpty(S1)==0){
printf("The queue is empty!\n");
return -1;
}else{
while(StackEmpty(S1)!=0){
Pop(S1,x);
Push(S2,*x);
}
Pop(S2,x);
}
return 0;
}
//判断队列是否为空
int QueueEmpty(SqStack *S1, SqStack *S2)
{
if(StackEmpty(S1)==0&&StackEmpty(S2)==0){
printf("The Queue is empty!\n");
return 0;
}else{
return -1;
}
}
~~~
具体代码见附件。
~~~
#include
#include
#define MaxSize 10
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack*);
void Push(SqStack*, ElemType);
void Pop(SqStack*, ElemType*);
int StackEmpty(SqStack*);
int StackOverflow(SqStack*);
void Print(SqStack*);
int EnQueue(SqStack*,SqStack*,ElemType);
int DeQueue(SqStack*,SqStack*,ElemType*);
int QueueEmpty(SqStack*, SqStack*);
int main(int argc,char* argv[])
{
SqStack S1;
SqStack S2;
InitStack(&S1);
InitStack(&S2);
for(int i=0;i<10;i++){
EnQueue(&S1,&S2,i);
}
ElemType x;
DeQueue(&S1,&S2,&x);
printf("%4d\n",x);
DeQueue(&S1,&S2,&x);
printf("%4d\n",x);
DeQueue(&S1,&S2,&x);
printf("%4d\n",x);
return 0;
}
//入队
int EnQueue(SqStack *S1,SqStack *S2,ElemType x)
{
if(StackOverflow(S1)!=0){
Push(S1,x);
return 0;
}
if(StackOverflow(S1)==0&&StackEmpty(S2)!=0){
printf("The Queue is full!\n");
return -1;
}
if(StackOverflow(S1)==0&&StackEmpty(S2)==0){
while(StackEmpty(S1)!=0){
Pop(S1,&x);
Push(S2,x);
}
return 0;
}
return -1;
}
//出队
int DeQueue(SqStack *S1,SqStack *S2, ElemType* x)
{
if(StackEmpty(S2)!=0){
Pop(S2,x);
}else if(StackEmpty(S1)==0){
printf("The queue is empty!\n");
return -1;
}else{
while(StackEmpty(S1)!=0){
Pop(S1,x);
Push(S2,*x);
}
Pop(S2,x);
}
return 0;
}
//判断队列是否为空
int QueueEmpty(SqStack *S1, SqStack *S2)
{
if(StackEmpty(S1)==0&&StackEmpty(S2)==0){
printf("The Queue is empty!\n");
return 0;
}else{
return -1;
}
}
/*--------------------------------------------*/
//初始化栈
void InitStack(SqStack *S)
{
S->top=-1;
}
//入栈
void Push(SqStack *S, ElemType x)
{
if(S->top==MaxSize-1){
printf("The Stack is full!\n");
return;
}
S->data[++S->top]=x;
}
//出栈
void Pop(SqStack *S, ElemType *x)
{
if(S->top==-1){
printf("The Stack is empty!\n");
return;
}
*x=S->data[S->top--];
}
//判断栈是否为空
int StackEmpty(SqStack *S)
{
if(S->top==-1){
return 0;
}
return -1;
}
//判断栈是否已满
int StackOverflow(SqStack *S)
{
if(S->top==MaxSize-1){
return 0;
}
return -1;
}
//打印栈中所有元素
void Print(SqStack *S)
{
int i=S->top;
while(i!=-1){
printf("%4d",S->data[i]);
i--;
}
printf("\n");
}
~~~
';