資料結構 : 雙向佇列 (雙端佇列)

C++資料結構

Jonny 自創文章 C++ 2018-03-08 2,656 0 0

本文已經過時, 最新的重構文章請點擊 : 《【資料結構 – 重構】雙向佇列 (雙端佇列) [上篇]》

雙向佇列是一種限定的線型結構. 儘管名字中存在佇列, 但實際並不是佇列. 它是一種同時具有佇列和堆疊性質的抽象數據類型. 它可以同時在前端或者後端插入或者彈出. 當然, 所有的操控都限於兩端

在實際的應用中, 除去不受限制的雙向佇列, 還有彈出受限制的雙向佇列和插入受限制的雙向佇列

輸出受限制 : 一端只允許插入, 另一端允許插入或者彈出
輸入受限制 : 一端只允許彈出, 另外一端允許插入和彈出
不受限制 : 兩頓都允許插入和彈出

不受限制的雙向佇列, 前端禁止操控即是一個堆疊, 當然實際運用到雙向佇列的話, 基本不會這樣去禁止, 因為可以直接用 stack 來處理

我在寫雙向佇列的時候, 將情況分為 5 種 :

前端彈出受限制
前端插入受限制
後端彈出受限制
後端插入受限制
兩端都不受限制

這些都可以通過一個類別和不同的選單去完成. 當然, 你可以使用不同的類別和同一個選單和提示完成

我們使用一張 SVG 圖像來表示雙向佇列

在本次的代碼中, 使用到了 STL (C++ 的標準程式庫) 中的 vector. 因為如果使用陣列來表示 Deque 的話, 程式碼會顯得很繁瑣. 並且這次並沒有使用註解, 因為代碼形式和之前的差別不大

下面是本人寫的原始碼

如若有錯誤存在, 可以聯絡我或者直接添加評論. 關於原始碼的註解, 已經給的比較全面, 還有不明白的可以直接評論, 對於註解的建議也可以提出. 直接讀原始碼的函式名稱或者變數名稱可以直接了解作用

Deque.hpp :

#ifndef DEQUE_DEQUE_HPP
#define DEQUE_DEQUE_HPP

#include <iostream>
#include <cstdlib>
#include <vector>

namespace Deque {
    using std::cin;
    using std::cout;
    using std::endl;
    using std::vector;
    class Queue {
    private :
        bool isEmpty();
    protected :
        vector<int> vec;
    public :
        Queue();
        ~Queue();
        long long int getFirst();
        long long int getLast();
        void firstEnter(int data);
        void lastEnter(int data);
        void firstOut();
        void lastOut();
        void clearDeque();
        void clearVector();
        void showDeque();
    };
}

#endif //DEQUE_DEQUE_HPP

Deque.cpp :

#include "Deque.hpp"

using namespace Deque;

