railqk.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include <iostream>
class queue;
class node
{
	friend queue;
public:
	int data;
	node *next;
};
class queue
{
	node *first,*tail;
public:
	int top,last;
	queue() {first=0;tail=0;top=0;}
	void dequeue();
	void enqueue(int x);
};
void queue::dequeue()
{
	
	node *p=first;
	first=first->next;
	top=first->data;
	if(!first) {top=0;last=0;}
	delete p;
}
void queue::enqueue(int x)
{
	node *p=new node;
	p->data=x;
	p->next=0;
	if(first) tail->next=p;
	else {first=p;top=x;}
	tail=p;	
	last=x;
}
int main()
{
	int n,i,k,j,max=0,l=0,m=1,tim=1;
	scanf("%d",&n);
	queue *q=new queue[n+2];
	for(i=0;i<n;i++)
	{
		scanf("%d",&k);
		q[0].enqueue(k);
	}
	for(i=1;i<n;i++)
	{	
		if(q[0].top==m)
		{
			q[0].dequeue();
			++m;
			if(q[0].top==m) break;
			for(j=1;j<=l;j++)
			{
	
				if(q[j].top!=m) continue;
				else
				{
					q[j].dequeue();
					++m;
					j=1;
					if(q[0].top==m) { tim=0;break;}
				}
				if(tim==0) {tim=1; break;}
			}
		}
		else
		{
	
			for(j=1;j<=l;j++)
			{
				if(q[0].top>q[j].last) {q[j].enqueue(q[0].top);q[0].dequeue();break;}
			}
			if(j==(l+1)) 
			{
				q[j].enqueue(q[0].top);
				q[0].dequeue();
			}
			if(max<j) 
			{
				max=j;
				++l;
			}
		}
	}
	printf("%d",max);
	return 0;
	
}