資料結構2021溫習篇——隊列(5a)

前言

本節我們讨論隊列。考慮有隊頭”指針“和隊尾"指針"的情況。

目錄：

資料結構2021溫習篇——概況(1)

資料結構2021溫習篇——線性表(2)

資料結構2021溫習篇——連結清單(3)

資料結構2021溫習篇——棧(4a)_線性存儲

資料結構2021溫習篇——隊列(5a)

資料結構2021溫習篇——堆(6)

資料結構2021溫習篇——二叉樹(7a)

資料結構2021溫習篇——圖(7a)_鄰接矩陣

資料結構2021溫習篇——圖(7b)_鄰接表

資料結構2021溫習篇——圖(8)_并查集

資料結構2021溫習篇——圖(9)_排序

解析

定義一個隊列類:

template<class T>
class SeqQueue {
public:
    explicit SeqQueue(int sz = DefaultMaxSize);

    ~SeqQueue();

    bool EnQueue(T x);

    bool DeQueue();

    bool DeQueue(T &x);

    bool getFront(T &x);

    void makeEmpty();

    bool IsEmpty() const;

    bool IsFull() const;

    int getSize() const;

    void output() const;

private:
    int rear, front; // 對頭，隊尾下标
    T *elements; 
    int maxSize;
};
           

構造函數:

template<class T>
SeqQueue<T>::SeqQueue(int sz) {
    front = rear = 0;
    maxSize = sz;
    elements = new T[maxSize];
    if (elements == nullptr) {
        cerr << "配置設定記憶體錯誤" << endl;
        exit(1);
    }
}
           

将某個元素排到隊尾，即進隊操作：

template<class T>
bool SeqQueue<T>::EnQueue(T x) {
    if (IsFull())
        return false;
    elements[rear] = x;
    rear = (rear + 1) % maxSize;
    return true;
}
           

出隊操作，即将對頭元素出隊。(這裡要注意的是，其實記憶體中該數值還是存在的，隻是我們把對頭"指針"移動了，邏輯上該元素已經不屬于這個隊列了)

template<class T>
bool SeqQueue<T>::DeQueue() {
    if (IsEmpty())
        return false;
    front = (front + 1) % maxSize;//出隊靠對頭移動
    return true;
}
           

template<class T>
bool SeqQueue<T>::DeQueue(T &x) {
    if (IsEmpty())
        return false;
    x = elements[front];
    front = (front + 1) % maxSize;
    return true;
}
           

取隊頭, 由引用x變量帶出。

template<class T>
bool SeqQueue<T>::getFront(T &x) {
    if (IsEmpty())
        return false;
    x = elements[front];
    return true;
}
           

置空:

//隻是讓棧邏輯為空而已，沒有破話空間結構
template<class T>
void SeqQueue<T>::makeEmpty() {
    front = rear = 0;
}
           

判空:

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

判滿:

template<class T>
bool SeqQueue<T>::IsFull() const {
    return (rear + 1) % maxSize == front;
}
           

擷取隊列元素個數

template<class T>
int SeqQueue<T>::getSize() const {
    return (rear - front + maxSize) % maxSize;
}
           

周遊列印隊列元素的值

template<class T>
void SeqQueue<T>::output() const {
    cout << "from front to rear(先進靠右邊)" << endl;
    for(int i = front; i != rear; i = (i + 1) % maxSize)
        cout << elements[i] << " ";
    cout << endl;
}
           

完整代碼

//
// Created by Dell on 2019/12/19.
//
#include <iostream>

using namespace std;
const int DefaultMaxSize = 50;

template<class T>
class SeqQueue {
public:
    explicit SeqQueue(int sz = DefaultMaxSize);

    ~SeqQueue();

    bool EnQueue(T x);

    bool DeQueue();

    bool DeQueue(T &x);

    bool getFront(T &x);

    void makeEmpty();

    bool IsEmpty() const;

    bool IsFull() const;

    int getSize() const;

    void output() const;

private:
    int rear, front;
    T *elements;
    int maxSize;
};

template<class T>
SeqQueue<T>::SeqQueue(int sz) {
    front = rear = 0;
    maxSize = sz;
    elements = new T[maxSize];
    if (elements == nullptr) {
        cerr << "配置設定記憶體錯誤" << endl;
        exit(1);
    }
}

template<class T>
SeqQueue<T>::~SeqQueue() {
    if (elements != nullptr)
        delete[] elements;
}

template<class T>
bool SeqQueue<T>::EnQueue(T x) {
    if (IsFull())
        return false;
    elements[rear] = x;
    rear = (rear + 1) % maxSize;
    return true;
}

template<class T>
bool SeqQueue<T>::DeQueue() {
    if (IsEmpty())
        return false;
    front = (front + 1) % maxSize;//出隊靠對頭移動
    return true;
}

template<class T>
bool SeqQueue<T>::DeQueue(T &x) {
    if (IsEmpty())
        return false;
    x = elements[front];
    front = (front + 1) % maxSize;
    return true;
}

template<class T>
bool SeqQueue<T>::getFront(T &x) {
    if (IsEmpty())
        return false;
    x = elements[front];
    return true;
}

//隻是讓棧邏輯為空而已，沒有破話空間結構
template<class T>
void SeqQueue<T>::makeEmpty() {
    front = rear = 0;
}

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

template<class T>
bool SeqQueue<T>::IsFull() const {
    return (rear + 1) % maxSize == front;
}


template<class T>
int SeqQueue<T>::getSize() const {
    return (rear - front + maxSize) % maxSize;
}


template<class T>
void SeqQueue<T>::output() const {
    cout << "from front to rear(先進靠右邊)" << endl;
    for(int i = front; i != rear; i = (i + 1) % maxSize)
        cout << elements[i] << " ";
    cout << endl;
}


int main() {
    SeqQueue<int> s1;
    cout << "s1.IsEmpty(): " << s1.IsEmpty() << endl;
    cout << "s1.IsFull(): " << s1.IsFull() << endl;
    cout << "EnQueue 1 to 10 ..." << endl;
    s1.EnQueue(1);
    s1.EnQueue(2);
    s1.EnQueue(3);
    s1.EnQueue(4);
    s1.EnQueue(5);
    s1.EnQueue(6);
    s1.EnQueue(7);
    s1.EnQueue(8);
    s1.EnQueue(9);
    s1.EnQueue(10);
    cout << "s1.getSize(): " << s1.getSize() << endl;
    s1.output();

    cout << "s1.DeQueue()..." << endl;
    s1.DeQueue();
    int x;
    s1.DeQueue(x);
    cout << "DeQueue one more element, it is " << x << "."<< endl;
    s1.output();
}