【C++模板编程】：std::stack的类型无关栈类编写指南

# 1. C++模板编程基础

## 1.1 模板编程概念引入

在C++中，模板是一种允许程序员编写与数据类型无关的代码的强大工具。它可以用于函数和类，使得同一个函数或类可以用于处理不同的数据类型，而无需为每种类型编写重复的代码。模板机制基于参数化的概念，通过将数据类型、常量或其他模板作为参数，从而提高代码的可重用性和可维护性。

## 1.2 模板的分类

C++模板分为两种：函数模板和类模板。函数模板是对多个函数进行抽象的模板，它使得函数可以操作不同的数据类型；而类模板则是对多个类进行抽象的模板，它允许定义一种通用的数据结构，这种数据结构可以用于多种数据类型。

## 1.3 函数模板的使用

函数模板通过关键字`template`来声明，使用尖括号`<>`定义一个或多个模板参数。例如，可以定义一个交换两个变量值的模板函数，如下所示：

template <typename T>
void swap(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

// 使用示例
int main() {
    int x = 5, y = 10;
    swap(x, y);  // 调用模板函数交换整数变量
    // ...
}

在上述代码中，`swap`函数模板可以用于任意类型的`T`，因此它可以交换整数、浮点数、字符串等。函数模板的使用使得代码更加简洁且具有通用性。接下来的章节将会深入探讨模板在实际编程中的应用。

# 2. std::stack标准容器概览

### 2.1 栈容器的基本概念
在C++标准库中，`std::stack`是一个容器适配器，它给程序员提供了一个后进先出（LIFO, Last-In-First-Out）的数据结构。它允许你在序列的末端插入和移除元素，但是不允许随机访问到序列中的元素。这种数据结构在解决各种问题时非常有用，比如在编译器中处理括号匹配、在程序中实现撤销操作等。

`std::stack`模板类在`<stack>`头文件中声明，并且它以另一个容器类型作为其底层容器，例如`std::vector`或`std::deque`。这种设计允许`std::stack`利用底层容器提供的各种操作，比如动态数组的扩容、双向队列的快速插入和移除等。

### 2.2 栈容器的关键操作与属性
在`std::stack`的使用中，有一些关键的操作是必须要掌握的：

- `push(item)`：将元素`item`压入栈顶。
- `pop()`：移除栈顶元素。
- `top()`：返回栈顶元素的引用，但不移除它。
- `empty()`：判断栈是否为空，返回`true`或`false`。
- `size()`：返回栈内元素的数量。

### 2.3 栈容器的实现原理
`std::stack`的实现依赖于底层容器的操作。当使用`std::vector`作为其底层容器时，栈的`push`操作实际上是在`vector`的末尾插入一个新元素。栈的`pop`操作则调用`vector`的`erase`方法来移除最后一个元素。

#include <stack>
#include <vector>

int main() {
    std::stack<int, std::vector<int>> s;
    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << "栈顶元素为: " << ***() << std::endl;

    s.pop();
    std::cout << "栈顶元素为: " << ***() << std::endl;

    return 0;
}

在这个例子中，我们创建了一个以`std::vector<int>`为底层容器的栈，并演示了基本操作。

### 2.4 栈容器的使用场景
`std::stack`在实际编程中非常实用。例如，在处理文本解析问题时，如括号匹配或者表达式求值，它提供了一种直观的方式来管理开闭符号。

### 2.5 栈容器的限制与注意事项
需要注意的是，由于`std::stack`仅提供了有限的操作接口，因此它并没有提供直接遍历或者迭代的方法。如果需要对栈中的所有元素进行操作，必须将元素逐个从栈顶弹出，然后再进行处理。此外，使用`std::stack`时，还应当注意其底层容器的选择可能对性能有一定的影响。

总的来说，`std::stack`作为一种容器适配器，它的接口简单明了，对于需要后进先出操作的场景来说，它是一个非常方便的工具。接下来的章节，我们将深入探讨如何创建一个自定义的类型无关栈类，并探讨模板编程中的高级概念。

# 3. 自定义类型无关栈类

## 3.1 栈类的设计理念与模板实现

栈是一种后进先出（LIFO）的数据结构，常用于保存临时变量，支持诸如`push`、`pop`、`top`等操作。在C++中，我们可以利用模板来设计一个类型无关的栈类，这样可以处理不同类型的元素，如整数、浮点数、甚至自定义对象等。

### 3.1.1 栈的操作接口设计

在设计栈类时，我们首先定义其操作接口，主要包括以下几个成员函数：

- `push(T element)`：将一个元素添加到栈顶。
- `pop()`：移除栈顶元素。
- `top()`：返回栈顶元素的值，但不移除它。
- `size()`：返回栈中元素的个数。
- `isEmpty()`：检查栈是否为空。
- `isFull()`：检查栈是否已满（适用于固定大小的栈）。

### 3.1.2 模板类的定义和参数传递

为了实现一个类型无关的栈，我们需要定义一个模板类。模板类允许我们在编译时期动态地指定栈中元素的类型。

template <typename T>
class Stack {
private:
    T* elements;  // 指向栈中元素的指针
    int topIndex; // 栈顶元素的索引
    int stackCapacity; // 栈的最大容量

public:
    // 构造函数
    Stack(int capacity) : topIndex(-1), stackCapacity(capacity) {
        elements = new T[stackCapacity];
    }

    // 析构函数
    ~Stack() {
        delete[] elements;
    }

    // ... 其他成员函数 ...
};

在这个模板类中，我们定义了一个动态数组`elements`来存储栈元素，并且使用`topIndex`来追踪栈顶的位置。构造函数接受一个参数`capacity`，用于初始化栈的大小。

### 3.1.3 构造函数与析构函数的实现

构造函数负责分配内存，并初始化栈顶索引。析构函数负责释放内存。为了安全地使用资源，我们还将实现拷贝构造函数和赋值运算符，确保栈的深拷贝。

## 3.2 栈的基本操作实现

### 3.2.1 push操作的实现

`push`操作将一个元素添加到栈顶。如果栈已满，则需要扩展栈的容量。

template <typename T>
void Stack<T>::push(T element) {
    if (topIndex == stackCapacity - 1) {
        // 如果栈已满，需要扩展容量
        T* newElements = new T[stackCapacity * 2];
        for (int i = 0; i <= topIndex; ++i) {
            newElements[i] = elements[i];
        }
        delete[] elements;
        elements = newElements;
        stackCapacity *= 2;
    }
    elements[++topIndex] = element;
}

### 3.2.2 pop操作的实现

`pop`操作移除栈顶元素。如果栈为空，则需要处理错误。

template <typename T>
void Stack<T>::pop