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

串列堆疊與鏈結串列具有一定的相似性, 堆疊在操作上是受到限制的線型表

根據堆疊的基本特點 :

• Last In First Out (LIFO)

可以將鏈結串列改造為串列堆疊

本文中的均為 top 指標指向尾部的串列堆疊. 從性質上分析, 這是一種方便推入而不方便彈出的堆疊; 當然, 你亦可以寫成 top 指標指向頭部的串列堆疊, 則性質與上述相反

堆疊的具體操作在之前已經講過, 這裏就不再繼續講解了

首先用一張 SVG 圖像描述串列堆疊

根據圖像描述, 所有的推入彈出都是針對 top 指標的操作. 為了方便判斷, 我將串列堆疊的第一個節點的數據設定為空, 即不寫入數據

下面是本人寫的關於串列堆疊的原始碼

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

LinkedStack.hpp :

#ifndef LINKEDSTACK_LINKEDSTACK_HPP
#define LINKEDSTACK_LINKEDSTACK_HPP

#include <iostream>
#include <cstdlib>

namespace LinkedStack {
    using std::cout;
    using std::cin;
    using std::endl;
    class Node {
    protected :
        int data;
        Node *next;
    public :
        Node();
        ~Node();
        void insertData(int data);
        void insertNext(Node *next);
        Node *getNext();
        int getData();
    };
    class Stack : protected Node {
    private :
        bool isEmpty();
    protected :
        Node *first;
        Node *top;
    public :
        Stack();
        ~Stack();
        long long int getTop();
        void push(int data);
        void pop();
        void clearStack();
        void showStack();
    };
}


#endif //LINKEDSTACK_LINKEDSTACK_HPP

LinkedStack.cpp :

#include "LinkedStack.hpp"

using namespace LinkedStack;

Node::Node() {

}
Node::~Node() {

}
void Node::insertNext(Node *next) {
    this->next = next;
}
void Node::insertData(int data) {
    this->data = data;
}
int Node::getData() {
    return this->data;
}
Node *Node::getNext() {
    return this->next;
}
Stack::Stack() {
    this->first = new Node();
    this->first->insertNext(nullptr);
    this->top = this->first;
}
Stack::~Stack() {
    this->top = nullptr;        //To avoid a pointer is going to be deleted twice.
    auto *node = this->first;
    /* Delete all node to avoid Memory Leaks. */
    while(node->getNext() != nullptr) {
        auto *deleteNode = node;
        node = node->getNext();
        delete deleteNode;
        deleteNode = nullptr;
    }
    delete node;
}
bool Stack::isEmpty() {
    if(this->top == this->first) {
        return true;
    }
    return false;
}
long long int Stack::getTop() {
    if(this->isEmpty()) {
        return INT64_MIN;
    }
    return (long long int)top->getData();
}
void Stack::push(int data) {
    auto *node = new Node();
    node->insertData(data);
    node->insertNext(nullptr);
    this->top->insertNext(node);        //Insert new node from the tail of stack.
    top = node;     //Top point to new node.
}
void Stack::pop() {
    if(this->isEmpty()) {
        cout << "The stack is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    Node *node = this->first;
    while(node->getNext() != this->top) {
        node = node->getNext();
    }
    node->insertNext(nullptr);
    cout << "The element : " << this->top->getData() << " has been popped!" << endl;
    /* Delete top and reset top. */
    delete this->top;
    this->top = node;
    node = nullptr;
    delete node;
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Stack::clearStack() {
    this->top = this->first;
    Node *node = this->first->getNext();
    /* If node is not nullptr, then delete the node after node. */
    if(node) {
        while(node->getNext() != nullptr) {
            Node *temp = node;
            node = node->getNext();
            delete temp;
            temp = nullptr;
        }
    }
    delete node;
    node = nullptr;
    this->first->insertNext(nullptr);       //Set first node's next to nullptr.
}
void Stack::showStack() {
    int count = 0;      //To count the number of stack.
    Node *node = this->first;
    /* Count Module */
    while(node->getNext() != nullptr) {
        node = node->getNext();
        count++;
    }
    if(!count) {
        return;
    }
    /* Print the index of elements. */
    cout << "Index : \t";
    for(int i = 1; i <= count; i++) {
        cout << i << "\t";
    }
    /* Print all elements. */
    cout << endl << "Element : \t";
    node = this->first;
    while(node->getNext() != nullptr) {
        node = node->getNext();
        cout << node->getData() << "\t";
    }
    cout << endl;
    node = nullptr;
    delete node;
}

main.cpp :

#include "LinkedStack.hpp"

using namespace LinkedStack;

void menu();

int main(int argc, char *argv[]) {
    auto *stack = new Stack();
    long long int top;
    int data;
    int choice;
    do {
        system("clear");
        stack->showStack();
        menu();
        cin >> choice;
        switch(choice) {
            case 1 :
                top = stack->getTop();
                if(top == INT64_MIN) {
                    cout << "The stack is empty!" << endl;
                    cout << "Press any key to continue!" << endl;
                }else {
                    cout << "The top element : " << top << endl;
                    cout << "Press any key to continue!" << endl;
                }
                getchar();
                getchar();
                break;
            case 2 :
                cout << "Please enter the element you want to push : ";
                cin >> data;
                stack->push(data);
                break;
            case 3 :
                stack->pop();
                break;
            case 4 :
                stack->clearStack();
                break;
            case 5 :
                delete stack;
                exit(0);
            default :
                break;
        }
    }while(choice != 5);
}
void menu() {
    cout << "------------------------------------------------" << endl;
    cout << "1. Get the top element of stack." << endl;
    cout << "2. Push." << endl;
    cout << "3. Pop." << endl;
    cout << "4. Clear the stack." << endl;
    cout << "5. Exit." << endl;
    cout << "------------------------------------------------" << endl;
    cout << "Please enter your choice : ";
}