[数据结构与算法]【数据结构】队列

今天复习了顺序表、栈、队列
明天复习堆与优先队列、二叉树

#include<iostream>
#include<exception>
using namespace std;


class OutOfRange:public exception {
public:
    const char* what()const throw() {
        return "ERROE! OUT OF Range.\n";
    }
};

class BadSize:public exception {
public:
    const char* what()const throw() {
        return "ERROR! BAD SIZE.\n";
    }
};


template<class T>
class Queue {
public:
    virtual bool isEmpty()const = 0;
    virtual bool isFull()const = 0;
    virtual void clear() = 0;
    virtual int size()const = 0;
    virtual void enQueue(const T& x) = 0;
    virtual T deQueue() = 0;
    virtual T getHead()const = 0;
};


template<class T>
class seqQueue : public Queue<T> {
private:
    T* data;
    int maxSize;
    int front, rear;
    void resize();
public:
    seqQueue(int initSize = 100);
    ~seqQueue() { delete[] data; }
    bool isEmpty()const { return front == rear; }
    bool isFull()const { return (rear + 1) % maxSize == front; }
    void clear() { front = rear = -1; }
    int size()const { return (rear - front + maxSize) % maxSize; }
    void enQueue(const T& x);
    T deQueue();
    T getHead()const { return data[front]; }
}; 

template<class T>
seqQueue<T>::seqQueue(int initSize) {
    if (initSize <= 0) throw BadSize();
    data = new T[initSize];
    maxSize = initSize;
    front = rear = -1;
}


template<class T>
void seqQueue<T>::enQueue(const T& x) {
    if (isFull()) resize();
    rear = (rear + 1) % maxSize;
    data[rear] = x;
}

template<class T>
T seqQueue<T>::deQueue() {
    if (isEmpty()) throw OutOfRange();
    front = (front + 1) % maxSize;
    return data[front];
}

template<class T>
T seqQueue<T>::getHead()const {
    if (isEmpty()) throw OutOfRange();
    return data[(front + 1) % maxSize];
}

template<class T>
void seqQueue<T>::resize() {
    T* p = data;
    data = new T[maxSize * 2];
    for (int i = 1; i <= maxSize; ++i) {
        data[i] = p[(front + i) % maxSize];
    }
    maxSize *= 2;
    delete[] p;
}



template<class T>
class linkQueue:public Queue<T> {
private:
    struct LinkNode {
        int val;
        LinkNode* next;
        LinkNode(const T& x, LinkNode* p = nullptr): val(x), p(nullptr) {}
        LinkNode(const T& x): p(nullptr), val(x) {}
    };
    LinkNode* front, * rear;
public:
    linkNode() { front = nullptr; rear = nullptr;}
    ~linkNode() { clear(); }
    bool isEmpty()const { return front == nullptr; }
    void clear();
    int size()const;
    void enQueue(const T& x);
    T deQueue();
    T getHead()const;
};


template<class T>
void linkQueue<T>::clear() {
    LinkNode* del = front
    while (front) {
        del = front;
        front = front->next;
        delete del;
    }
    rear = nullptr;
}

template<class T>
int linkQueue<T>::size()const {
    LinkNode* node = front;
    int cnt = 0;
    while (node) {
        ++cnt;
        node = node->next;
    }
    return cnt;
}

template<class T>
void linkQueue<T>::enQueue(const T& x) {
    if (rear == nullptr) 
        front = rear = new node(x);
    else {
        LinkNode* p = new LinkNode(x);
        rear->next = p;
        rear = p;
    }
}

template<class T>
T linkQueue<T>::deQueue() {
    if (isEmpty()) throw OutOfRange();
    LinkNode* del = front;
    T value = front->val;
    front = front->next;
    if (front == nullptr)
        rear = nullptr;
    delete del;
    return val;
}

template<class T>
T linkQueue<T>::getHead()const {
    if (isEmpty()) throw OutOfRange();
    return front->val;
}