【数据结构与算法实习】题目4 列车调度(Train)

某列车调度站的铁道联接结构如Figure 1所示。

image.png

其中，A为入口，B为出口，S为中转盲端。所有铁道均为单轨单向式：列车行驶的方向只能是从A到S，再从S到B；另外，不允许超车。因为车厢可在S中驻留，所以它们从B端驶出的次序，可能与从A端驶入的次序不同。不过S的容量有限，同时驻留的车厢不得超过m节。
设某列车由编号依次为{1, 2, …, n}的n节车厢组成。调度员希望知道，按照以上交通规则，这些车厢能否以{a1, a2, …, an}的次序，重新排列后从B端驶出。如果可行，应该以怎样的次序操作?

输入格式:
共两行。
第一行为两个整数n，m。
第二行为以空格分隔的n个整数，保证为{1, 2, …, n}的一个排列，表示待判断可行性的驶出序列{a1，a2，…，an}。

要求：
1 ≤ n ≤ 1,600,000
0 ≤ m ≤ 1,600,000

输出格式:
若驶出序列可行，则输出操作序列，其中push表示车厢从A进入S，pop表示车厢从S进入B，每个操作占一行。
若不可行，则输出No。

输入样例:
5 2
1 2 3 5 4
输出样例:
push
pop
push
pop
push
pop
push
push
pop
pop
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

#include<stdio.h>
#include<malloc.h>
//merge1
#define true 1
#define false 0
#define push 1
#define pop 0
#define ERROR -1

typedef int Position;
typedef int ElementType;
typedef struct SNode * PtrToSNode;
typedef int bool;

struct SNode
{
/* data */
ElementType *Data;
Position Top;
int MaxSize;
};//尝试修改

typedef int git ;
typedef PtrToSNode Stack;

Stack CreateStack(int MaxSize){
Stack S = (Stack)malloc(sizeof(struct SNode));
S->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType));
S->Top = -1;
S->MaxSize = MaxSize;
return S;
}

bool IsFull(Stack S){
return (S->Top == S->MaxSize-1);
}

ElementType Push(Stack S, ElementType X){
if (IsFull(S)){
return false;
}
else{
S->Data[++(S->Top)]=X;
return X;
}
}

bool IsEmpty(Stack S){
return(S->Top==-1);
}

ElementType Pop(Stack S){
if(IsEmpty(S)){
return ERROR;
}
else{
return (S->Data[(S->Top)–]);
}
}

int main(){
bool flag = false;
int maxSize; int maxHold;
Stack sFlag = CreateStack(10000);
Stack sFlag2 = CreateStack(10000);

//第一行为两个整数n，m。
scanf("%d", &maxSize);
scanf("%d", &maxHold);

ElementType qTo[16];
ElementType qFrom[16];
Stack sTrans = CreateStack(maxHold);

//第二行为以空格分隔的n个整数，保证为{1, 2, ..., n}的一个排列
//表示待判断可行性的驶出序列{a1，a2，...，an}。
ElementType Element;
ElementType sCache;
int countFrom;
int countTo;

for(countFrom=0;countFrom<maxSize;countFrom++){
    scanf("%d",&Element);
    qTo[countFrom] = Element;
}

for(countTo = 0; countTo<maxSize; countTo++){
    qFrom[countTo] = countTo+1;
}

int toCount = 0;
for(int count = 0; count<maxSize; ){
    if(qFrom[count]==qTo[toCount]){
        Push(sFlag, push);
        Push(sFlag, pop);

        toCount++;
        count++;
    }
    else{
        if(!IsEmpty(sTrans)){
            sCache = Pop(sTrans);
            if(sCache==qTo[toCount]){
                toCount++;
            }
            else{
                Push(sTrans, sCache);
                if(Push(sTrans, qFrom[count])){
                    Push(sFlag, push);
                }
                else{
                    printf("No");
                    return 0;
                }
                
                count++;
            }
        }
        else{
            if(Push(sTrans, qFrom[count])){
                Push(sFlag, push);
            }
            else{
                printf("No");
                return 0;
            }
            count++;
        }
    }
    if(toCount == maxSize-1){
        flag = true;
        break;
    }
}
while(!IsEmpty(sTrans)){
    sCache = Pop(sTrans);
    Push(sFlag, pop);
    if(sCache==qTo[toCount]){
        toCount++;
    }
    if(toCount == maxSize-1){
        flag = true;
        break;
    }
}

while(!IsEmpty(sFlag)){
    Push(sFlag2, Pop(sFlag));
}

if(flag){
        while(!IsEmpty(sFlag2)){
        if(Pop(sFlag2)){
            printf("push\n");
        }
        else{
            printf("pop\n");
        }
    }
}
else{
    printf("No");
}    
return 0;

}