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

栈和队列同样属于线性表, 但却是一种比较特殊的线性表. 因为它们对于输入和输出会有一定的限制, 所以是限定性线性表

栈里面有两个名词是需要了解的 :

• 栈顶 (Top) : 表中允许输入与输出的一端
• 栈底 (Bottom) : 栈顶对应的表中的另外一端

如果对于线性表的理解比较深刻的话, 栈写起来会非常简单. 因为对应起非限定性线性表, 栈只允许在顶部进行插入以及删除操作, 栈顶下面到栈底的元素都是在栈顶不动之前不允许动的

下面一张 SVG 图表示了 Stack 中的进栈与出栈操作 :

因为我们是以数组的形式存储栈, 所以上面用了类似于数组的方式表示. 实际上, 栈以向上的方式叠加更为直观

另外需要指出的是, 由于使用的是 C++, 所以不管是图中还是文中的 top 都为数组指针

1. 进栈

首先需要判断栈是否为满, 如果栈满还要进栈, 会造成溢出. 如果栈不满, 则在最后一个元素后面添加这个元素, 并且让 top 指针指向这个元素即可

2. 出栈

首先需要判断栈是否为空, 如果栈不空, 那么直接让 top 指针指向的元素 *top 出栈即可, 然后让 top 指针指向出栈元素的前一个元素即可

这次的代码经过重构并且加上了注释, 不过注释是英文的. 之前 top 用的非数组指针

这次的重构也让我认识到了之前的代码的注释问题, 之后如果有时间, 我将会对之前的所有代码进行重构. 该有注释的地方我会加上注释, 并且我将会考虑对于注释写一篇专门的文章

下面给出源代码, 有错误欢迎指出

分成三个文件, 其中一个是 Class 源文件, 分为 .hpp 文件和 .cpp 文件, 另外一个是 main 函数文件

Stack.hpp :

#ifndef STACK_STACK_HPP
#define STACK_STACK_HPP

#include <iostream>
#include <cstdlib>

namespace SequentialStack {
    using std::cin;
    using std::cout;
    using std::endl;
    class Stack {
    private :
        bool isEmpty();
        bool isFull();
    protected :
        int *arr;
        int *top;        //The pointer of arr
        int maxSize;        //The max size of stack, designated by users
    public :
        Stack(int maxSize);
        ~Stack();
        long long int getTop();     //Get the top element from the stack
        void push(int data);
        void pop();
        void clearStack();
        void showStack();
    };
}

Stack.cpp :

#include "Stack.hpp"

using namespace SequentialStack;

Stack::Stack(int maxSize) {
    this->top = nullptr;
    this->arr = new int[maxSize];
    this->maxSize = maxSize;
}
Stack::~Stack() {
    this->top = nullptr;
    delete []this->arr;
    delete this->top;
}
bool Stack::isEmpty() {
    if(!this->top) {
        return true;
    }
    return false;
}
bool Stack::isFull() {
    if(this->arr + this->maxSize - 1 == this->top) {
        return true;
    }
    return false;
}
long long int Stack::getTop() {
    if(this->isEmpty()) {
        return INT64_MIN;
    }
    return (long long int)*this->top;
}
void Stack::push(int data) {
    if(this->isFull()) {
        cout << "The stack is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    /* If top pointer is nullptr, let it point to the first position of arr. */
    if(this->isEmpty()) {
        this->top = this->arr;
        *this->top = data;
        return;
    }
    this->top++;
    *this->top = data;
}
void Stack::pop() {
    if(isEmpty()) {
        cout << "The stack is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    cout << "The top element : " << *this->top << " has been popped!" << endl;
    this->top--;
    /* If all element has been popped, set top pointer as nullptr. */
    if(this->top < this->arr) {
        this->top = nullptr;
    }
    cout << "Press any key to continue!" << endl;
    getchar();
    getchar();
}
void Stack::clearStack() {
    this->top = nullptr;
}
void Stack::showStack() {
    if(this->isEmpty()) {
        return;
    }
    cout << "Index : \t";
    int count = 0;      //size of the arr
    int *p = this->arr;     //traversal pointer
    while(p != this->top + 1) {
        count++;
        cout << count << "\t";
        p++;
    }
    p = nullptr;
    delete p;
    cout << endl << "Element : \t";
    for(int *i = this->arr; i <= this->top; i++) {
        cout << *i << "\t";
    }
    cout << endl;
}

main.cpp :

#include "Stack.hpp"

using namespace SequentialStack;

void menu();

int main(int argc, char *argv[]) {
    int maxSize;        //The max size of stack, input by users
    Stack *stack;
    long long int top;      //The top element of stack
    int data;       //Element need be pushed, input by users
    cout << "Please enter the max size of stack : ";
    cin >> maxSize;
    stack = new Stack(maxSize);
    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 is : " << 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);        //Exit code : 0
            default :
                break;
        }
    }while(choice != 5);
}
void menu() {
    cout << "-----------------------------------------------------------" << endl;
    cout << "1. Get the top element of the 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 : ";
}