3-5链式栈的基本操作1

链式栈是一种特殊的线性数据结构，它与数组栈不同，不依赖于预先固定的内存空间。在链式栈中，每个元素（称为节点）包含一个数据域和一个指向下一个节点的指针。这种结构允许栈在运行时动态地扩展或收缩，而无需预先知道其可能的最大大小。 在C++中，我们可以创建一个模板类`LStack`来实现链式栈。这个类使用了泛型编程，允许我们存储任何类型的数据（只要该类型支持拷贝构造函数）。以下是`LStack`类的主要组成部分及其功能： 1. **私有成员变量**： - `SLNode<T> *top`：这是一个指针，指向栈顶的节点。在初始化时，`top`被设置为`NULL`，表示栈是空的。 2. **构造函数**： - `LStack()`: 默认构造函数，初始化栈顶指针`top`为`NULL`，表示栈为空。 3. **析构函数**： - `~LStack()`: 当对象销毁时自动调用，用于释放栈中的所有元素。通过`clear()`函数实现。 4. **清空栈**： - `void clear()`: 这个函数遍历栈并删除所有节点，同时更新栈顶指针`top`。在删除节点时，先保存当前栈顶节点的下一个节点，然后释放当前节点，最后将`top`更新为保存的下一个节点。 5. **压栈操作**： - `bool Push(const T& item)`: 向栈顶添加一个新元素。创建一个新的节点，将其数据域设置为`item`，并将它的`next`指针指向当前的栈顶节点。然后更新`top`指向新创建的节点。如果成功，返回`true`。 6. **弹栈操作**： - `bool Pop(T &item)`: 从栈顶移除一个元素，并将该元素的值赋给`item`。如果栈为空，返回`false`，并打印错误信息。否则，将栈顶元素的值复制到`item`，释放栈顶节点，更新`top`为下一个节点，返回`true`。 7. **查看栈顶元素**： - `bool Peek(T &item) const`: 返回栈顶元素的值，但不移除它。如果栈为空，返回`false`，并打印错误信息。否则，将栈顶元素的值复制到`item`，返回`true`。 8. **检测栈是否为空**： - `int IsEmpty(void) const`: 如果`top`等于`NULL`，即栈顶指针没有指向任何节点，说明栈为空，返回`true`；否则返回`false`。 这些基本操作构成了链式栈的核心，使得我们能够灵活地管理数据，执行常见的栈操作，如压栈、弹栈、查看栈顶元素等，同时确保了内存的有效管理。链式栈适用于需要高效插入和删除操作且数据量不确定的场景。