栈的物理实现有 顺序栈 和 链式栈

一、顺序栈（Array-based Stack）

  1. 使用向量实现，本质上是顺序表的简化版
    • 栈有固定大小
  2. 关键是确定哪一端作为栈顶
  3. 注意上溢、下溢问题

类定义：

template <class T> 
class arrStack : public Stack <T> { 
private: // 栈的顺序存储
    int mSize; // 栈中最多可存放的元素个数
    int top; // 栈顶位置，应小于mSize
    T *st; // 存放栈元素的数组
public: // 栈的运算的顺序实现
    arrStack(int size) { // 创建一个给定长度的顺序栈实例
        mSize = size; 
        top = -1; 
        st = new T[mSize]; 
    } 
    arrStack() { // 创建一个顺序栈的实例
        top = -1; 
    }
    ~arrStack() { 
        delete [] st; 
    } 
    void clear() { 
        top = -1; 
    } // 清空栈
};

bool arrStack<T>::push(const T item) { // 入栈
    if (top == mSize-1) { // 栈已满
        cout << "栈满溢出" << endl; 
        return false; 
    } else { // 新元素入栈并修改栈顶指针
        st[++top] = item; 
        return true; 
    } 
}

bool arrStack<T>::pop(T& item) { // 出栈
    if (top == -1) { // 栈为空
        cout << "栈为空，不能执行出栈操作"<< endl;
        return false; 
    } else { 
        item = st[top--]; // 返回栈顶，并缩减1
        return true; 
    } 
}

二、链式栈（Linked Stack）

  1. 用单链表方式存储，其中指针的方向是从栈顶向下链接
  2. 理论上没有大小限制

类定义：

template <class T> 
class Link{
private:
    T data;
    Link* next{nullptr};
public:
    Link(T info, Link* nextValue);
};

template <class T> 
class lnkStack : public Stack <T> {
private: // 栈的链式存储
    Link<T>* top; // 指向栈顶的指针
    int size; // 存放元素的个数
public: // 栈运算的链式实现
    lnkStack(int defSize) { // 构造函数
        top = nullptr; 
        size = 0; 
    } 
    ~lnkStack() { // 析构函数
        clear(); 
    } 
};

// 具有两个参数的Link构造函数
Link(const T info, Link* nextValue) {
    data = info;
    next = nextValue;
}

// 入栈操作的链式实现
bool lnkStack<T>:: push(const T item) {
    Link<T>* tmp = new Link<T>(item, top); 
    top = tmp; 
    size++; 
    return true; 
}

// 出栈操作的链式实现
bool lnkStack<T>:: pop(T& item) {
    Link <T> *tmp; 
    if (size == 0) { 
        cout << "栈为空，不能执行出栈操作"<< endl;
        return false; 
    }
    item = top->data;
    tmp = top->next; 
    delete top; 
    top = tmp; 
    size--; 
    return true; 
}

三、顺序栈与链式栈的比较

  1. 时间效率
    顺序栈和链式栈都是 $\mathcal{O}(1)$ 的时间复杂度

  2. 空间效率

    • 顺序栈须说明一个固定的长度
    • 链式栈的长度可变，但增加了结构性开销（增加了一个指针变量）

  3. 实际应用中，顺序栈比链式栈用得更广泛，尤其在能预测栈中最大数据量的情况下，一般是用顺序栈来实现