队列的实现

顺序队列

循环队列：（此代码没有 队满后进行扩大队 的操作）

#include <iostream>
using namespace std;

template <class T>
class Queue {
private:
    T* queue;
    int front;//队首元素下标
    int rear;//队尾元素后一个空位置下标
    int maxsize;
public:
    Queue(int max = 10);
    bool IsEmpty();
    T& GetFront();
    T& GetRear();
    void Show();
    bool enQueue(T data);
    bool deQueue();

};

template<class T>
Queue<T>::Queue(int max) {
    queue = new T[max];
    front = 0;
    rear = 0;
    maxsize = max;
}

template<class T>
inline bool Queue<T>::IsEmpty() {
    return front == rear;
}

template<class T>
T& Queue<T>::GetFront() {
    try {
        if (IsEmpty())throw "Queue is empty! Can't get element";
    }
    catch (char const* s) {
        cout << s << endl;
    }
    return queue[front];
}

template<class T>
T& Queue<T>::GetRear() {
    try {
        if (IsEmpty())throw "Queue is empty! Can't get element";
    }
    catch (char const* s) {
        cout << s << endl;
    }
    return queue[(rear - 1 + maxsize) % maxsize];
}

template<class T>
void Queue<T>::Show() {
    try {
        if (IsEmpty())throw "Queue is empty! Can't show element";
    }
    catch (char const* s) {
        cout << s << endl;
    }
    for (int i = 0; i < (rear - 1 + maxsize) % maxsize - front + 1; i++) {
        cout << queue[front + i] << " ";
    }
    cout << endl;
}

template<class T>
bool Queue<T>::enQueue(T data) {
    //队满
    if ((rear + 1) % maxsize == front) {
        return false;
    }
    else {
        queue[rear] = data;
        rear = (rear + 1) % maxsize;
        return true;
    }
}

template<class T>
bool Queue<T>::deQueue() {
    //队空
    if (IsEmpty()) {
        return false;
    }
    else {
        front = (front + 1) % maxsize;
        return true;
    }
}

int main()
{
    Queue<int> queue;
    int table[5] = { 1,2,3,4,5 };
    for (int i = 0; i < 5; i++) {
        queue.enQueue(table[i]);
    }
    
    queue.deQueue();queue.deQueue();
    queue.enQueue(10);
    queue.Show();
    cout<<queue.GetRear();
}

队满后扩大队的操作可参考：https://www.bilibili.com/video/BV1AW411k7rw?p=13
（视频中，front是指向第一个元素的前面的空位置，rear指向最后一个元素，和我的有所不同）

链式队列

#include <iostream>
using namespace std;
template <class T> class Queue;

template <class T>
class Node {
public:
    friend class Queue<T>;
    Node() {};
    Node(T num) {
        data = num;
        next = NULL;
    }
private:
    T data;
    Node<T>* next;
};

template <class T>
class Queue {
public:
    Queue() {
        front = NULL;
        rear = NULL;
    }
    void enQueue(T num);
    void deQueue();
    T& GetRear();
    T& GetFront();
    void show();
    bool IsEmpty();
private:
    Node<T>* front;
    Node<T>* rear;
};

template <class T>
void Queue<T>::enQueue(T num){
    Node<T>* pnew = new Node<T>(num);
    if ( !front ) {
        front = pnew;
        rear = pnew;
    }
    else {
        rear->next = pnew;
        rear = pnew;
    }
}

template <class T>
void Queue<T>::deQueue() {
    Node<T>* p = front;
    front = p->next;
    p->next = NULL;
    delete p;
}


template <class T>
T& Queue<T>::GetFront() {
    try {
        if (IsEmpty()) throw "error! The Queue is empty!";
    }
    catch (const char* str) {
        cout << str << endl;
    }
    
    return front->data;
}

template <class T>
T& Queue<T>::GetRear() {
    try {
        if (IsEmpty()) throw "error! The Queue is empty!";
    }
    catch (const char* str) {
        cout << str << endl;
    }

    return rear->data;
}

template <class T>
void Queue<T>::show() {
    try {
        if (IsEmpty()) throw "error! The Queue is empty!";
    }
    catch (const char* str) {
        cout << str << endl;
    }
    Node<T>* p = front;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }cout << endl;
}

template <class T>
bool Queue<T>::IsEmpty() {
    return front == NULL;
}

int main()
{
    Queue<char> queue;
    char table[5] = { 'A','B','C','D','E' };
    for (int i = 0; i < 5; i++) {
        queue.enQueue(table[i]);
    }
    queue.show();
    queue.deQueue();
    queue.show();
    cout<<"front:"<<queue.GetFront()<<endl;
    cout << "rear:" << queue.GetRear() << endl;
    queue.deQueue(); queue.deQueue(); queue.deQueue(); queue.deQueue();
    queue.show();
    return 0;
}