利用两个栈S1和S2模拟一个队列，写出入队和出队的算法，可用栈的基本操作

Question

请尽快回答哦 就是用数据结构的知识 要是C++的 谢拉 答得好的话还可以加分啊

Answer 1

// s1是容量为n的栈，栈中元素类型是elemtp。本函数将x入栈，若入栈成功返回1，否则返回0。
int enqueue( stack s1, elemtp x )
{
if( top1==n && !Sempty(s2) ) // top1是栈s1的栈顶指针，是全局变量
{
// s1满、s2非空，这时s1不能再入栈
printf(“栈满”);
return(0);
}
if( top1==n && Sempty(s2) ) // 若s2为空，先将s1退栈,元素再压栈到s2
{
while( !Sempty(s1) )
POP( s1, x );
PUSH( s2, x );
}
PUSH( s1, x ); // x入栈，实现了队列元素的入队
return(1);
}

// s2是输出栈，本函数将s2栈顶元素退栈，实现队列元素的出队
void dequeue( stack s2, stack s1 )
{
if( !Sempty(s2) ) // 栈s2不空，则直接出队
{
POP( s2, x );
printf( “出队元素为”, x );
}
else if( Sempty(s1) ) // 处理s2空栈。若输入栈也为空，则判定队空
{
printf(“队列空”);
exit(0);
}
else // 先将栈s1倒入s2中，再作出队操作
{
while( !Sempty(s1) )
{
POP( s1, x );
PUSH( s2, x );
}
POP( s2, x ); // s2退栈相当队列出队
printf( “出队元素为”, x );
}
}

// 本函数判用栈s1和s2模拟的队列是否为空
int queue_empty()
{
if( Sempty(s1) && Sempty(s2) ) // 队列空
return(1);
else
return(0); //队列不空。
}

#include <stdlib.h>
#include <stdio.h>

typedef struct
{
char *base;
char *top;
int stack_size;
}stack;

void init_stack(stack *s)
{
s->base=(char *)malloc(50*sizeof(char));
if(!s->base)return;

s->top=s->base;
s->stack_size=50;
}

void push(stack *s,char e)
{
if(s->top-s->base>=s->stack_size)
{
s->base=(char *)realloc(s->base,(s->stack_size+50)*sizeof(char));
if(!s->base)return;
s->top=s->base+s->stack_size;
s->stack_size+=50;
}

*(s->top)=e;
s->top++;

}

void pop(stack *s,char *e)
{
s->top--;
*e=*(s->top);

}
int stack_empty(stack *s)
{
if(s->top==s->base)return 1;
return 0;
}
int queue_empty(stack *s1,stack *s2)
{
if(stack_empty(s1)&&stack_empty(s2))return 1;
return 0;
}
void dequeue(stack *s1,stack *s2,char *a) /*s1负责入队，s2负责出队*/
{ /*出队之前 */
char e; /*先把s1倒灌到s2里面*/
if(!queue_empty(s1,s2)) /*这样把最先入队的暴露在最外面*/
{
while(!stack_empty(s1))
{
pop(s1,&e);
push(s2,e);
}
pop(s2,a);
}
}

void enqueue(stack *s1,stack *s2,char a)
{
char e;
while(!stack_empty(s2))
{
pop(s2,&e);
push(s1,e);
}
push(s1,a);
}

main()
{
char e,*a="good good study day day up";
int i=0;
stack s1,s2;
init_stack(&s1);
init_stack(&s2);

while(a[i])
{
enqueue(&s1,&s2,a[i]);
i++;
}
while(!queue_empty(&s1,&s2))
{
dequeue(&s1,&s2,&e);
printf("%c",e);
}

getch();
}

Answer 2

使用两个栈，分别依元素加入的顺序和其反序保存元素，在适当的时机将元素在两个栈中进行转移，从而模拟队列的操作。
令s1中元素的顺序为自底向上与元素添加顺序一致，s2与其相反，则：
加入队列时，若s2不空，则将s2中的元素依次出栈，每出栈一个向s1中入栈一个；将入队元素入s1栈；
从队列中取出时，若s1不空，则将s1中元素依次出栈，每出栈一个向s2中入栈一个；从s2栈顶出栈一个即队列中取出的元素。
用伪代码描述如下：
enqueue(elem)
while(!s2.empty())
temp
=
s2.pop();
s1.push(temp);
s1.push(elem);
dequeue()
while(!s1.empty())
temp
=
s1.pop();
s2.push(temp);
return
s2.pop();

Answer 3

S1做入队栈，S2做出对栈
入队 x
if S1 is empty S2==>S1
然后
S1->push(x)
出队
if S2 is empty S1==>S2
然后
S2->pop本回答被提问者采纳

Answer 4

入队:
while(!S2.empty())
{
S1.push(S2.top());
S2.pop();
}
S1.push(c);//C是入队数据
出队
while(!S1.empty())
{
S2.push(S1.top());
S1.pop();
}
c = S2.top();
S2.pop();