pex13_7.cpp

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

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

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

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

// the priority queue is implemented using a maximum heap
#include "maxheap.h"

// implementation of a stack using a priority queue
template <class T>
class Stack
{
	private:
		// pointer to heap object that holds stack items
		MaxHeap< PriorityData<T> > *stackList;
		// priority level of the next data value inserted.
		// PL = {0, 1, 2, 3, ...}
		int PL;
		
	public:
		// constructor
		Stack(int maxsize);
		
		// stack access methods 
		void Push(const T& item);
		T Pop(void);
		T Peek(void);
		
		// stack test and clear methods
		int StackEmpty(void) const;
		void ClearStack(void);
};

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

// Stack method StackEmpty tests for empty stack
template <class T>
int Stack<T>::StackEmpty(void) const
{
	return stackList->ListEmpty();
}

// Stack method ClearStack clears the stack
template <class T>
void Stack<T>::ClearStack(void)
{
	stackList->ClearList();
	PL = 0;
}

// Stack method Push inserts item into the stack
template <class T>
void Stack<T>::Push(const T& elt)
{
	PriorityData<T> rec;
	
	// assign elt to the data field of rec and the
	// current priority value to the priority field
	// increment the priority level
	rec.data = elt;
	rec.priority = PL++;
	
	if (stackList->ListFull())
	{
		cerr << "QInsert: stack full!" << endl;
		exit(1);
	}
	
	// insert rec into the maximum heap
	stackList->Insert(rec);
}

// Stack method Pop removes item from top of the stack
template <class T>
T Stack<T>::Pop(void)
{
	// test for an empty stack and terminate if true
	if (stackList->ListEmpty())
	{
		cerr << "Calling Pop for an empty stack!" << endl;
		exit(1);
	}
	
	PriorityData<T> rec;
	
	// delete the record having the maximum priority field.
	// this is the last record inserted into the maximum heap,
	// giving us a LIFO structure (stack)
	rec = stackList->Delete();
	return rec.data;
}

// return the data value from the top of the stack
template <class T>
T Stack<T>::Peek(void)
{
	// test for an empty stack and terminate if true
	if (stackList->ListEmpty())
	{
		cerr << "Calling Peek for an empty stack!" << endl;
		exit(1);
	}
	
	// return maximum element from the heap
	return (*stackList)[0].data;
}

void main(void)
{
	Stack<int> S(5);
	int val;
	
	// read 5 data values. insert them into S
	// and flush the stack, printing the values

	cout << "Enter 5 integer values: ";
	for(int i=0;i < 5;i++)
	{
		cin >> val;
		S.Push(val);
	}
	cout << endl;

	cout << "The stack is: ";
	while(!S.StackEmpty())
		cout << S.Pop() << "  ";
	cout << endl;
} 

/*
<Run>

Enter 5 integer values: 1 2 3 4 5

The stack is: 5  4  3  2  1
*/