学步园

#include <iostream.h>
#include <assert.h>
#define DefaultSize 10
template <class T> class Stack;
template <class T> class Queue;
template <class T> class PQueue;
// Bag类的定义
template <class T>
class Bag 
{
 friend class Stack<T>;
 friend class Queue<T>;
 friend class PQueue<T>;
 
public:
 Bag(int sz = DefaultSize);     //构造函数
 virtual ~Bag();        //析构函数
 virtual void Add(const T& item);   //插入函数
 virtual T *Remove();      //删除函数
 virtual int IsEmpty() { return top == -1; } //判空函数
 virtual int IsFull() { return top == maxSize - 1; }  //判满函数
private:
 virtual void Empty() { cout << "Data Structure is empty." << endl; }
 virtual void Full() { cerr << "DataStructure is full." << endl; }
 T *elements;         //存储数组
 int maxSize;         //数组的大小
 int top;          //数组当前元素个数
};
// Bag类的构造函数
template <class T> 
Bag<T>::Bag(int MaxBagSize):maxSize(MaxBagSize) 
{
 elements = new T[maxSize];
 top = -1;
}
// Bag类的析构函数
template <class T>
Bag<T>::~Bag() 
{
 delete [] elements;
}
// Bag类的插入函数
template <class T>
void Bag<T>::Add(const T & item) 
{
 if (IsFull()) 
  Full();
 else 
  elements [++top] = item;
}
// Bag类的删除函数
template <class T>
T *Bag<T>::Remove() 
{
 if(IsEmpty()) 
 {
  Empty(); 
  return NULL; 
 }
 T &x = elements [0];     //保存被删除元素的值
 for(int i = 0; i < top; i++)   //后面元素填补上来
  elements [i] = elements [ i+1];
 top--;
 return &x;
}
// 栈的类定义（继承Bag类）
//------------------------------------------------------------------------------------------------stack
template <class T> 
class Stack:public Bag<T>
{
public:
 Stack(int sz = DefaultSize);    //构造函数
 ~Stack();         //析构函数
 T *Remove();         //删除函数
};
// 栈的构造函数
template <class T>
Stack<T>::Stack(int sz):Bag<T>(sz) {} //栈的构造函数Stack将调用Bag的构造函数
 
// 栈的析构函数
template <class T> 
Stack<T>::~Stack() {} //栈的析构函数将自动调用Bag的析构函数, 以确保数组elements的释放
 
// 栈的删除函数
template <class T> 
T * Stack<T>::Remove() 
{
 if(IsEmpty())
 {
  Empty();
  return NULL; 
 }
 T &x = elements[top--];
 return &x;
}
// 队列的类定义（继承Bag类）
//------------------------------------------------------------------------------------------------Queue
template <class T> 
class Queue:public Bag<T> 
{
public:
 Queue(int sz = DefaultSize);     //构造函数
 //~Queue();          //析构函数
 //T *Remove(); 
};
 
// 队列的构造函数
template <class T> 
Queue<T>::Queue(int sz):Bag<T>(sz) {}    //队列的构造函数Queue将调用Bag的构造函数

// 优先级队列的类定义（继承Bag类）
//------------------------------------------------------------------------------------------------PQueue
template <class T> 
class PQueue:public Bag<T> 
{
public:
 PQueue(int sz = DefaultSize);    //构造函数
 ~PQueue() {}        //析构函数
 T *Remove();        //删除函数
};
// 优先级队列的构造函数
template <class T> 
PQueue<T>::PQueue(int sz):Bag<T>(sz) {}  //建立一个最大具有sz个元素的空优先级队列。top = -1。
 
// 优先级队列的删除函数
template <class T> 
T *PQueue<T>::Remove() 
{
 //若优先级队列不空则函数返回该队列具最大优先权(值最小)元素的值, 同时将该元素删除。
 if(IsEmpty())
 {
  Empty(); 
  return NULL; 
 }
 T &min = elements[0];      //假设elements[0]是最小值，继续找最小值 
 int minindex = 0;
 for(int i = 1; i <= top; i++) 
 {
  if(elements[i] < min)
  {
   min = elements[i];
   minindex = i; 
  }
 }
 
 elements[minindex] = elements[top];   //用最后一个元素填补要取走的最小值元素
 top--;
 
 return &min;        //返回最小元素的值
}
void main()
{
 Stack<int> aStack(10);
 Queue<int> aQueue(10);
 PQueue<int> aPQueue(10);
 aStack.Add(1);
 aQueue.Add(2);
 int n = *aQueue.Remove();
 cout << n;
 
}