Stack

栈（Stack）概述

定义：栈是一种仅允许在一端进行插入和删除操作的线性表。这一端被称为“顶端”（Top），符合后进先出（LIFO）的原则。
- LIFO（Last In, First Out）：最后插入的元素最先被删除。
基本操作：
- Push：在栈顶插入元素。
- Pop：删除并返回栈顶元素（也称为“TopAndPop”）。
- IsEmpty：检查栈是否为空。
- TopValue：返回栈顶元素但不删除它。

栈的抽象数据类型（ADT）

template <typename E>
class Stack {
private:
    void operator=(const Stack&) {} // 防止赋值操作
    Stack(const Stack&) {} // 防止复制构造

public:
    // 将元素推入栈顶
    virtual bool push(const E& it) = 0;

    // 移除栈顶元素
    virtual E pop() = 0;

    // 返回栈顶元素的副本
    virtual const E& topValue() const = 0;
};

基于数组的栈实现

数组实现的栈

特征：栈的大小是固定的。
类定义：

template <typename E>
class AStack : public Stack<E> {
private:
    int maxSize;     // 栈的最大大小
    int top;         // 栈顶元素的索引（自由位置）
    E *listArray;    // 存储栈元素的数组

public:
    AStack(int size = defaultSize) // 构造函数
    {
        maxSize = size; 
        top = 0; 
        listArray = new E[size]; 
    }

    ~AStack() {
        delete[] listArray; // 析构函数
    }

    // 清空栈
    void clear() { 
        top = 0; 
    }

    // 将元素推入栈顶
    void push(const E& it) { 
        assert(top != maxSize && "Stack is full");
        listArray[top++] = it; 
    }

    // 弹出栈顶元素
    E pop() {
        assert(top != 0 && "Stack is empty");
        return listArray[--top]; 
    }

    // 返回栈顶元素
    const E& topValue() const { 
        assert(top != 0 && "Stack is empty");
        return listArray[top - 1]; 
    }
};

操作说明

构造函数：
- 初始化栈的最大大小和栈顶索引，并分配存储栈元素的数组。
清空栈：
- 将栈顶索引重置为0，表示栈为空。
Push操作：
- 在栈顶插入元素之前检查栈是否已满。
- 将元素存储在当前栈顶位置，然后将栈顶索引加1。
Pop操作：
- 在弹出元素之前检查栈是否为空。
- 将栈顶索引减1，并返回栈顶元素。
TopValue操作：
- 在返回栈顶元素之前检查栈是否为空。

时间复杂度

Push操作：\(O(1)\)（常数时间）
Pop操作：\(O(1)\)（常数时间）

基于链表的栈实现

链表实现的栈

特征：使用链表实现栈，节点中包含指向下一个节点的指针。
类定义：

template <typename E>
class LStack : public Stack<E> {
private:
    Link<E>* top; // 指向栈顶元素的指针
    int size;     // 元素数量

public:
    LStack(int sz = defaultSize) { // 构造函数
        top = NULL; 
        size = 0; 
    }

    ~LStack() {
        clear(); // 析构函数
    }

    // 清空栈
    void clear() {
        while (top != NULL) {
            Link<E>* temp = top;
            top = top->next; // 移动指针
            delete temp; // 删除节点
        }
        size = 0;
    }

    // 将元素推入栈顶
    void push(const E& it) {
        top = new Link<E>(it, top); // 创建新节点
        size++;
    }

    // 弹出栈顶元素
    E pop() {
        assert(top != NULL && "Stack is empty");
        E it = top->element; // 获取栈顶元素
        Link<E>* ltemp = top->next; // 暂存下一个节点
        delete top; // 删除当前节点
        top = ltemp; // 更新栈顶指针
        size--;
        return it;
    }

    // 返回栈顶元素
    const E& topValue() const {
        assert(top != NULL && "Stack is empty");
        return top->element;
    }
};