当前位置：首页 > 其他 > 手把手教你用链表实现栈：从步骤讲解到实战应用（新手友好版）

手把手教你用链表实现栈：从步骤讲解到实战应用（新手友好版）

4天前

一、简介和特点

链表栈是一种基于链表实现的数据结构，结合了栈的“先进后出（LIFO）”特性和链表的动态内存分配优势。相比数组实现的栈，链表栈无需提前指定固定容量，可动态扩展，插入和删除操作效率高，尤其适用于数据量动态变化的场景。本文将通过一个手写的C++链表栈代码，带你逐步理解其实现原理。

二、与其他数据结构相比的优点

1. 动态扩容：无需预设大小，通过动态内存分配（如new）实时创建节点，避免空间浪费或溢出。

2. 操作灵活：插入（add）和删除（del）仅需在头部操作，时间复杂度均为O(1)，效率优于某些需要移动元素的数组栈。

3. 内存管理：手动控制节点创建和释放（如delete），帮助新手理解内存管理机制。

三、实现步骤

步骤1：定义节点结构

使用struct node定义链表节点，包含数据域（data）和指向下一个节点的指针（next）。

步骤2：创建栈类

声明私有成员top指针，初始化为new node（空节点，头部哨兵）。

提供三个公有方法：add（入栈）、del（出栈）、select（获取栈顶元素）。

步骤3：实现核心逻辑

add(data)：创建新节点，赋值后插入头部（更新top）。

del()：删除栈顶节点，需先保存top指针，再更新top为下一个节点，最后释放旧节点。

select()：直接返回top->data，不修改栈结构。

步骤4：内存安全

在del()中使用delete释放节点，防止内存泄漏。

四、代码和注释

#include <iostream>
using namespace std;

// 定义链表节点结构
struct node {
    int data;         // 存储数据
    node* next;       // 指向下一个节点
};

class Stack {
private:
    node* top = new node;  // 栈顶指针，初始化为空节点（头部哨兵）

public:
    // 入栈操作：将数据插入栈顶
    void add(int data) {
        node* tmp = new node;     // 创建新节点
        tmp->data = data;         // 赋值
        tmp->next = top;          // 指向原栈顶
        top = tmp;                // 更新栈顶指针
    }

    // 出栈操作：删除栈顶节点
    void del() {
        node* tmp = top;          // 保存栈顶指针
        top = top->next;          // 更新栈顶为下一个节点
        delete tmp;               // 释放旧节点内存
    }

    // 获取栈顶元素（不修改栈结构）
    int select() {
        return top->data;         // 直接返回栈顶数据
    }
};