#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#define StackSize 100//假定预分配的栈空间最多元素为100个元素
#define MaxLength 100//最大的字符串长度
typedef int DataType;
typedef struct{
    DataType data[StackSize];
    int top;
}SeqStack;

void Initial(SeqStack *S)
{S->top=-1;}

int IsEmpty(SeqStack *S)
{ return S->top==-1;}

int IsFull(SeqStack *S)
{return S->top==StackSize-1;}

void Push(SeqStack *S,DataType x)
{if(IsFull(S)){printf("栈已满\n");exit(1);}
S->data[++S->top]=x;
}

DataType Pop(SeqStack *S)
{if(IsEmpty(S)){printf("栈已空\n");return (-1);}
return S->data[S->top--];
}

DataType Top(SeqStack *S)
{if(IsEmpty(S)){printf("栈已空\n");exit(1);}
return S->data[S->top];
}

int Hold(int c,int *minH,int *minS,SeqStack *H,int k,int n)
{
int BestTrack=0,i;//目前最优车道
int BestTop=n+1;//最优车道上的头辆车厢
DataType x;//车厢索引
for(i=1;i<=k;i++)//扫描缓冲轨道
{
    if(!IsEmpty(&H[i]))
    {x=Top(&H[i]);
        if(c<x && x<BestTop)
        {BestTop=x;BestTrack=i;}
    }

    else
    if(!BestTrack) {BestTrack=i;}
}
Push(&H[BestTrack],c);
printf("移动车%d从出口到缓冲道%d\n",c,BestTrack);
if(c<*minH){*minH=c;*minS=BestTrack;}
if(!BestTrack){printf("没有可用的轨道\n"); return 0;}
return 1;
}

void Output(int *minH,int *minS,SeqStack H[],int k,int n)
{
    int c,i;
    c=Pop(&H[*minS]);
    printf("移动车%d从缓冲车道%d到出口\n",*minH,*minS);
    *minH=n+1;
    for (i=1;i<=k;i++)
    {
    if(!IsEmpty(&H[i])&&(c=Top(&H[i]))<*minH)
    {*minH=c;*minS=i;}
    }
}

int Railroad(int p[],int n,int k)
{
    SeqStack *H;
    int NowOut=1;
    int minH=n+1;
int minS,a,j;
H=(SeqStack*)calloc(10,sizeof(SeqStack));
for(j=1;j<=k;j++)
{
    Initial (&H[j]);
}
for(a=0;a<=n-1;a++)
{
    if(p[a]==NowOut)
    {printf("移动车厢%d从入口到出口\n",p[a]);NowOut++;
    while(minH==NowOut){Output(&minH,&minS,H,k,n);NowOut++;}
    }
    else
    {if(!Hold(p[a],&minH,&minS,H,k,n)) return 0;}
}
return 1;
}

void main(void)
{

    int p[8]={3,2,1,8,6,7,4,5};
    Railroad(p,8,4);
}