链栈的基本操作 c语言-C语言-盈思创科技

什么是链栈？

栈是一种后进先出 的数据结构，链栈就是采用链表（这里是单链表）来实现的栈。

与顺序栈（基于数组）相比,链栈的主要优点是：

动态大小：可以根据需要动态地增加或删除节点，没有固定的大小限制，避免了顺序栈可能出现的“溢出”问题。
内存效率：只在需要时才分配内存,不会像顺序栈那样预先分配一块可能用不完的连续空间。

链栈的栈顶指针通常指向链表的第一个节点，这样在栈顶进行插入和删除操作的时间复杂度都是 O(1),效率很高。

数据结构定义

我们需要定义链栈中节点的结构体和栈的结构体。

StackNode：代表链表中的一个节点，包含数据域 data 和指向下一个节点的指针 next。
LinkStack：代表整个栈，只需要一个指向栈顶节点的指针 top，如果栈为空，top 指针为 NULL。

#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 定义栈节点的结构体
typedef struct StackNode {
    int data;           // 数据域，这里以 int 类型为例
    struct StackNode *next; // 指针域，指向下一个节点
} StackNode;
// 定义链栈的结构体
typedef struct {
    StackNode *top; // 栈顶指针，指向第一个节点
} LinkStack;

基本操作实现

以下是链栈所有核心操作的 C 语言实现。

1 初始化栈

创建一个空栈，只需将栈顶指针 top 置为 NULL。

// 初始化链栈
void InitStack(LinkStack *S) {
    S->top = NULL; // 空栈的 top 指针为 NULL
    printf("链栈初始化成功，\n");
}

2 判断栈是否为空

检查栈顶指针 top 是否为 NULL。

// 判断链栈是否为空
int IsEmpty(LinkStack *S) {
    return S->top == NULL; // top 为 NULL，则栈为空，返回 1 (true)，否则返回 0 (false)
}

3 入栈

在栈顶插入一个新节点,这是链栈的核心操作之一。

创建一个新节点。
将新节点的 next 指针指向当前的栈顶节点。
更新栈顶指针 top,使其指向新节点。

// 入栈操作
int Push(LinkStack *S, int value) {
    // 1. 创建新节点
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return 0; // 入栈失败
    }
    // 2. 填充新节点的数据
    newNode->data = value;
    // 3. 将新节点插入到链表头部（栈顶）
    newNode->next = S->top; // 新节点的 next 指向原来的栈顶
    S->top = newNode;       // 更新栈顶指针，指向新节点
    printf("元素 %d 入栈成功，\n", value);
    return 1; // 入栈成功
}

4 出栈

删除栈顶的节点,这也是核心操作。

检查栈是否为空,如果为空则不能出栈。
创建一个临时指针指向栈顶节点,以便后续释放内存。
将栈顶指针 top 移向下一个节点。
释放原栈顶节点的内存。

// 出栈操作
int Pop(LinkStack *S, int *e) {
    // 1. 检查栈是否为空
    if (IsEmpty(S)) {
        printf("栈为空，无法出栈！\n");
        return 0; // 出栈失败
    }
    // 2. 保存栈顶元素的值到 e 指针指向的变量中
    *e = S->top->data;
    // 3. 创建临时指针指向当前栈顶节点
    StackNode *temp = S->top;
    // 4. 移动栈顶指针到下一个节点
    S->top = S->top->next;
    // 5. 释放原栈顶节点的内存
    free(temp);
    printf("元素 %d 出栈成功，\n", *e);
    return 1; // 出栈成功
}

5 获取栈顶元素

与出栈不同，此操作只是读取栈顶元素的值，不删除该节点。

检查栈是否为空。
直接返回栈顶节点的数据。

// 获取栈顶元素（不删除）
int GetTop(LinkStack *S, int *e) {
    // 1. 检查栈是否为空
    if (IsEmpty(S)) {
        printf("栈为空，没有栈顶元素！\n");
        return 0; // 获取失败
    }
    // 2. 将栈顶元素的值赋给 e
    *e = S->top->data;
    printf("栈顶元素为: %d\n", *e);
    return 1; // 获取成功
}

6 销毁栈

释放链栈中所有节点的内存,防止内存泄漏。

从栈顶开始,遍历整个链表。
使用一个临时指针 p 指向当前节点，q 指向下一个节点。
释放 p 指向的节点，然后移动 p 和 q。
将栈的 top 指针置为 NULL。

