本文已經過時, 最新文章請點擊 : 《【資料結構 – 重構】堆疊與雙邊堆疊》

Google 的時候, 一直找不到對於雙向堆疊 (共享堆疊) 的資料, 不知錯誤是否出在搜尋的關鍵詞

雙向堆疊通常應用於一個應用程式需要兩個及以上的堆疊, 其原理為一個足夠大的儲存空間中放入幾個堆疊, 以此來解決堆疊溢位以及堆疊空間浪費的問題. 一個足夠大的存儲空間不一定只放兩個堆疊, 可能是多個的, 只要在類別中指出這些堆疊頂端元素 (top) 即可

除了多出了一個指標之外, 其它都是和陣列堆疊一樣的

下面用一張 SVG 圖像表示雙向堆疊

從圖像中可以知道, 雙向堆疊其實就是一個儲存空間的頭和底分別有一個陣列堆疊 (當然, 在實際的程式設計中, 是儲存在陣列中的)


下面是本人寫的關於雙向堆疊的原始碼

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

DoubleStack.hpp :

#ifndef DOUBLESTACK_DOUBLESTACK_HPP
#define DOUBLESTACK_DOUBLESTACK_HPP

#include <iostream>
#include <cstdlib>

namespace DoubleStack {
    using std::endl;
    using std::cin;
    using std::cout;
    class Stack {
    private :
        bool isHeadStackEmpty();
        bool isTailStackEmpty();
        bool isFull();
    protected :
        int *arr;       //The array is to save the data of stack.
        int headTop;
        int tailTop;
        int maxSize;        //The max size of stack. It is suggested to allocate a big space for double stack.
        Stack();        //Default constructor is protected to avoid anyone who is fucking calling it.
    public :
        Stack(int maxSize);
        ~Stack();
        long long int getHeadTop();
        long long int getTailTop();
        void headPush(int data);
        void tailPush(int data);
        void headPop();
        void tailPop();
        void clearHeadStack();
        void clearTailStack();
        void clearStack();      //Clean all of stack.
        void showStack();
    };
}

DoubleStack.cpp :

#include "DoubleStack.hpp"

using namespace DoubleStack;

Stack::Stack() {

}
Stack::Stack(int maxSize) {
    this->arr = new int[maxSize];
    this->maxSize = maxSize;
    this->headTop = -1;
    this->tailTop = maxSize;
}
Stack::~Stack() {
    delete []this->arr;
}
bool Stack::isFull() {
    if(this->headTop + 1 == this->tailTop) {
        return true;
    }
    return false;
}
bool Stack::isHeadStackEmpty() {
    if(this->headTop == -1) {
        return true;
    }
    return false;
}
bool Stack::isTailStackEmpty() {
    if(this->tailTop == this->maxSize) {
        return true;
    }
    return false;
}
long long int Stack::getHeadTop() {
    if(isHeadStackEmpty()) {
        return INT64_MIN;
    }
    return (long long int)this->arr[this->headTop];
}
long long int Stack::getTailTop() {
    if(isTailStackEmpty()) {
        return INT64_MIN;
    }
    return (long long int)this->arr[this->tailTop];
}
void Stack::headPush(int data) {
    if(isFull()) {
        cout << "The double stack is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    /* Push Module */
    this->headTop++;
    this->arr[this->headTop] = data;
}
void Stack::tailPush(int data) {
    if(isFull()) {
        cout << "The double stack is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    /* Push Module */
    this->tailTop--;
    this->arr[this->tailTop] = data;
}
void Stack::headPop() {
    if(isHeadStackEmpty()) {
        cout << "The head stack is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    /* Pop Module */
    cout << "The element : " << this->arr[this->headTop] << " has been popped!" << endl;
    this->headTop--;
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Stack::tailPop() {
    if(isTailStackEmpty()) {
        cout << "The tail stack is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    /* Push Module */
    cout << "The element : " << this->arr[this->tailTop] << " has been popped!" << endl;
    this->tailTop++;
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Stack::clearHeadStack() {
    this->headTop = -1;
}
void Stack::clearTailStack() {
    this->tailTop = this->maxSize;
}
void Stack::clearStack() {
    this->headTop = -1;
    this->tailTop = this->maxSize;
}
void Stack::showStack() {
    if(!isHeadStackEmpty()) {
        cout << "Head Stack Index : \t";
        /* Count the head stack's size */
        for(int i = 0; i <= this->headTop; i++) {
            cout << i + 1 << "\t";
        }
        cout << endl << "Head Stack Element : \t";
        for(int i = 0; i <= this->headTop; i++) {
            cout << this->arr[i] << "\t";
        }
        cout << endl;
    }
    if(!isTailStackEmpty()) {
        cout << "Tail Stack Index : \t";
        int count = this->maxSize - this->tailTop;
        /* Count the tail stack's size */
        for(int i = 1; i <= count; i++) {
            cout << i << "\t";
        }
        cout << endl << "Tail Stack Element : \t";
        for(int i = maxSize - 1; i >= this->tailTop; i--) {
            cout << this->arr[i] << "\t";
        }
        cout << endl;
    }
}

main.cpp :

#include "DoubleStack.hpp"

using namespace DoubleStack;

void menu();

int main(int argc, char *argv[]) {
    Stack *stack;
    int maxSize;
    cout << "Please enter the max size of stack : ";
    cin >> maxSize;
    stack = new Stack(maxSize);
    long long int top;
    int data;
    int choice;
    do {
        system("clear");
        stack->showStack();
        menu();
        cin >> choice;
        switch(choice) {
            case 1 :
                top = stack->getHeadTop();
                if(top == INT64_MIN) {
                    cout << "The top stack is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The element of head stack : " << top << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 2 :
                top = stack->getTailTop();
                if(top == INT64_MIN) {
                    cout << "The tail stack is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The element of head stack : " << top << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element you want to push : ";
                cin >> data;
                stack->headPush(data);
                break;
            case 4 :
                cout << "Please enter the element you want to push : ";
                cin >> data;
                stack->tailPush(data);
                break;
            case 5 :
                stack->headPop();
                break;
            case 6 :
                stack->tailPop();
                break;
            case 7 :
                stack->clearHeadStack();
                break;
            case 8 :
                stack->clearTailStack();
                break;
            case 9 :
                stack->clearStack();
                break;
            case 10 :
                delete stack;
                exit(0);
            default :
                break;
        }
    }while(choice != 10);
}
void menu() {
    cout << "----------------------------------------------------" << endl;
    cout << "1. Get the top element of head stack." << endl;
    cout << "2. Get the top element of tail stack." << endl;
    cout << "3. Push for head stack." << endl;
    cout << "4. Push for tail stack." << endl;
    cout << "5. Pop for head stack." << endl;
    cout << "6. Pop for tail stack." << endl;
    cout << "7. Clear head stack." << endl;
    cout << "8. Clear tail stack." << endl;
    cout << "9. Clear head stack and clear tail stack." << endl;
    cout << "10. Exit." << endl;
    cout << "----------------------------------------------------" << endl;
    cout << "Please enter your choice : ";
}