c++中如何使用链表实现栈_c++链表实现栈方法

可以用链表实现栈结构，通过定义节点和栈类实现LIFO操作，核心是将链表头部作为栈顶，支持push、pop、peek和empty等方法，示例代码展示了入栈出栈过程，使用时需注意内存管理。

在C++中，可以用链表来实现栈结构。栈是一种“后进先出”（LIFO）的数据结构，使用链表实现可以动态管理内存，避免数组实现时的容量限制。

定义链表节点和栈类

首先需要定义一个链表节点结构体，每个节点存储数据和指向下一个节点的指针。然后创建一个栈类，维护栈顶指针并提供入栈、出栈等操作。

struct ListNode {
   int val;
   ListNode* next;
   ListNode(int x) : val(x), next(nullptr) {}
};

class Stack {
private:
   ListNode top;

public:
   Stack() : top(nullptr) {}

   void push(int x) {
      ListNode newNode = new ListNode(x);
      newNode->next = top;
      top = newNode;
   }

   void pop() {
      if (top == nullptr) {
         std::cout << "栈为空，无法出栈\n";
         return;
      }
      ListNode* temp = top;
      top = top->next;
      delete temp;
   }

   int peek() const {
      if (top == nullptr) {
         throw std::runtime_error("栈为空");
      }
      return top->val;
   }

   bool empty() const {
      return top == nullptr;
   }

   // 析构函数，释放所有节点
   ~Stack() {
      while (top != nullptr) {
         ListNode* temp = top;
         top = top->next;
         delete temp;
      }
   }
};

关键操作说明

链表实现栈的核心在于将链表头部作为栈顶，这样所有操作都能在常数时间内完成。

爱图表

AI驱动的智能化图表创作平台

99

查看详情

立即学习“C++免费学习笔记（深入）”；

• push(x)：创建新节点，将其 next 指向当前栈顶，再更新 top 指针。
• pop()：检查是否为空，非空则删除头节点并更新 top 指针。
• peek()：返回 top 节点的值，不修改栈结构。
• empty()：判断 top 是否为 nullptr。

使用示例

下面是一个简单的测试代码：

int main() {
   Stack s;
   s.push(1);
   s.push(2);
   s.push(3);

   std::cout << s.peek() << std::endl; // 输出 3
   s.pop();
   std::cout << s.peek() << std::endl; // 输出 2

   return 0;
}

基本上就这些。用链表实现栈灵活高效，适合不确定元素数量的场景。注意手动管理内存或结合智能指针提升安全性。

以上就是c++++中如何使用链表实现栈_c++链表实现栈方法的详细内容，更多请关注php中文网其它相关文章！