// 销毁链栈
void DestroyStack(LinkStack *S) {
    StackNode *p = S->top;
    StackNode *q;
    while (p != NULL) {
        q = p->next; // q 指向 p 的下一个节点
        free(p);     // 释放 p 当前指向的节点
        p = q;       // p 移动到下一个节点
    }
    S->top = NULL; // 栈顶指针置为 NULL
    printf("链栈已销毁，\n");
}

完整示例代码

下面是一个完整的、可运行的 C 程序,它演示了如何使用上述所有链栈操作。

#include <stdio.h>
#include <stdlib.h>
// 定义栈节点的结构体
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;
// 定义链栈的结构体
typedef struct {
    StackNode *top;
} LinkStack;
// 函数声明
void InitStack(LinkStack *S);
int IsEmpty(LinkStack *S);
int Push(LinkStack *S, int value);
int Pop(LinkStack *S, int *e);
int GetTop(LinkStack *S, int *e);
void DestroyStack(LinkStack *S);
void PrintStack(LinkStack *S);
int main() {
    LinkStack myStack;
    int value, poppedValue, topValue;
    // 1. 初始化
    InitStack(&myStack);
    // 2. 入栈
    Push(&myStack, 10);
    Push(&myStack, 20);
    Push(&myStack, 30);
    printf("当前栈内元素（从栈顶到栈底）: ");
    PrintStack(&myStack);
    // 3. 获取栈顶元素
    if (GetTop(&myStack, &topValue)) {
        // GetTop 函数内部已经打印了，这里可以省略
    }
    // 4. 出栈
    if (Pop(&myStack, &poppedValue)) {
        printf("当前栈内元素（从栈顶到栈底）: ");
        PrintStack(&myStack);
    }
    if (Pop(&myStack, &poppedValue)) {
        printf("当前栈内元素（从栈顶到栈底）: ");
        PrintStack(&myStack);
    }
    // 5. 测试从空栈出栈
    Pop(&myStack, &poppedValue); // 此时栈中只剩一个元素，出栈后为空
    Pop(&myStack, &poppedValue); // 栈已为空，这次会失败
    // 6. 销毁栈
    DestroyStack(&myStack);
    return 0;
}
// --- 函数实现 ---
void InitStack(LinkStack *S) {
    S->top = NULL;
    printf("链栈初始化成功，\n");
}
int IsEmpty(LinkStack *S) {
    return S->top == NULL;
}
int Push(LinkStack *S, int value) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return 0;
    }
    newNode->data = value;
    newNode->next = S->top;
    S->top = newNode;
    printf("元素 %d 入栈成功，\n", value);
    return 1;
}
int Pop(LinkStack *S, int *e) {
    if (IsEmpty(S)) {
        printf("栈为空，无法出栈！\n");
        return 0;
    }
    *e = S->top->data;
    StackNode *temp = S->top;
    S->top = S->top->next;
    free(temp);
    printf("元素 %d 出栈成功，\n", *e);
    return 1;
}
int GetTop(LinkStack *S, int *e) {
    if (IsEmpty(S)) {
        printf("栈为空，没有栈顶元素！\n");
        return 0;
    }
    *e = S->top->data;
    printf("栈顶元素为: %d\n", *e);
    return 1;
}
void DestroyStack(LinkStack *S) {
    StackNode *p = S->top;
    StackNode *q;
    while (p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }
    S->top = NULL;
    printf("链栈已销毁，\n");
}
// 辅助函数：打印栈中所有元素（用于演示）
void PrintStack(LinkStack *S) {
    if (IsEmpty(S)) {
        printf("栈为空，\n");
        return;
    }
    StackNode *p = S->top;
    printf("[");
    while (p != NULL) {
        printf("%d", p->data);
        if (p->next != NULL) {
            printf(", ");
        }
        p = p->next;
    }
    printf("]\n");
}

操作	C 语言实现	时间复杂度	描述
初始化	`S->top = NULL;`	O(1)	将栈顶指针设为 `NULL`。
判空	`S->top == NULL`	O(1)	检查栈顶指针是否为 `NULL`。
入栈	`newNode->next = S->top; S->top = newNode;`	O(1)	在链表头部插入一个新节点。
出栈	`temp = S->top; S->top = S->top->next; free(temp);`	O(1)	删除链表头部的节点，并释放内存。
取栈顶	`*e = S->top->data;`	O(1)	读取链表头部节点的数据。
销毁	遍历链表并逐个 `free()`	O(n)	释放所有节点的内存，`n` 为栈中元素个数。

链栈的实现非常直观，其所有核心操作都依赖于单链表的头部操作，因此效率很高，掌握链栈的实现是理解更复杂数据结构（如表达式求值、函数调用栈等）的基础。

链栈的基本操作 c语言