Queue::Queue() {

}
Queue::~Queue() {

}
bool Queue::isEmpty() {
    if(this->vec.empty()) {
        return true;
    }
    return false;
}
long long int Queue::getFirst() {
    if(this->isEmpty()) {
        return INT64_MIN;
    }
    return (long long int)this->vec.front();
}
long long int Queue::getLast() {
    if(this->isEmpty()) {
        return INT64_MIN;
    }
    return (long long int)this->vec.back();
}
void Queue::firstEnter(int data) {
    this->vec.insert(this->vec.begin(), data);
}
void Queue::lastEnter(int data) {
    this->vec.push_back(data);
}
void Queue::firstOut() {
    if(this->isEmpty()) {
        cout << "The deque is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    cout << "The element : " << this->vec.front() << " has been out!" << endl;
    this->vec.erase(this->vec.begin());
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Queue::lastOut() {
    if(this->isEmpty()) {
        cout << "The deque is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    cout << "The element : " << this->vec.back() << " has been out!" << endl;
    this->vec.pop_back();
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Queue::clearDeque() {
    this->vec.clear();
}
void Queue::clearVector() {
    vector<int> tempVector;
    tempVector.swap(this->vec);
}
void Queue::showDeque() {
    if(this->isEmpty()) {
        return;
    }
    int size = this->vec.size();
    cout << "Index : \t";
    for(int i = 1; i <= size; i++) {
        cout << i << "\t";
    }
    cout << endl << "Element : \t";
    for(vector<int>::iterator iterator = this->vec.begin(); iterator < this->vec.end(); iterator++) {
        cout << *iterator << "\t";
    }
    cout << endl;
}

main.cpp :

#include "Deque.hpp"

#define UNLIMITED_QUEUE 1
#define FIRST_OUT_LIMITED_QUEUE 2
#define FIRST_ENTER_LIMITED_QUEUE 3
#define LAST_OUT_LIMITED_QUEUE 4
#define LAST_ENTER_LIMITED_QUEUE 5

using namespace Deque;

void unlimitedQueueMenu();
void unlimitedQueueLoop(Queue *deque);
void firstOutLimitedQueueMenu();
void firstOutLimitedQueueLoop(Queue *deque);
void firstEnterLimitedQueueMenu();
void firstEnterLimitedQueueLoop(Queue *deque);
void lastOutLimitedQueueMenu();
void lastOutLimitedQueueLoop(Queue *deque);
void lastEnterLimitedQueueMenu();
void lastEnterLimitedQueueLoop(Queue *deque);

int main(int argc, char *argv[]) {
    int choice;
    auto *deque = new Queue;
    cout << "-------------------------------------" << endl;
    cout << "1. Unlimited Queue" << endl;
    cout << "2. First Out Limited Queue" << endl;
    cout << "3. First Enter Limited Queue" << endl;
    cout << "4. Last Out Limited Queue" << endl;
    cout << "5. Last Enter Limited Queue" << endl;
    cout << "-------------------------------------" << endl;
    cout << "Please choose what queue you want to use : ";
    cin >> choice;
    switch(choice) {
        case UNLIMITED_QUEUE :
            unlimitedQueueLoop(deque);
            break;
        case FIRST_OUT_LIMITED_QUEUE :
            firstOutLimitedQueueLoop(deque);
            break;
        case FIRST_ENTER_LIMITED_QUEUE :
            firstEnterLimitedQueueLoop(deque);
            break;
        case LAST_OUT_LIMITED_QUEUE :
            lastOutLimitedQueueLoop(deque);
            break;
        case LAST_ENTER_LIMITED_QUEUE :
            lastEnterLimitedQueueLoop(deque);
            break;
        default :
            break;
    }
}
void unlimitedQueueMenu() {
    cout << "-------------------------------------" << endl;
    cout << "1. Get the first element." << endl;
    cout << "2. Get the last element." << endl;
    cout << "3. First enter." << endl;
    cout << "4. Last enter." << endl;
    cout << "5. First out." << endl;
    cout << "6. Last out." << endl;
    cout << "7. Clear the deque." << endl;
    cout << "8. Exit." << endl;
    cout << "-------------------------------------" << endl;
    cout << "Please enter your choice : ";
}
void unlimitedQueueLoop(Queue *deque) {
    int choice;
    long long int dataGet;
    int data;
    do {
        system("clear");
        deque->showDeque();
        unlimitedQueueMenu();
        cin >> choice;
        switch(choice) {
            case 1 :
                dataGet = deque->getFirst();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 2 :
                dataGet = deque->getLast();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                deque->firstEnter(data);
                break;
            case 4 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                deque->lastEnter(data);
                break;
            case 5 :
                deque->firstOut();
                break;
            case 6 :
                deque->lastOut();
                break;
            case 7 :
                deque->clearDeque();
                break;
            case 8 :
                deque->clearVector();
                delete deque;
                exit(0);
            default :
                break;
        }
    }while(choice != 8);
}
void firstOutLimitedQueueMenu() {
    cout << "-------------------------------------" << endl;
    cout << "1. Get the first element." << endl;
    cout << "2. Get the last element." << endl;
    cout << "3. First enter." << endl;
    cout << "4. Last enter." << endl;
    cout << "5. Last out." << endl;
    cout << "6. Clear the deque." << endl;
    cout << "7. Exit." << endl;
    cout << "-------------------------------------" << endl;
    cout << "Please enter your choice : ";
}
void firstOutLimitedQueueLoop(Queue *deque) {
    int choice;
    long long int dataGet;
    int data;
    do {
        system("clear");
        deque->showDeque();
        firstOutLimitedQueueMenu();
        cin >> choice;
        switch(choice) {
            case 1 :
                dataGet = deque->getFirst();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 2 :
                dataGet = deque->getLast();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                deque->firstEnter(data);
                break;
            case 4 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                deque->lastEnter(data);
                break;
            case 5 :
                deque->lastOut();
                break;
            case 6 :
                deque->clearDeque();
                break;
            case 7 :
                deque->clearVector();
                delete deque;
                exit(0);
            default :
                break;
        }
    }while(choice != 7);
}
void firstEnterLimitedQueueMenu() {
    cout << "-------------------------------------" << endl;
    cout << "1. Get the first element." << endl;
    cout << "2. Get the last element." << endl;
    cout << "3. Last enter." << endl;
    cout << "4. First out." << endl;
    cout << "5. Last out." << endl;
    cout << "6. Clear the deque." << endl;
    cout << "7. Exit." << endl;
    cout << "-------------------------------------" << endl;
    cout << "Please enter your choice : ";
}
void firstEnterLimitedQueueLoop(Queue *deque) {
    int choice;
    long long int dataGet;
    int data;
    do {
        system("clear");
        deque->showDeque();
        firstEnterLimitedQueueMenu();
        cin >> choice;
        switch(choice) {
            case 1 :
                dataGet = deque->getFirst();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 2 :
                dataGet = deque->getLast();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                deque->lastEnter(data);
                break;
            case 4 :
                deque->firstOut();
                break;
            case 5 :
                deque->lastOut();
                break;
            case 6 :
                deque->clearDeque();
                break;
            case 7 :
                deque->clearVector();
                delete deque;
                exit(0);
            default :
                break;
        }
    }while(choice != 7);
}
void lastOutLimitedQueueMenu() {
    cout << "-------------------------------------" << endl;
    cout << "1. Get the first element." << endl;
    cout << "2. Get the last element." << endl;
    cout << "3. First enter." << endl;
    cout << "4. Last enter." << endl;
    cout << "5. First out." << endl;
    cout << "6. Clear the deque." << endl;
    cout << "7. Exit." << endl;
    cout << "-------------------------------------" << endl;
    cout << "Please enter your choice : ";
}
void lastOutLimitedQueueLoop(Queue *deque) {
    int choice;
    long long int dataGet;
    int data;
    do {
        system("clear");
        deque->showDeque();
        lastOutLimitedQueueMenu();
        cin >> choice;
        switch(choice) {
            case 1 :
                dataGet = deque->getFirst();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 2 :
                dataGet = deque->getLast();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                deque->firstEnter(data);
                break;
            case 4 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                deque->lastEnter(data);
                break;
            case 5 :
                deque->firstOut();
                break;
            case 6 :
                deque->clearDeque();
                break;
            case 7 :
                deque->clearVector();
                delete deque;
                exit(0);
            default :
                break;
        }
    }while(choice != 7);
}
void lastEnterLimitedQueueMenu() {
    cout << "-------------------------------------" << endl;
    cout << "1. Get the first element." << endl;
    cout << "2. Get the last element." << endl;
    cout << "3. First enter." << endl;
    cout << "4. First out." << endl;
    cout << "5. Last out." << endl;
    cout << "6. Clear the deque." << endl;
    cout << "7. Exit." << endl;
    cout << "-------------------------------------" << endl;
    cout << "Please enter your choice : ";
}
void lastEnterLimitedQueueLoop(Queue *deque) {
    int choice;
    long long int dataGet;
    int data;
    do {
        system("clear");
        deque->showDeque();
        lastEnterLimitedQueueMenu();
        cin >> choice;
        switch(choice) {
            case 1 :
                dataGet = deque->getFirst();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 2 :
                dataGet = deque->getLast();
                if(dataGet == INT64_MIN) {
                    cout << "The deque is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The first element : " << dataGet << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element you want to enter : ";
                cin >> data;
                deque->firstEnter(data);
                break;
            case 4 :
                deque->firstOut();
                break;
            case 5 :
                deque->lastOut();
                break;
            case 6 :
                deque->clearDeque();
                break;
            case 7 :
                deque->clearVector();
                delete deque;
                exit(0);
            default :
                break;
        }
    }while(choice != 7);
}

自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《資料結構 : 雙向佇列 (雙端佇列)》https://jonny.vip/2018/03/08/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e9%9b%99%e5%90%91%e4%bd%87%e5%88%97/

Like (0)