用队列写的啊
#include<iostream.h>
const N=100;
template <class T>
struct Node
{
T data;
Node<T> *next; //此处<T>也可以省略
};
template <class T>
class LinkQueue
{
public:
LinkQueue( ); //构造函数，初始化一个空的链队列
~LinkQueue( ); //析构函数，释放链队列中各结点的存储空间
void EnQueue(T x); //将元素x入队
T DeQueue( ); //将队头元素出队
T GetQueue( ); //取链队列的队头元素
bool Empty( ); //判断链队列是否为空
Node<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点
};
template <class T>
LinkQueue<T>::LinkQueue( )
{
Node <T> *s;
s=new Node<T>;
s->next=NULL;
front=rear=s;
}
/*
* 前置条件：队列存在
* 输 入：无
* 功 能：销毁队列
* 输 出：无
* 后置条件：释放队列所占用的存储空间
*/
template <class T>
LinkQueue<T>::~LinkQueue( )
{
while(front)
{
Node <T> *p;
p=front->next;
delete front;
front=p;
}
}
/*
* 前置条件：队列已存在
* 输 入：元素值s
* 功 能：在队尾插入一个元素
* 输 出：无
* 后置条件：如果插入成功，队尾增加了一个元素
*/
template <class T>
void LinkQueue<T>::EnQueue(T x)
{
Node<T> *s;
s=new Node<T>;
s->data=x; //申请一个数据域为x的结点s
s->next=NULL;
rear->next=s; //将结点s插入到队尾
rear=s;
}
/*
* 前置条件：队列已存在
* 输 入：无
* 功 能：删除队头元素
* 输 出：如果删除成功，返回被删元素值，否则，抛出删除异常
* 后置条件：如果删除成功，队头减少了一个元素
*/
template <class T>
T LinkQueue<T>::DeQueue()
{
Node <T> *p; int x;
if (rear==front) throw "下溢";
p=front->next;
x=p->data; //暂存队头元素
front->next=p->next; //将队头元素所在结点摘链
if (p->next==NULL) rear=front; //判断出队前队列长度是否为1
delete p;
return x;
}
/*
* 前置条件：队列已存在
* 输 入：无
* 功 能：读取队头元素
* 输 出：若队列不空，返回队头元素
* 后置条件：队列不变
*/
template <class T>
T LinkQueue<T>::GetQueue()
{
if (front!=rear)
return front->next->data;
}
/*
* 前置条件：队列已存在
* 输 入：无
* 功 能：判断队列是否为空
* 输 出：如果队列为空，返回1，否则，返回0
* 后置条件：队列不变
*/
template <class T>
bool LinkQueue<T>::Empty( )
{
if(front==rear)
return 1;
else
return 0;
}
void Output(int& minH, int& minQ, LinkQueue<int> H[], int k, int n)
{ //从缓冲铁轨移动到出轨，并修改minH 和m i n Q .
int c; // 车厢编号
// 从队列minQ 中删除编号最小的车厢minH
H[minQ].DeQueue( ) ;
cout << "Move car " << minH << " from holding track " << minQ << " to output" << endl;
// 通过检查所有队列的首部，寻找新的m i n H和m i n Q
minH= n+2;
for (int i = 1; i <= k; i++)
if (!H[i].Empty() &&(c = H[i].front->next->data) < minH)
{
minH = c;
minQ = i;}
}
bool Hold(int c, int& minH, int &minQ, LinkQueue<int> H[], int k)
{ //把车厢c 移动到缓冲铁轨中
// 如果没有可用的缓冲铁轨，则返回f a l s e，否则返回t r u e
// 为车厢c 寻找最优的缓冲铁轨
// 初始化
int BestTrack = 0, // 目前最优的铁轨
BestLast = 0, // BestTrack 中最后一节车厢
x; // 车厢编号
// 扫描缓冲铁轨
for (int i = 1; i <= k; i++)
if (!H[i].Empty()) {// 铁轨i 不为空
x = H[i].rear->data;
if (c > x && x > BestLast) { // 铁轨i 尾部的车厢编号较大
BestLast = x;
BestTrack = i;}
}
else // 铁轨i 为空
if (!BestTrack) BestTrack = i;
if (!BestTrack) return false; // 没有可用的铁轨
// 把c 移动到最优铁轨
H [BestTrack ] . EnQueue ( c ) ;
cout << "Move car " << c << " from input " << "to holding track " << BestTrack << endl;
// 如果有必要，则修改m i n H和m i n Q
if (c < minH) {minH = c; minQ = BestTrack ; }
return true;
}
bool Railroad(int p[], int n, int k)
{// k 个缓冲铁轨，车厢初始排序为p [ 1 : n ]
// 如果重排成功，返回t r u e，否则返回false
// 如果内存不足，则引发异常NoMem 。
//创建与缓冲铁轨对应的堆栈
LinkQueue<int> *H;
H = new LinkQueue<int> [k + 1];
int NowOut = 1; //下一次要输出的车厢
int minH = n+1; //缓冲铁轨中编号最小的车厢
int minS; //minH号车厢对应的缓冲铁轨
//车厢重排
for (int i = 0; i < n; i++)
if (p[i] == NowOut)
{// 直接输出t
cout << "Move car " << p[i] << " from input to output" << endl;
NowOut++ ;
//从缓冲铁轨中输出
while (minH == NowOut)
{
Output(minH, minS, H, k, n);
NowOut++ ;
}
}
else {// 将p[i] 送入某个缓冲铁轨
if (!Hold(p[i], minH, minS, H, k))
return false;
}
return true;
}
void main()
{
//int p[9]={3,6,9,2,4,7,1,8,5},i=9,j=3;
int p[N],i,j;
cout<<"火车总数i和缓冲轨数j"<<endl;
cin>>i>>j;
cout<<"输入火车进轨的顺序"<<endl;
for(int k=0;k<i;k++)
cin>>p[k];
Railroad(p,i,j);
}