3.1 栈

3.1.1 栈的基本概念

只允许在一端进行插入或删除操作的线性表。

3.1.2 栈的顺序存储结构

typedef struct{
  int data[50];
  int top;
}Sqstack;

3.1.3 栈的链式存储结构

typedef struct Linknode{
  int data;
  struct Linknode *next；
}*LiStack;

二、实现 stack

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
class Stack {
public:
    void push(const T &value) {
        data.push_back(value); // 将元素插入 vector 尾部
    }

    void pop() {
        if (empty()) {
            throw underflow_error("pop from empty stack"); // 如果栈为空，则抛出异常
        }
        data.pop_back(); // 移除 vector 尾部元素
    }

    T &top() {
        if (empty()) {
            throw underflow_error("top from empty stack"); // 如果栈为空，则抛出异常
        }
        return data.back(); // 返回 vector 尾部元素
    }

    bool empty() const {
        return data.empty(); // 判断 vector 是否为空
    }

private:
    vector<T> data; // 用 vector 存储栈中的元素
};