摘要：
双堆栈模拟队列的基本思想：队列是先进先出的，堆栈是先进先出来的。使用输入堆栈存储团队元素，使用输出堆栈反转输出堆栈中的元素，然后退出堆栈。注意：队列已满的条件是输入堆栈S1已满，而输出堆栈S2不为空#include#include #definemaxsize30typedefint数据类型；typedefstruct｛datatypedata[maxsize]；inttop；｝SeqStack；voidInitial｛S-˃top=-1；｝intStackIsFull｛returnS-˃top==maxsize-1；｝intStackIsEmpty｛returnS-˃top==-1；｝intStackPop｛intk；ifreturn0；k=S-˃数据[S-˃top--˃；returnk；｝intStackPush｛ifretrn0；S-˃data[++S-˃top]=x；return1；}//判断团队是否为空intQueueIsEmpty｛returnStackIsEmpty&&StackIsEmpty；｝//在队列intEnQueue中｛if｛if（！QueueIsEmpty）｛intk；k＝DeQueue；printf；｝｝main（）｛SeqStack*S1=malloc；SeqStack*S2=malloc；IminateQueue；｝铁路车辆调度问题调车场两侧铁路均为单行道，中间有一段“栈道”用于调度，调车场入口处有硬座车和软座车。设计了一种算法，将所有软座汽车调度到硬座汽车的前面。需要输出调度n辆车的结果序列。
双栈模拟队列
基本思路：队列是先进先出，栈是先进后出。用一个输入栈存进队元素，用一个输出栈将输出栈中的元素倒置，再出栈。这就实现了队列的先进先出。
注意：队满的条件为输入栈S1满且输出栈S2非空。并非输入栈满就代表队列满，因为如果输入栈满但输出栈空，可以将输出栈中的元素全部压入输出栈中，这就相当于队列没满，同时如果输出栈中有元素，则输入栈中的元素不能压入输出栈，如果压入就会打乱原有的序列。
#include<stdio.h>
#include<stdlib.h>
#define maxsize 30
typedef int datatype;
typedef struct{
datatype data[maxsize];
int top;
}SeqStack;
void Initial(SeqStack *S){
S->top = -1;
}
int StackIsFull(SeqStack *S){
return S->top == maxsize-1;
}
int StackIsEmpty(SeqStack *S){
return S->top == -1;
}
int StackPop(SeqStack *S){
int k;
if(StackIsEmpty(S))
return 0;
k = S->data[S->top--];
return k;
}
int StackPush(SeqStack *S,datatype x){
if(StackIsFull(S))
return 0;
S->data[++S->top]=x;
return 1;
}
//判断队空
int QueueIsEmpty(SeqStack *S1,SeqStack *S2){
return StackIsEmpty(S1)&&StackIsEmpty(S2);
}
//进队列
int EnQueue(SeqStack *S1,SeqStack *S2,datatype x){
if(StackIsFull(S1)){
if(!StackIsEmpty(S2)){
printf("用栈模拟的队列已满");
return 0;
}
else{
int k;
while(!StackIsEmpty(S1)){
k = StackPop(S1);
StackPush(S2,k);
}
}
}
StackPush(S1,x);
return 1;
}
// 出队列
int DeQueue(SeqStack *S1,SeqStack *S2){
int k;
if(QueueIsEmpty(S1,S2)){
printf("用栈模拟的队列已空");
return 0;
}
else{
if(StackIsEmpty(S2)){
while(!StackIsEmpty(S1)){
k = StackPop(S1);
StackPush(S2,k);
}
}
}
return StackPop(S2);
}
void ImitateQueue(SeqStack *S1,SeqStack *S2){
Initial(S1);
Initial(S2);
int x;
printf("请输入进队元素：");
scanf("%d",&x);
while(x!=0){
EnQueue(S1,S2,x);
scanf("%d",&x);
}
printf("出队元素为：");
while(!QueueIsEmpty(S1,S2)){
int k;
k = DeQueue(S1,S2);
printf("%d",k);
}
}
main(){
SeqStack *S1 = (SeqStack*)malloc(sizeof(SeqStack));
SeqStack *S2 = (SeqStack*)malloc(sizeof(SeqStack));
ImitateQueue(S1,S2);
}
铁道车厢调度问题
调车场两侧的铁道均为单向行驶道，中间有一段用于调度的“栈道”，调车场的入口有n节硬座和软座车厢（分别用H和S表示），设计一个算法，把所有软座车厢调度道硬座车厢前面来。要求输出对这n节车厢进行调度的结果序列。
#include<stdio.h>
#include<stdlib.h>
#define maxsize 30
typedef struct {
char data[maxsize];
int top;
}SeqStack;
void Initial(SeqStack *S){
S->top = -1;
}
int IsFull(SeqStack *S){
return S->top==maxsize-1;
}
int IsEmpty(SeqStack *S){
return S->top==-1;
}
int Push(SeqStack *S,char x){
if(IsFull(S))
return 0;
S->data[++S->top]=x;
return 1;
}
char Pop(SeqStack *S){
char c;
if(IsEmpty (S))
return 0;
c = S->data[S->top];
S->top--;
return c;
}
void Railway(SeqStack *S){
int i,j=0,n=9;
char train[n] = {'H','S','H','H','S','H','S','S','H'},result[n];
for(i=0;i<n;i++){
if(train[i]=='S')
result[j++]=train[i];
else{
Push(S,train[i]);
}
}
while(!IsEmpty(S)){
for(;j<n;j++){
result[j]=Pop(S);
}
}
for(j=0;j<n;j++){
printf("%c",result[j]);
}
}
main(){
SeqStack *S = (SeqStack*)malloc(sizeof(SeqStack));
Initial(S);
Railway(S);
}