怎么用C语言实现链式栈

发布时间：2021-12-20 12:27:15 作者：小新
来源：亿速云阅读：206

# 怎么用C语言实现链式栈

## 1. 链式栈概述

链式栈(Linked Stack)是采用链式存储结构实现的栈。与顺序栈不同，链式栈不需要预先分配固定大小的存储空间，而是通过动态内存分配来存储元素，理论上只要内存足够就可以无限扩展。

### 1.1 链式栈的特点
- 动态内存分配，无需预先确定栈大小
- 插入和删除操作都在表头进行，时间复杂度为O(1)
- 不会出现栈满的情况（除非内存耗尽）
- 每个节点需要额外空间存储指针，空间利用率略低于顺序栈

### 1.2 链式栈的基本操作
- 初始化(init)
- 入栈(push)
- 出栈(pop)
- 获取栈顶元素(top)
- 判断栈空(isEmpty)
- 销毁栈(destroy)

## 2. 链式栈的数据结构设计

### 2.1 节点结构定义

```c
typedef struct StackNode {
    int data;               // 存储数据（这里以int为例）
    struct StackNode *next; // 指向下一个节点的指针
} StackNode;

2.2 栈结构定义

typedef struct LinkedStack {
    StackNode *top;         // 栈顶指针
    int size;               // 栈中元素个数（可选）
} LinkedStack;

3. 链式栈的实现

3.1 初始化栈

void initStack(LinkedStack *stack) {
    stack->top = NULL;     // 栈顶指针初始化为NULL
    stack->size = 0;       // 元素个数初始化为0
}

3.2 判断栈是否为空

int isEmpty(LinkedStack *stack) {
    return stack->top == NULL;  // 或者 return stack->size == 0;
}

3.3 入栈操作

int push(LinkedStack *stack, int value) {
    // 创建新节点
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return 0; // 入栈失败
    }
    
    newNode->data = value;
    newNode->next = stack->top; // 新节点指向原栈顶
    stack->top = newNode;       // 更新栈顶指针
    stack->size++;              // 栈大小增加
    return 1; // 入栈成功
}

3.4 出栈操作

int pop(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return 0; // 出栈失败
    }
    
    StackNode *temp = stack->top; // 临时保存栈顶节点
    *value = temp->data;         // 通过指针参数返回栈顶值
    stack->top = temp->next;      // 更新栈顶指针
    free(temp);                   // 释放原栈顶节点
    stack->size--;                // 栈大小减少
    return 1; // 出栈成功
}

3.5 获取栈顶元素

int top(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return 0; // 获取失败
    }
    
    *value = stack->top->data; // 通过指针参数返回栈顶值
    return 1; // 获取成功
}

3.6 销毁栈

void destroyStack(LinkedStack *stack) {
    StackNode *current = stack->top;
    StackNode *next;
    
    while (current != NULL) {
        next = current->next; // 保存下一个节点地址
        free(current);        // 释放当前节点
        current = next;       // 移动到下一个节点
    }
    
    stack->top = NULL; // 重置栈顶指针
    stack->size = 0;   // 重置栈大小
}

4. 完整示例代码

#include <stdio.h>
#include <stdlib.h>

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

typedef struct LinkedStack {
    StackNode *top;
    int size;
} LinkedStack;

void initStack(LinkedStack *stack) {
    stack->top = NULL;
    stack->size = 0;
}

int isEmpty(LinkedStack *stack) {
    return stack->top == NULL;
}

int push(LinkedStack *stack, int value) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return 0;
    }
    
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
    return 1;
}

int pop(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return 0;
    }
    
    StackNode *temp = stack->top;
    *value = temp->data;
    stack->top = temp->next;
    free(temp);
    stack->size--;
    return 1;
}

int top(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return 0;
    }
    
    *value = stack->top->data;
    return 1;
}

void destroyStack(LinkedStack *stack) {
    StackNode *current = stack->top;
    StackNode *next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    stack->top = NULL;
    stack->size = 0;
}

void printStack(LinkedStack *stack) {
    printf("Stack (top to bottom): ");
    StackNode *current = stack->top;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    LinkedStack stack;
    initStack(&stack);
    
    // 测试入栈
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    printStack(&stack); // 输出: 30 20 10
    
    // 测试获取栈顶元素
    int topValue;
    if (top(&stack, &topValue)) {
        printf("Top element: %d\n", topValue); // 输出: 30
    }
    
    // 测试出栈
    int poppedValue;
    pop(&stack, &poppedValue);
    printf("Popped: %d\n", poppedValue); // 输出: 30
    printStack(&stack); // 输出: 20 10
    
    // 测试栈空判断
    printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No"); // 输出: No
    
    // 销毁栈
    destroyStack(&stack);
    printf("Is stack empty after destruction? %s\n", isEmpty(&stack) ? "Yes" : "No"); // 输出: Yes
    
    return 0;
}

5. 链式栈的应用场景

内存受限环境：当系统内存有限且难以预估栈的大小时
递归算法：深度不确定的递归调用（虽然编译器通常使用系统栈）
撤销操作：如文本编辑器的撤销功能
表达式求值：处理括号匹配、中缀转后缀等
函数调用：虽然实际由系统栈处理，但原理类似

6. 链式栈的变体与扩展

6.1 多栈共享空间

可以通过链表实现多个栈共享同一存储空间，比顺序结构的多栈共享更灵活。

6.2 泛型实现

使用void指针或宏定义可以实现支持任意数据类型的链式栈：

typedef struct GenericStackNode {
    void *data;
    struct GenericStackNode *next;
} GenericStackNode;

6.3 线程安全版本

通过添加互斥锁可以实现线程安全的链式栈：

#include <pthread.h>

typedef struct ThreadSafeStack {
    StackNode *top;
    int size;
    pthread_mutex_t lock;
} ThreadSafeStack;

7. 常见问题与注意事项

内存泄漏：每次pop操作后必须free节点
空栈检查：pop和top操作前必须检查栈是否为空
错误处理：malloc可能失败，需要处理分配失败的情况
多线程安全：多线程环境下需要额外的同步机制
性能考虑：频繁的动态内存分配可能影响性能，可考虑内存池优化

8. 总结

链式栈通过链表结构实现了栈的先进后出特性，相比顺序栈具有更好的灵活性，不受固定大小的限制。本文详细介绍了链式栈的数据结构设计、基本操作实现以及相关应用场景。理解链式栈的实现原理不仅有助于掌握栈这种基础数据结构，也为学习更复杂的链式结构打下了坚实基础。

在实际开发中，应根据具体需求选择顺序栈或链式栈。对于大小可预估且变化不大的场景，顺序栈更为高效；而对于大小不可预知或变化较大的情况，链式栈则是更好的选择。 “`