awe的程設筆記

Queue.h 佇列ADT

#ifndef QUEUE_H
#define QUEUE_H

template <typename E>
class Queue
{
private:
void operator = (const Queue&){}
Queue (const Queue&) {}
public:
Queue(){};
virtual ~Queue(){}

virtual void clear() = 0;
virtual void enqueue(const E&) = 0;
virtual E dequeue() = 0;

virtual const E& frontValue()const = 0;
virtual int length() const = 0;
};
#endif

Limk.h 節點定義

#ifndef LINK_H
#define LINK_H


#include<iostream>
using namespace std;
template<typename E>
class Link
{
private:
    static Link<E>* freelist;
public:
    E element;
    Link<E>* next;

    Link(const E& elemval, Link<E>* nextval = NULL)
    {
        element = elemval;
        next = nextval;
    }

    Link(Link<E>* nextval = NULL)
    {
        next = nextval;
    }
    
    void* operator new (size_t)
    {
        if(freelist == NULL) return ::new Link;
        Link<E>* temp = freelist;
        freelist = freelist->next;
        return temp;
    }
    
    void operator delete(void* ptr)
    {
        ((Link<E>*) ptr)->next = freelist;
        freelist = (Link<E>*)ptr;
    }
    
};

template<typename E>
Link<E>* Link<E>::freelist = NULL;
#endif

LQueue.h 串列佇列實作

#ifndef LQUEUE_H
#define LQUEUE_H

#include"Queue.h"
#include"Link.h"
#include<iostream>
#include<cstdlib>

using namespace std;
const int defaultSize = 10;

template<typename E>
class LQueue : public Queue<E>
{
private:
    Link<E>* front;
    Link<E>* rear;
    int      size;
public:    
    LQueue(int sz = defaultSize)
    {
        front = rear = (Link<E>*)new Link<E>;
        size = 0;
    }
    
    ~LQueue()
    {
        clear(); delete front;
    }
    
    void clear()
    {
        Link<E>* temp;
        while(front != rear)
        {
            temp = front ;
            front = front->next;
            delete temp;
        }
        size = 0;
    }
    
    void enqueue(const E& it)
    {
        rear->next = (Link<E>*)new Link<E>(it,NULL);
        rear =rear->next;
        size++;
    }
    
    E dequeue()
    {
        if(size == 0)
        {
            cerr<<"Queue is empty"<<endl;
            exit(-1);
        }
        Link<E>* temp = front->next;
        E it = temp->element;
        front->next = temp->next;
        if(rear == temp) rear = front;
        delete temp;
        size--;
        return it;
    }
    
    const E& frontValue()const
    {
        return front->next->element;
    }
    
    int length() const
    {
        return size;
    }
};
#endif