C++链栈的实现代码怎么写

C++链栈的实现代码怎么写

链栈是一种基于链表实现的栈结构，它具有动态分配内存、无需预先设定栈的大小等优点。本文将详细介绍如何使用C++实现链栈，并提供完整的代码示例。

1. 链栈的基本概念

栈是一种后进先出（LIFO, Last In First Out）的数据结构，链栈则是通过链表来实现栈的操作。链栈的每个节点包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。

链栈的基本操作包括： - Push: 将元素压入栈顶。 - Pop: 弹出栈顶元素。 - Top: 获取栈顶元素。 - IsEmpty: 判断栈是否为空。

2. 链栈的节点结构

首先，我们需要定义一个节点结构，用于表示链栈中的每个节点。

struct Node { int data; // 数据域 Node* next; // 指针域，指向下一个节点 Node(int val) : data(val), next(nullptr) {} }; 

在这个结构中，data用于存储节点的数据，next指针用于指向下一个节点。

3. 链栈类的定义

接下来，我们定义一个LinkedStack类，用于封装链栈的操作。

class LinkedStack { private: Node* top; // 栈顶指针 public: LinkedStack() : top(nullptr) {} // 构造函数，初始化栈顶指针为空 ~LinkedStack(); // 析构函数，用于释放内存 void push(int val); // 压栈操作 void pop(); // 弹栈操作 int topElement(); // 获取栈顶元素 bool isEmpty(); // 判断栈是否为空 }; 

4. 链栈操作的实现

4.1 压栈操作（Push）

压栈操作是将一个新元素添加到栈顶。我们需要创建一个新节点，并将其插入到链表的头部。

void LinkedStack::push(int val) { Node* newNode = new Node(val); // 创建新节点 newNode->next = top; // 新节点的next指向当前栈顶 top = newNode; // 更新栈顶指针 } 

4.2 弹栈操作（Pop）

弹栈操作是移除栈顶元素。我们需要删除链表头部的节点，并更新栈顶指针。

void LinkedStack::pop() { if (isEmpty()) { std::cout << "栈为空，无法执行弹栈操作！" << std::endl; return; } Node* temp = top; // 临时保存栈顶节点 top = top->next; // 更新栈顶指针 delete temp; // 释放原栈顶节点的内存 } 

4.3 获取栈顶元素（Top）

获取栈顶元素的操作是返回栈顶节点的数据。

int LinkedStack::topElement() { if (isEmpty()) { std::cout << "栈为空，无法获取栈顶元素！" << std::endl; return -1; // 返回一个无效值表示栈为空 } return top->data; // 返回栈顶元素的数据 } 

4.4 判断栈是否为空（IsEmpty）

判断栈是否为空的操作是检查栈顶指针是否为nullptr。

bool LinkedStack::isEmpty() { return top == nullptr; // 如果栈顶指针为空，则栈为空 } 

4.5 析构函数

析构函数用于释放链栈中所有节点的内存，防止内存泄漏。

LinkedStack::~LinkedStack() { while (!isEmpty()) { pop(); // 逐个弹出栈顶元素，释放内存 } } 

5. 完整代码示例

#include <iostream> struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; class LinkedStack { private: Node* top; public: LinkedStack() : top(nullptr) {} ~LinkedStack(); void push(int val); void pop(); int topElement(); bool isEmpty(); }; LinkedStack::~LinkedStack() { while (!isEmpty()) { pop(); } } void LinkedStack::push(int val) { Node* newNode = new Node(val); newNode->next = top; top = newNode; } void LinkedStack::pop() { if (isEmpty()) { std::cout << "栈为空，无法执行弹栈操作！" << std::endl; return; } Node* temp = top; top = top->next; delete temp; } int LinkedStack::topElement() { if (isEmpty()) { std::cout << "栈为空，无法获取栈顶元素！" << std::endl; return -1; } return top->data; } bool LinkedStack::isEmpty() { return top == nullptr; } int main() { LinkedStack stack; stack.push(10); stack.push(20); stack.push(30); std::cout << "栈顶元素: " << stack.topElement() << std::endl; stack.pop(); std::cout << "弹栈后栈顶元素: " << stack.topElement() << std::endl; stack.pop(); stack.pop(); if (stack.isEmpty()) { std::cout << "栈为空" << std::endl; } return 0; } 

6. 运行结果

运行上述代码，输出结果如下：

栈顶元素: 30 弹栈后栈顶元素: 20 栈为空 

7. 总结

本文详细介绍了如何使用C++实现链栈，并提供了完整的代码示例。链栈通过链表实现，具有动态分配内存、无需预先设定栈的大小等优点。通过实现链栈的基本操作，我们可以更好地理解栈这种数据结构的工作原理。