链式队列.cpp

利用链式队列模拟操作系统中先来先服务算法

// 链式队列.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "iostream.h"
template<class T> class LinkedQueue;
//节点类
template<class T>
class ChainNode
{
	private:
	T data;
	ChainNode<T> *link;
	friend class LinkedQueue<T>;
};
template<class T>
class LinkedQueue{
 public:
  LinkedQueue()
  {
	  front=rear=0;
  }
  ~LinkedQueue();
  bool IsEmpty()const {return ((front) ? false:true);}
  bool IsFull()const;
  T First()const;
  T Last()const;
  LinkedQueue<T> &Add(const T &x);
  LinkedQueue<T> &Delete();
  void Output(ostream &out)const; 
 private:
  ChainNode<T> *front;
  ChainNode<T> *rear; 
};

// 析构 函数          

template<class T>
LinkedQueue<T>::~LinkedQueue()
{
 ChainNode<T> *next;
 while(front)
 {
  next = front->link;
  delete front;
  front = next;
 }
}

// 满队 函数          

template<class T>
bool LinkedQueue<T>::IsFull()const
{
 ChainNode<T> *p;
 try
 {
  p = new ChainNode<T>;
  delete p;
  return false;
 }
 catch(NoMem)
 {
  return true;
 }
}

// 队列头 函数          

template<class T>
T LinkedQueue<T>::First()const
{
 if(IsEmpty())
  throw OutOfBounds();
 return front->data;
}

// 队列尾 函数          

template<class T>
T LinkedQueue<T>::Last()const
{
 if(IsEmpty())
  throw OutOfBounds();
 return rear->data;
}

// 入列 函数          

 template<class T>
LinkedQueue<T> &LinkedQueue<T>::Add(const T &x)
{
 ChainNode<T> *p = new ChainNode<T>;
 p->data = x;
 p->link = 0;
 if(front)
  rear->link = p;
 else
  front = p;
 rear = p;
 return *this;
}


 //出列 函数          


template<class T>
LinkedQueue<T> &LinkedQueue<T>::Delete()
{
 if(IsEmpty())
	 cout<<"队列空！"<<endl;
 else
 {
 ChainNode<T> *s =new ChainNode<T>;
 s -> data= front -> data;
 s->link=front->link;
 ChainNode<T> *p = front;
 front=s->link;
 delete p;
 }
 return *this;
}


// 输出 函数          

template<class T>
void LinkedQueue<T>::Output(ostream &out)const
{
 ChainNode<T> *current;
 for(current=front;current;current=current->link)
 {
  out<<current->data<<" ";
 }
}

// << 重载 函数          

template<class T>
ostream &operator<< (ostream &out, const LinkedQueue<T> &x)
{
 x.Output(out);
 return out;
}

void main()
{
	LinkedQueue<int> a;
	int i,x=0;//x是队列中作业的编号
	printf("按下“1”做出队操作，并显示队列中的作业编号;\n按下“2”做出队操作，并显示队列中的作业编号;\n按下“0”退出\n");
	do
	{
	cin>>i;
	switch(i)
	{
	    case 1: 
			{
				a.Add(x);
				x++;
				cout<<a<<endl;
				break;
			}
		case 2: 
			{
				a.Delete();
				cout<<a<<endl;
			}
	}//end switch
	}while(i);
	
}