链式栈定义

### 链式栈定义与实现 #### 一、链式栈的概念 链式栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作，这一端称为栈顶，另一端称为栈底。当一个元素被插入时，它会成为新的栈顶元素；当一个元素被删除时，总是删除当前的栈顶元素。链式栈相比于顺序栈（数组实现），具有动态分配内存的优点，可以避免空间溢出的情况。 #### 二、链式栈的基本结构 链式栈由节点构成，每个节点包含两个部分：存储数据的数据域(data)和指向下一个节点的指针(link)。链式栈的核心类`linkstack`继承自抽象类`stack`，并且包含了一个指向栈顶节点的指针`top`和记录栈中元素个数的整型变量`size`。 ```cpp class linknode { public: int data; // 数据域 linknode *link; // 指向下一个节点的指针 linknode(const int &el, linknode *ptr = 0) { // 构造函数 data = el; link = ptr; } }; class linkstack : public stack { private: linknode *top; // 指向栈顶的指针 int size; // 栈中元素的数量 public: linkstack(int s = 0) { top = NULL; size = 0; } ~linkstack() { clear(); // 析构函数调用清空栈的方法 } void clear(); // 清空栈 bool Push(const int item); // 入栈操作 bool Pop(int &item); // 出栈操作 bool Top(int &item); // 获取栈顶元素 }; ``` #### 三、链式栈的基本操作 1. **入栈(Push)**：创建一个新的节点，将新节点设置为栈顶节点，并更新栈顶指针。 ```cpp bool Push(const int item) { linknode *tmp = new linknode(item, top); // 创建新节点 top = tmp; // 更新栈顶指针 size++; // 栈大小加1 return true; } ``` 2. **出栈(Pop)**：获取并返回栈顶元素后，释放栈顶节点，并更新栈顶指针。 ```cpp bool Pop(int &item) { if (size == 0) { // 栈为空 cout << "栈为空" << endl; return false; } item = top->data; // 获取栈顶元素 linknode *tmp = top->link; // 保存原栈顶的下一个节点 delete top; // 释放原栈顶节点 top = tmp; // 更新栈顶指针 size--; // 栈大小减1 return true; } ``` 3. **获取栈顶元素(Top)**：返回栈顶元素，不修改栈的状态。 ```cpp bool Top(int &item) { if (size == 0) { // 栈为空 cout << "栈为空，无法获取元素" << endl; return false; } item = top->data; // 获取栈顶元素 return true; } ``` 4. **清空栈(Clear)**：依次释放栈中的所有节点，并将栈顶指针设为`NULL`，同时重置栈大小。 ```cpp void clear() { while (top != NULL) { linknode *tmp = top; // 保存当前栈顶 top = top->link; // 移动栈顶指针 delete tmp; // 释放节点 } size = 0; // 重置栈大小 } ``` #### 四、链式栈的应用实例 下面是一个简单的链式栈应用示例： ```cpp void main() { int n; linkstack s1; for (int i = 0; i < 10; i++) { s1.Push(i); // 将0到9依次入栈 } s1.Pop(n); // 弹出栈顶元素 cout << n << endl; // 输出弹出的元素 s1.Top(n); // 获取当前栈顶元素 cout << n << endl; // 输出栈顶元素 } ``` 通过上述代码可以看到，链式栈可以有效地完成基本的栈操作，如入栈、出栈、获取栈顶元素等。链式栈由于其灵活的空间管理机制，在实际应用中非常广泛，尤其是在需要频繁进行栈操作且不确定数据量的情况下更为适用。