pex9_13.cpp

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

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

#include "cnode.h"

// queue class implemented with a circular linked list
template <class T>
class Queue
{
    private:
    	// header for a circular linked list
    	// that holds the queue items
        CNode<T> queueHeader;
        // pointer to the rear of the list
        CNode<T> *rear;
        // number of items in the queue
        int qsize;
        
    public:
    	// constructor
        Queue(void);
        
        // queue access methods 
        void QInsert(const T& elt);
        T QDelete(void);
        
        // queue access
        T QFront(void) const;
        
        // queue test methods
        int QLength(void) const;
        int QEmpty(void) const;
        void QClear(void);
};

// constructor. rear points to the header,
// qsize is 0
template <class T>
Queue<T>::Queue (void)
{
	rear = &queueHeader;
	qsize = 0;
}

// insert an element at the rear of the queue
template <class T>
void Queue<T>::QInsert (const T& item)
{
	// allocate a node containing data value item
	CNode<T> *p = new CNode<T>(item);
	
	// insert new node at the rear of the list
    rear->InsertAfter(p);
    // update the rear pointer and queue size
    rear = p;
    qsize++;
}

// delete the item at the front of the queue
template <class T>
T Queue<T>::QDelete (void)
{
    T temp;
    
	// if the header points to itself, the list is empty
    if (queueHeader.NextNode() == &queueHeader)
    {
        cerr << "Attempt to delete from an empty Queue!" << endl;
        exit(1);
    }

	// retrieve the value at the front of the list
    temp = queueHeader.NextNode()->data;

    // if header points to rear, the queue has 1 element
    // and will become empty. adjust rear to be address
    // of the header
    if (queueHeader.NextNode() == rear)
    	rear = &queueHeader;
    // unlink the front of the list and delete the node
    delete queueHeader.DeleteAfter();
    // decrement the queue size
    qsize--;
    
	// return the value that was at the front of the queue
    return temp;
}

// return the data value at the front of the queue
template <class T>
T Queue<T>::QFront(void) const
{
	// error if the queue is empty
   if (queueHeader.NextNode() == &queueHeader)
   {
   		cerr << "Attempting to access and empty queue" << endl;
   		exit(1);
   	}

   	return queueHeader.NextNode()->data;
}

// return the number of elements in the queue
template <class T>
int Queue<T>::QLength(void) const
{
   return qsize;
}

// indicate whether the queue is empty
template <class T>
int Queue<T>::QEmpty(void) const
{
	// the queue is empty if header points to itself
	return queueHeader.NextNode() == &queueHeader;
}

// delete all the elements in the queue
template <class T>
void Queue<T>::QClear(void)
{
	// remove nodes after the header until the header
	// points to itself
	while(queueHeader.NextNode() != &queueHeader)
		delete queueHeader.DeleteAfter();
}

void main(void)
{
	// Q will contain 1  2 ... 10
	Queue<int> Q;

	// insert the data values into Q
	for (int i = 1; i <= 10; i++)
		Q.QInsert(i);
	// for testing purposes, print the queue length and
	// the element at the front of the queue
	cout << "Queue size is " << Q.QLength() << endl;
	cout << "First element is " << Q.QFront() << endl;
	
	// delete and print queue values until the queue is empty
	cout << "Deleting all values from the queue: ";
	while (!Q.QEmpty())
		cout << Q.QDelete() << "  ";
	cout << endl;
}

/*
<Run>

Queue size is 10
First element is 1
Deleting all values from the queue: 1  2  3  4  5  6  7  8  9  10
*/