pex13_6.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <stdlib.h>
#pragma hdrstop

// a heap serves as a priority queue
#include "heap.h"

// used to implement a queue with a priority queue
template <class T>
struct PriorityData
{
	T data;
	int priority;
};

// compare two PriorityData records by priority
template <class T>
int operator<= (const PriorityData<T>& x, const PriorityData<T>& y)
{
	return x.priority <= y.priority;
}

// implements a queue using a priority queue
template <class T>
class Queue
{
	private:
		// pointer to heap object that holds queue items and
		// serves as a priority queue
		Heap< PriorityData<T> > *queueList;
		// priority level of the next data value inserted.
		// PL = {0, 1, 2, 3, ...}
		int PL;

	public:
		// constructor
		Queue(int maxsize);

		// queue access methods 
		void QInsert(const T& elt);
		T QDelete(void);

		// queue access
		T QFront(void);

		// queue test methods
		int QLength(void) const;
		int QEmpty(void) const;
		void QClear(void);
};

// constructor
template <class T>
Queue<T>::Queue(int maxsize): PL(0)
{
	// allocate the heap
	queueList = new Heap< PriorityData<T> >(maxsize);
	if(queueList == NULL)
	{
		cerr << "Queue constructor: Memory allocation failure!" << endl;
		exit(1);
	}
}

// PQueue method PQLength returns length of list
template <class T>
int Queue<T>::QLength(void) const
{
	return queueList->ListSize();
}

// PQueue method PQEmpty tests for empty queue
template <class T>
int Queue<T>::QEmpty(void) const
{
	return queueList->ListEmpty();
}

// PQueue method PQClear clears the queue
template <class T>
void Queue<T>::QClear(void)
{
	queueList->ClearList();
	PL = 0;
}

// PQueue method PQInsert inserts item into the queue
template <class T>
void Queue<T>::QInsert(const T& elt)
{
	PriorityData<T> rec;
	
	// assign elt to the data field of rec and set the
	// priority field to the current value of PL.
	// increment PL
	rec.data = elt;
	rec.priority = PL++;
	
	if (queueList->ListFull())
	{
		cerr << "QInsert: queue full!" << endl;
		exit(1);
	}
	
	// insert the record into the heap
	queueList->Insert(rec);
}

// PQueue method PQDelete removes item from front of the queue
template <class T>
T Queue<T>::QDelete(void)
{
	// test for an empty queue and terminate if true
	if (queueList->ListEmpty())
	{
		cerr << "Calling QDelete for an empty queue!" << endl;
		exit(1);
	}
	
	PriorityData<T> rec;
	
	// delete the record with the smallest value of PL. the
	// records come out in FIFO order. return the data field
	rec = queueList->Delete();
	return rec.data;
}

// return the data value from the first item in the queue
template <class T>
T Queue<T>::QFront(void)
{
	// test for an empty queue and terminate if true
	if (queueList->ListEmpty())
	{
		cerr << "Calling QFront for an empty queue!" << endl;
		exit(1);
	}
	
	// return minimum element from the heap
	return (*queueList)[0].data;
}

void main(void)
{
	Queue<int> Q(5);
	int val;
	
	// read 5 data values. insert them into Q
	// and flush the queue, printing the values
	
	cout << "Enter 5 integer values: ";
	for(int i=0;i < 5;i++)
	{
		cin >> val;
		Q.QInsert(val);
	}
	cout << endl;

	cout << "The queue is: ";
	while(!Q.QEmpty())
		cout << Q.QDelete() << "  ";
	cout << endl;
} 

/*
<Run>

Enter 5 integer values: 5 3 2 7 8

The queue is: 5  3  2  7  8
*/