本文共 2092 字，大约阅读时间需要 6 分钟。

栈的应用：火车调度

问题概述

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

思路分析

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

代🐎与注释

#include
   
    #include
    
     #include
     
      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]);}
     
    
   

测试与结果

输入：6\n YYRYRR

完

copyright swy_swy_swy , all rights reserved.

转载地址：http://ozwai.baihongyu.com/