栈的应用：火车调度问题

栈的应用：火车调度

问题概述

输入第一行是一个整数N，表示车厢的数量；第二行是一个由Y于R组成的字符串，表示车厢的排列，其中Y表示硬座，R表示软座。我们的任务，是借助一个栈，使得车厢的顺序变为软座在硬座前。
输出是一个由I与O组成的字符串，代表栈的操作，I表示入栈，O表示出栈

思路分析

逐一读入火车字符串，遇到硬座，就把它入栈缓存，遇到软座，就先入栈，然后立刻出栈（相当于没有缓存），最后，当所有车厢被读入完毕，此时所有硬座都在栈内缓存，依次出栈直到栈空为止。

代🐎与注释

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>struct ListNode {char data;ListNode* Next;ListNode* Last;
};
struct List {ListNode* header;ListNode* trailer;int _size;
};void CreateList(List* l)//build the list
{l->_size = 0;l->header = (ListNode*)malloc(sizeof(ListNode));l->trailer = (ListNode*)malloc(sizeof(ListNode));l->header->Next = l->trailer;l->header->Last = NULL;l->trailer->Last = l->header;l->trailer->Next = NULL;
}void InsertList(List* l, char e)//空表，在尾节点前插入
{ListNode* np = (ListNode*)malloc(sizeof(ListNode));np->data = e;np->Next = l->trailer;np->Last = l->trailer->Last;l->trailer->Last->Next = np;l->trailer->Last = np;l->_size++;
}void PushList(List* l, char e)//入栈
{ListNode* np = (ListNode*)malloc(sizeof(ListNode));np->data = e;np->Last = l->header;np->Next = l->header->Next;np->Next->Last = np;l->header->Next = np;l->_size++;
}char PopList(List* l)//出栈
{ListNode* now = l->header->Next;char old = now->data;now->Last->Next = now->Next;now->Next->Last = now->Last;free(now);l->_size--;return old;
}int main()
{int N;//车厢总数scanf_s("%d",&N);int ready = 0;//已经处理完的车厢数List notready;CreateList(&notready);for (int i = 0; i < N+1; i++){char tmp;scanf_s("%c", &tmp);if (tmp != '\n')InsertList(&notready, tmp);}List train;//总栈CreateList(&train);char* out;out = (char*)calloc(2 * N, sizeof(char));int outhead = 0;while (1){if ( ready == N)break;else{if ((train._size == 0||train.header->Next->data=='Y')&&notready._size!=0){PushList(&train, PopList(&notready));out[outhead] = 'I';}else {PopList(&train);ready++;out[outhead] = 'O';}}outhead++;}for (int i = 0; i < 2 * N; i++)printf_s("%c", out[i]);
}