railk.cpp

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

// 1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream.h>
#include <fstream.h>
class Node
{
	friend class stack;
    private:
	int data;
	Node *next;
};
class stack
{
	public:
		stack(){top=0;}
		~stack();
		bool empty(){return top==0;}
		bool full();
		int Top();
		stack &push(int x);
		stack &pop(int x);
	private:
		Node *top;
};
stack::~stack()
{
	Node *next;
	while(top)
	{
		next=top->next;
		delete top;
		top=next;
	}
}

int stack::Top()
{
	return top->data;
}
stack &stack::push(int x)
{
	Node *p=new Node;
	p->data=x;
	p->next=top;
	top=p;
	return *this;
}

stack &stack::pop(int x)
{
	x=top->data;
	Node *p=top;
	top=top->next;
	delete p;
	return *this;
}
void main()
{
	ifstream in("input.txt");
    int t=0,a,b,c,d,m=1,n,y,z;                 
	stack *p;
	in>>n;
	p=new stack[n];	
	for(int i=0;i<n;i++)
	{
	  in>>a;
	  y=t;
	 if(a==m) m++; //m为现在要输出的数
	 else 
	 {
	    for(int k=0,z=t;k<t;k++)      // t代表所需栈的个数   
		{
	      if(p[k].empty()!=1&&p[k].Top()==m)//栈不为空，栈顶数为现在要输出的数（成立的条件）
		  {
        	p[k].pop(m); //所需返回
	    	m++;		
	    	if(p[k].empty()) 
	    	z--;
	    	k=-1;				
		  }
       	  else if(p[k].empty())continue;//栈为空时再k++
		}



	    if(t==0)      
		{
	       t++;
		   p[t-1].push(a); //入栈
		}



	    else
		{
	     for(int j=0,c=-1,b=n;j<y;j++)
		 {
	       if(p[j].empty()!=1&&a<p[j].Top())  //  栈不为空，栈顶数大于a  （成立的条件） 
        	if(p[j].Top()<=b)
			{
			  b=p[j].Top();   //得到所有栈顶元素中最小的
			  c=j;     // c为最小值所在的栈的编号
			}
		 }
	     if(c==-1)
		 {
	      for(int r=1,d=-1;r<=t;r++)


		    if(p[r-1].empty())
			{
			  d=r;   //找是否有空栈可以存放a变量
			  break;
			}


            if(d==-1)  {p[t].push(a);t++;}   //如果找不到，就存在新开的栈里
	        else 
				p[r-1].push(a);z++; //如找到，就存放在空栈里
		  
		 }
	      else p[c].push(a);
		}
	 }
	}
	ofstream out("output.txt");
	out<<t<<endl;
}