队列的应用

实验题目：队列的应用

1、实验目的：

（1）掌握队列的特点及其存储方法；

（2）掌握队列的常见算法和程序实现。 2、实验内容：火车车厢重排问题。 3、实验说明：

转轨站示意图如下：

H1 581742963 入 轨 H3 H2 987654321 出 轨 火车车厢重排过程如下：

963 H1 581 H3 出 轨 入 轨 742 H2

(a) 将369、247依次入缓冲轨

96 H1 5 54321 H3 出 轨 入 轨 87 H2 将8入缓冲轨，5移至出轨 (c)

火车车厢重排算法伪代码如下：

96 H1 58 入 轨 H3 7 H2 4321 出 轨 (b) 将1移至出轨，234移至

出轨

H1 入 轨 H3 H2 (d) 将67移至出轨

987654321 出 轨 1. 分别对k个队列初始化； 2. 初始化下一个要输出的车厢编号nowOut = 1; 3. 依次取入轨中的每一个车厢的编号； 3.1 如果入轨中的车厢编号等于nowOut，则 3.1.1 输出该车厢； 3.1.2 nowOut++； 3.2 否则，考察每一个缓冲轨队列 for (j=1; j<=k; j++) 3.2.1 取队列 j 的队头元素c； 3.2.2 如果c=nowOut，则 3.2.2.1 将队列 j 的队头元素出队并输出； 3.2.2.2 nowOut++； 3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则 3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j; 3.3.2 如果 j 存在，则把入轨中的第一个车厢移至缓冲轨 j； 3.3.2 如果 j 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；

设计分析

用队列解决出列问题，这里采用的是顺序队列的存储结构。

采用的算法思想是：分别对k个队列初始化；初始化下一个要输出的车厢编号nowOut = 1; 依次取入轨中的每一个车厢的编号；如果入轨中的车厢编号等于nowOut，则输出该车厢；nowOut++；否则，考察每一个缓冲轨队列

for (j=1; j<=k; j++)

3.2.1 取队列 j 的队头元素c； 3.2.2 如果c=nowOut，则

3.2.2.1 将队列 j 的队头元素出队并输出； 3.2.2.2 nowOut++；

如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;如果 j 存在，则把入轨中的第一个车厢移至缓冲轨 j；如果 j 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束

源程序代码

#include const N=10;

template struct Node

{ T data; Node *next; };

template class LinkQueue { public: LinkQueue(); ~LinkQueue(); void EnQueue(T x); T DeQueue(); T GetQueue(); bool Empty(); Node*front,*rear; };

template

LinkQueue::LinkQueue() { Node*s; s=new Node; s->next=NULL; front=rear=s; }

template

LinkQueue::~LinkQueue() { while(front) { Node*p; p=front->next; delete front; front=p; } }

template

void LinkQueue::EnQueue(T x) { Node*s; s=new Node; s->data=x; s->next=NULL; rear->next=s; rear=s;

}

template

T LinkQueue::DeQueue() { Node*p; int x; if(rear==front) throw\"下溢\"; p=front->next; x=p->data; front->next=p->next; if(p->next==NULL)rear=front; delete p; return x; }

template

T LinkQueue::GetQueue() { if(front!=rear) return front->next->data; }

template

bool LinkQueue::Empty() { if(front==rear) return 1; else return 0; }

void Output(int& minH,int& minQ,LinkQueueH[],int k,int n) { int c; H[minQ].DeQueue(); cout<<\"move car\"<next->data)bool Hold(int c,int &minH,int &minQ,LinkQueueH[],int k) { int BestTrack=0,BestLast=0,x;

for(int i=1;i<=k;i++) if(!H[i].Empty()) { x=H[i].rear->data; if(c>x&&x>BestLast) { BestLast=x; BestTrack=i; } } else if (!BestTrack)BestTrack=i; if (!BestTrack)return false; H[BestTrack].EnQueue(c); cout<<\"move car\"<bool Railroad(int p[],int n,int k) { LinkQueue*H; H=new LinkQueue[k+1]; int NowOut=1; int minH=n+1; int minS; for(int i=0;ivoid main()

{ int p[N],i,j; cout<<\"请输入一列火车的车厢总数i和缓冲轨数j\"<>i>>j; if(i>=N) cout<<\"输入车厢总数i不能超过(N=10)\"<>p[k]; Railroad(p,i,j); }

测试用例

当车厢数为7个缓冲数为3时

当车厢数为8个缓冲数为3时

当车厢数为8个缓冲数为4时

当车厢数为9个缓冲数为3时

当车厢数为9个缓冲数为4时

当输入车厢总数i 超过(N=10)时

当缓冲轨数不足时（失败）

实验总结

通过本次实验我理解了栈和队列的特性以及它们之间的差异，知道在何时使用哪种数据结构。掌握了在顺序栈和链栈上实现栈和队列的进栈出栈、入队列出队等基本运算算法，以及它们的顺序存储结构和链式存储结构。

这次实验我参考了书上的报数问题和迷宫问题的求解方法思想，根据火车重排问题伪代码编写，在实验过程中出现了不少问题，同学给了我很大的帮助，同时我也收获了很多。