awe的程設筆記

Queue.h 佇列ＡＤＴ

#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

AQueue.h陣列佇列實作

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

using namespace std;

const int defaultSize = 10;

template <typename E>
class AQueue : public Queue<E>
{
private:
    int maxSize;
    int front;
    int rear;
    E* listArray;

public:
    AQueue(int size =defaultSize)
    {
        maxSize = size + 1;
        rear = 0;
        front = 1;
        listArray = new E[maxSize];
    }

    ~AQueue()
    {
        delete [] listArray;
    }

    void clear() {rear = 0 ; front = 1; }

    void enqueue(const E& item)
    {
        if( (rear +2 )% maxSize == front) // Queue is full
        {
            E* newListArray = new E [maxSize *2 -1];
            int newRear = 0;
            while(front != (rear+1) % maxSize)
            {
                newListArray[newRear++] = listArray[front];
                front = (front+1)% maxSize;
            }
            front = 0;
            rear = newRear -1;
            maxSize = maxSize* 2 -1;
            delete [] listArray;
            listArray = newListArray;
        }
        rear = (rear+1)%maxSize;
        listArray[rear] = item;
    }

    E dequeue()
    {
        if(length() != 0 )
        {
            E it = listArray[front];
            front = (front +1 )%maxSize;
            return it;
        }
        else
        {
            cerr<<"This Queue is empty"<<endl;
        }
    }

    const E& frontValue()const
    {
        if(length() != 0)
        return listArray[front];
        else
        cerr<<"This Queue is empty"<<endl;
    }

    virtual int length()const
    {
        return ((rear + maxSize - front + 1)% maxSize);
    }
};