链式栈 - C语言实现

数据结构学习笔记 | 2026-4-30

一、基本概念

栈（Stack）是一种后进先出（LIFO, Last In First Out）的线性表。它只允许在表尾进行插入和删除操作。

链式栈：用链表实现的栈，不需要考虑栈满的问题，动态分配内存。

基本操作：

  • 初始化：创建空栈
  • 入栈（Push）：将元素压入栈顶
  • 出栈（Pop）：将栈顶元素弹出
  • 取栈顶元素（GetTop）：获取栈顶元素的值但不弹出
  • 判空（StackEmpty）：判断栈是否为空
  • 销毁（DestroyStack）：释放栈占用的内存

二、结构体定义

1
2
3
4
5
6
7
typedef char ElemType;

typedef struct linknode
{
    ElemType data;         // 数据域
    struct linknode *next; // 指针域
} LinkStNode;
成员 含义
data 栈节点的数据域，存储元素值
next 指向下一个节点的指针

说明：ElemType 定义为 char 类型，可根据需要修改为其他类型

三、函数声明

1
2
3
4
5
6
void InitStack(LinkStNode **s);           // 初始化栈
void Push(LinkStNode **s, ElemType e);    // 入栈（压栈）
bool GetTop(LinkStNode *s, ElemType *e);  // 取栈顶元素
bool Pop(LinkStNode **s, ElemType *e);   // 出栈
bool StackEmpty(LinkStNode *s);          // 判断栈是否为空
void DestroyStack(LinkStNode **s);        // 销毁链栈

四、功能函数实现

1. 初始化栈

1
2
3
4
5
void InitStack(LinkStNode **s)
{
    (*s) = (LinkStNode *)malloc(sizeof(struct linknode));
    (*s)->next = NULL;
}
  • 通过 malloc() 分配头结点空间
  • 头结点的 next 指针设为 NULL，表示空栈

2. 入栈（压栈）

1
2
3
4
5
6
7
8
void Push(LinkStNode **s, ElemType e)
{
    // 生成一个新的结点，结点的数据域的值是e
    LinkStNode *p = (LinkStNode *)malloc(sizeof(LinkStNode));
    p->data = e;
    p->next = (*s)->next; // 插入p节点作为开始节点
    (*s)->next = p;
}

特点：新节点插入到栈顶（头结点之后），成为新的栈顶元素

3. 取栈顶元素

1
2
3
4
5
6
7
bool GetTop(LinkStNode *s, ElemType *e)
{
    if (s->next == NULL) // 栈空的情况
        return false;
    *e = s->next->data;
    return true;
}

注意：只是获取栈顶元素的值，不弹出该元素

4. 出栈

1
2
3
4
5
6
7
8
9
10
11
bool Pop(LinkStNode **s, ElemType *e)
{
    LinkStNode *p;
    if ((*s)->next == NULL) // 栈空的情况
        return false;
    p = (*s)->next;        // p指向开始节点（栈顶节点）
    *e = p->data;
    (*s)->next = p->next;   // 删除p节点
    free(p);                // 释放p节点
    return true;
}

注意：出栈操作需要 free(p) 释放被弹出节点的内存

5. 判断栈是否为空

1
2
3
4
bool StackEmpty(LinkStNode *s)
{
    return (s->next == NULL);
}

简化：直接返回判断表达式的结果

6. 销毁链栈

1
2
3
4
5
6
7
8
9
10
11
void DestroyStack(LinkStNode **s)
{
    LinkStNode *p = (*s)->next;
    while (p != NULL)
    {
        free(*s);
        *s = p;
        p = p->next;
    }
    free(*s); // s指向尾节点，释放其空间
}

说明：遍历所有节点，逐个释放内存，最后将指针置为 NULL

五、使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int main()
{
    LinkStNode *s;
    ElemType e;

    printf("初始化堆栈开始:\n");
    InitStack(&s);

    // 入栈操作
    Push(&s, 'a');
    GetTop(s, &e);
    printf("当前栈顶的元素为: %c\n", e); // a

    Push(&s, 'b');
    GetTop(s, &e);
    printf("当前栈顶的元素为: %c\n", e); // b

    Push(&s, 'c');
    Push(&s, 'd');
    Push(&s, 'e');

    // 出栈操作
    printf("开始出栈: \n");
    while (!StackEmpty(s))
    {
        Pop(&s, &e);
        printf("当前出栈的元素为: %c\n", e);
    }

    DestroyStack(&s);
    printf("栈已销毁 \n");

    return 0;
}

运行结果：

1
2
3
4
5
6
7
8
9
10
初始化堆栈开始:
当前栈顶的元素为: a
当前栈顶的元素为: b
开始出栈:
当前出栈的元素为: e
当前出栈的元素为: d
当前出栈的元素为: c
当前出栈的元素为: b
当前出栈的元素为: a
栈已销毁

六、图解链式栈结构

1
2
3
4
5
6
7
8
9
栈结构示意图：

        +---+     +---+     +---+     +---+
        | e |     | d |     | c |     | b |     | a |
        +---+     +---+     +---+     +---+     +---+
          ↑         ↑
        top         ...
        
    栈顶(top) → e (最后进入，最先弹出)
1
2
3
4
5
6
7
入栈操作 (Push 'x')：

    原栈: [a] → [b] → [c]
    
    Push后: [x] → [a] → [b] → [c]
              ↑
             top
1
2
3
4
5
6
7
8
9
10
出栈操作 (Pop):

    原栈: [x] → [a] → [b] → [c]
              ↑
             top
    
    Pop后: [a] → [b] → [c]
            ↑
           top
    返回弹出元素: x

七、时间复杂度分析

操作 时间复杂度 说明
初始化 O(1) 只需分配一个头结点
入栈（Push） O(1) 直接在栈顶插入节点
出栈（Pop） O(1) 直接删除栈顶节点
取栈顶元素（GetTop） O(1) 直接访问栈顶节点
判空（StackEmpty） O(1) 直接判断头结点next
销毁（DestroyStack） O(n) 需要遍历释放所有节点

八、关键知识点

  1. 栈的特点：后进先出（LIFO），只能在一端操作
  2. 链式栈优势：不需要考虑栈满问题，动态分配内存
  3. 头结点作用：简化栈操作，头结点本身不存储数据
  4. 内存管理：入栈 malloc() 分配，出栈 free() 释放
  5. 指针维护：入栈时注意 p->next 和 (*s)->next 的赋值顺序
  6. 栈空判断：s->next == NULL 表示栈空

九、完整代码下载

源代码文件：Linked-Stack-from-Scratch-with-C.c