C语言怎么实现栈

# C语言怎么实现栈

## 1. 栈的基本概念

### 1.1 什么是栈
栈（Stack）是一种特殊的线性数据结构，它遵循**后进先出（LIFO, Last In First Out）**的原则。这意味着最后入栈的元素会最先被取出，类似于我们日常生活中叠放的盘子——总是从最上面取用。

### 1.2 栈的特性
- **限定性操作**：只允许在栈顶进行插入（push）和删除（pop）操作
- **单向性**：数据只能从栈顶进出
- **动态性**：栈的大小可动态变化（取决于实现方式）

### 1.3 栈的常见操作
| 操作 | 描述 |
|------|------|
| Push | 将元素压入栈顶 |
| Pop  | 移除并返回栈顶元素 |
| Peek/Top | 查看栈顶元素但不移除 |
| isEmpty | 检查栈是否为空 |
| isFull | 检查栈是否已满（固定大小栈） |

## 2. 栈的C语言实现方式

### 2.1 基于数组的实现（顺序栈）

#### 2.1.1 数据结构定义
```c
#define MAX_SIZE 100  // 栈的最大容量

typedef struct {
    int data[MAX_SIZE];
    int top;          // 栈顶指针
} ArrayStack;

2.1.2 初始化栈

void initStack(ArrayStack *stack) {
    stack->top = -1;  // 初始状态下栈为空
}

2.1.3 入栈操作

int push(ArrayStack *stack, int value) {
    if (stack->top >= MAX_SIZE - 1) {
        printf("Stack Overflow!\n");
        return 0;  // 入栈失败
    }
    stack->data[++stack->top] = value;
    return 1;  // 入栈成功
}

2.1.4 出栈操作

int pop(ArrayStack *stack) {
    if (stack->top == -1) {
        printf("Stack Underflow!\n");
        return INT_MIN;  // 返回最小值表示错误
    }
    return stack->data[stack->top--];
}

2.1.5 其他辅助操作

// 查看栈顶元素
int peek(ArrayStack *stack) {
    if (stack->top == -1) {
        printf("Stack is empty!\n");
        return INT_MIN;
    }
    return stack->data[stack->top];
}

// 检查栈是否为空
int isEmpty(ArrayStack *stack) {
    return stack->top == -1;
}

// 检查栈是否已满
int isFull(ArrayStack *stack) {
    return stack->top == MAX_SIZE - 1;
}

2.2 基于链表的实现（链式栈）

2.2.1 节点结构定义

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

2.2.2 栈结构定义

typedef struct {
    StackNode *top;  // 栈顶指针
    int size;        // 栈当前大小（可选）
} LinkedStack;

2.2.3 初始化栈

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

2.2.4 入栈操作

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

2.2.5 出栈操作

int linkedPop(LinkedStack *stack) {
    if (stack->top == NULL) {
        printf("Stack Underflow!\n");
        return INT_MIN;
    }
    StackNode *temp = stack->top;
    int popped = temp->data;
    stack->top = stack->top->next;
    free(temp);
    stack->size--;
    return popped;
}

3. 两种实现方式的对比

特性	数组实现	链表实现
内存分配	静态固定大小	动态分配
空间效率	可能浪费或不足	按需分配
时间复杂度	所有操作O(1)	所有操作O(1)
实现复杂度	较简单	较复杂（需处理指针）
扩容难度	困难（需重新分配）	容易（自动扩展）
缓存友好性	好（连续内存）	较差（内存不连续）

4. 栈的应用实例

4.1 括号匹配检查

int isBalanced(char expr[]) {
    ArrayStack stack;
    initStack(&stack);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
            push(&stack, expr[i]);
        } else {
            if (isEmpty(&stack)) return 0;
            
            char top = pop(&stack);
            if ((expr[i] == ')' && top != '(') || 
                (expr[i] == ']' && top != '[') || 
                (expr[i] == '}' && top != '{')) {
                return 0;
            }
        }
    }
    return isEmpty(&stack);
}

4.2 表达式求值（后缀表达式）

int evaluatePostfix(char* exp) {
    ArrayStack stack;
    initStack(&stack);
    
    for (int i = 0; exp[i]; i++) {
        if (isdigit(exp[i])) {
            push(&stack, exp[i] - '0');
        } else {
            int val1 = pop(&stack);
            int val2 = pop(&stack);
            switch (exp[i]) {
                case '+': push(&stack, val2 + val1); break;
                case '-': push(&stack, val2 - val1); break;
                case '*': push(&stack, val2 * val1); break;
                case '/': push(&stack, val2 / val1); break;
            }
        }
    }
    return pop(&stack);
}

5. 高级话题与优化

5.1 动态扩容的顺序栈

当数组实现的栈容量不足时，可以自动扩容：

typedef struct {
    int *data;        // 动态数组指针
    int top;          // 栈顶指针
    int capacity;     // 当前容量
} DynamicStack;

void resize(DynamicStack *stack) {
    stack->capacity *= 2;
    stack->data = realloc(stack->data, stack->capacity * sizeof(int));
    if (!stack->data) {
        printf("Memory reallocation failed!\n");
        exit(1);
    }
}

5.2 多栈共享同一存储空间

#define TOTAL_SIZE 200

typedef struct {
    int data[TOTAL_SIZE];
    int top1;         // 栈1的栈顶指针
    int top2;         // 栈2的栈顶指针
} DoubleStack;

// 初始化双栈
void initDoubleStack(DoubleStack *stack) {
    stack->top1 = -1;
    stack->top2 = TOTAL_SIZE;
}

// 栈1的push操作
int push1(DoubleStack *stack, int value) {
    if (stack->top1 + 1 >= stack->top2) {
        printf("Stack Overflow!\n");
        return 0;
    }
    stack->data[++stack->top1] = value;
    return 1;
}

6. 常见问题与调试技巧

6.1 常见错误

1. 栈溢出：未检查栈是否已满就执行push操作
2. 栈下溢：未检查栈是否为空就执行pop操作
3. 内存泄漏：链式栈中pop操作后未释放节点内存
4. 野指针：链式栈操作后未正确处理指针关系

6.2 调试建议

• 在关键操作前后打印栈状态
• 使用assert检查前置条件
• 编写单元测试验证边界条件
• 使用Valgrind等工具检测内存问题

7. 扩展阅读与参考资料

1. 《数据结构与算法分析：C语言描述》 - Mark Allen Weiss
2. 《算法导论》 - Thomas H. Cormen 等
3. Linux内核中的栈实现（kfifo）
4. C++ STL stack容器源码分析
5. 计算机系统栈的工作原理（调用栈）

8. 完整示例代码

8.1 基于数组的完整实现

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

#define MAX_SIZE 10  // 减小栈大小便于测试溢出

typedef struct {
    int data[MAX_SIZE];
    int top;
} ArrayStack;

void initStack(ArrayStack *stack) {
    stack->top = -1;
}

int isFull(ArrayStack *stack) {
    return stack->top == MAX_SIZE - 1;
}

int isEmpty(ArrayStack *stack) {
    return stack->top == -1;
}

int push(ArrayStack *stack, int value) {
    if (isFull(stack)) {
        printf("Stack Overflow!\n");
        return 0;
    }
    stack->data[++stack->top] = value;
    printf("Pushed %d to stack\n", value);
    return 1;
}

int pop(ArrayStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow!\n");
        return INT_MIN;
    }
    printf("Popped %d from stack\n", stack->data[stack->top]);
    return stack->data[stack->top--];
}

void display(ArrayStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return;
    }
    printf("Stack elements: ");
    for (int i = 0; i <= stack->top; i++) {
        printf("%d ", stack->data[i]);
    }
    printf("\n");
}

int main() {
    ArrayStack stack;
    initStack(&stack);
    
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    display(&stack);
    
    pop(&stack);
    display(&stack);
    
    // 测试栈溢出
    for (int i = 0; i < MAX_SIZE + 2; i++) {
        push(&stack, i);
    }
    
    // 测试栈下溢
    for (int i = 0; i < MAX_SIZE + 2; i++) {
        pop(&stack);
    }
    
    return 0;
}

8.2 基于链表的完整实现

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

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

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

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

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

void linkedPush(LinkedStack *stack, int value) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        return;
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
    printf("Pushed %d to stack\n", value);
}

int linkedPop(LinkedStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow!\n");
        return INT_MIN;
    }
    StackNode *temp = stack->top;
    int popped = temp->data;
    stack->top = stack->top->next;
    free(temp);
    stack->size--;
    printf("Popped %d from stack\n", popped);
    return popped;
}

void display(LinkedStack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return;
    }
    printf("Stack elements (size=%d): ", stack->size);
    StackNode *current = stack->top;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    LinkedStack stack;
    initLinkedStack(&stack);
    
    linkedPush(&stack, 100);
    linkedPush(&stack, 200);
    linkedPush(&stack, 300);
    display(&stack);
    
    linkedPop(&stack);
    display(&stack);
    
    // 测试大量操作
    for (int i = 0; i < 20; i++) {
        linkedPush(&stack, i);
    }
    display(&stack);
    
    for (int i = 0; i < 25; i++) {
        linkedPop(&stack);
    }
    display(&stack);
    
    return 0;
}

9. 总结

本文详细介绍了在C语言中实现栈的两种主要方式：基于数组的顺序栈和基于链表的链式栈。通过对比分析，我们可以得出以下结论：

1. 数组实现适合已知最大容量或对性能要求高的场景
2. 链表实现适合需要动态扩容或不确定最大容量的场景
3. 栈的核心操作（push/pop）时间复杂度均为O(1)
4. 正确实现栈需要注意边界条件检查和内存管理

栈作为基础数据结构，在编译器设计、操作系统、算法等领域有广泛应用。掌握其实现原理和特性，对于提高编程能力和理解复杂系统都有重要意义。 “`

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>