$\Huge\color{orchid}{点击此处获取更多干货}$

两种方式实现

栈和队列其实就是限制了存取位置的线性表，在STL中存在stack（栈）和queue（队列），它们都是deque（双端队列）的配接器。栈和队列部分一共分为三个阶段：无单调性、有单调性、综合应用。目前处于第一阶段，暂不使用deque

对于栈来说，存取点限制在了表的一端，插入和删除都只能在同一端进行。因此，允许进行插入和删除操作的那一端被称为栈口或者栈顶，另一端则为栈底。如果将$\{1,2,3,4,5\}$按顺序插入栈，那么从中挨个取出时，顺序就为$\{5,4,3,2,1\}$，因此栈属于一种后进先出（LIFO）型数据结构。

C++ 代码

顺序表和链表都可以实现栈，下面给出两种实现方式，细节可参阅注释

//顺序存储
template<class Elem>
class SequenceStack {
private:
    Elem* base;//用作栈本体的顺序表（数组）
    size_t top;//栈顶索引，可直接从此处取得栈顶元素
public:
    SequenceStack() {
        base = new Elem[cntCmd];
        top = 0ull;//初始栈顶为0
    }

    ~SequenceStack() {
        delete[] base;
    }

    //插入
    void push(Elem e) {
        base[++top] = e;//先后移栈顶，然后插入元素
    }

    //删除
    void pop() {
        //首先要判断栈空不空，如果对空栈执行pop()需要抛出异常
        if (top == 0) {
            throw logic_error("back() called on an empty deque");
        }
        //删除元素，只需要前移栈顶
        top--;
    }

    //判空
    bool empty() {
        //0代表空
        return top == 0;
    }

    //取栈顶元素
    Elem top() {
        //同样，对空栈取栈顶元素需要抛出异常
        if (top == 0) {
            throw logic_error("back() called on an empty deque");
        }
        return base[top];
    }
};

//链式存储（双向链表）
template<class Elem> 
class LinkedStack {
private:
    //bottom相当于头节点用来判空，top是栈顶，del用于析构
    Node<Elem>* bottom = nullptr, * del = nullptr, * top;
public:
    LinkedStack() {
        bottom = new Node<Elem>(0);
        top = bottom;
    }

    ~LinkedStack() {
        while (bottom != nullptr) {
            del = bottom;
            bottom = bottom->next;
            delete del;
            del = nullptr;
        }
    }

    //插入
    void push(Elem e) {
        //构造节点
        Node<Elem>* cur = new Node<Elem>(e);
        //连接两节点之间的指针
        top->next = cur;
        cur->prev = top;
        //后移top
        top = top->next;
    }

    //删除
    void pop() {
        if (top->prev == nullptr) {
            throw logic_error(("back() called on an empty list"));
        }
        //准备删除
        del = top;
        //前移top
        top = top->prev;
        //将当前栈顶和待删节点之间的指针断开
        del->prev = nullptr;
        top->next = nullptr;
        //析构并置空del
        delete del;
        del = nullptr;
    }

    bool empty() {
        //链表不是循环的，只要前驱为空就说明top指向了bottom即空栈
        return top->prev == nullptr;
    }

    Elem top() {
        if (top->prev == nullptr) {
            throw logic_error("back() called on an empty list");
        }
        //直接返回top节点的元素值
        return top->val;
    }
};

可以写一个类似的测试函数，让main函数执行后返回：

auto testStack = []()->int {
        cin >> cntCmd;
        LinkedStack<int> stk;
        string op;
        int x;
        while (cntCmd--) {
            cin >> op;
            if (op == "push") {
                cin >> x;
                stk.push(x);
            }
            else if (op == "pop") {
                //函数如果抛出了异常，需要用try...catch...处理
                try {
                    stk.pop();
                }
                catch (logic_error e) {
                    //MessageBoxA(GetForegroundWindow(), e.what(), "Error", 3);
                    cerr << "\n" << e.what() << endl;
                    return 3;
                }
            }
            else if (op == "empty") {
                cout << (stk.empty() ? "YES" : "NO") << endl;
            }
            else if (op == "query") {
                try {
                    cout << stk.top() << endl;
                }
                catch (logic_error e) {
                    //MessageBoxA(GetForegroundWindow(), e.what(), "Error", 3);
                    cerr << "\n" << e.what() << endl;
                    return 3;
                }
            }
        }
        return 0;
    };