C语言中怎样实现栈结构 C语言栈的数组与链表实现对比

来源：这里教程网时间：2026-02-21 17:25:44 作者：

栈在c语言中可用数组或链表实现，各有优劣。1. 数组栈实现简单、访问速度快，但容量固定、扩展性差；2. 链表栈灵活可扩展、无需预设大小，但实现较复杂、访问速度慢且需额外内存存指针。性能上，数组栈通常更快因其内存连续，利于缓存；而链表栈在频繁扩展时更优。选择时若容量已知且稳定，选数组栈；若需动态扩展或不确定容量，选链表栈。此外，也可用动态数组或双端队列实现栈，以兼顾灵活性与性能。

栈，简单来说，是一种后进先出（LIFO）的数据结构。在C语言中，我们可以用数组或者链表来实现它。用数组实现更简单直接，但容量固定；用链表实现更灵活，容量可以动态扩展，但实现起来稍微复杂一点。

数组实现和链表实现各有千秋，选择哪种取决于你的具体需求。

数组栈的实现：简单直接，但容量受限

数组栈的实现非常直观。我们用一个数组来存储栈中的元素，用一个变量（通常称为

top

）来记录栈顶的位置。入栈时，将元素放入

top

指向的位置，然后

top

加1；出栈时，

top

减1，然后返回

top

指向的元素。

立即学习“C语言免费学习笔记（深入）”；

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;
// 初始化栈
void initStack(Stack *stack) {
    stack->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}
// 判断栈是否已满
int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}
// 入栈
void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("Stack Overflow!\n");
        return;
    }
    stack->data[++stack->top] = value;
}
// 出栈
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow!\n");
        return -1; // 或者返回其他错误值
    }
    return stack->data[stack->top--];
}
// 获取栈顶元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is Empty!\n");
        return -1; // 或者返回其他错误值
    }
    return stack->data[stack->top];
}
int main() {
    Stack stack;
    initStack(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    printf("Top element: %d\n", peek(&stack));
    printf("Popped: %d\n", pop(&stack));
    printf("Popped: %d\n", pop(&stack));
    printf("Top element: %d\n", peek(&stack));
    return 0;
}

优点：

实现简单，代码量少。 访问速度快，因为数组元素在内存中是连续存储的。

缺点：

容量固定，需要在定义时指定大小，容易造成空间浪费或溢出。 扩展性差，如果需要更大的容量，需要重新分配数组。

链表栈的实现：灵活可扩展，但稍复杂

链表栈的实现使用链表来存储栈中的元素。每个元素都是一个节点，包含数据和指向下一个节点的指针。栈顶就是链表的头节点。入栈时，创建一个新节点，将其插入到链表的头部；出栈时，移除链表的头节点。

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node *next;
} Node;
typedef struct {
    Node *top;
} Stack;
// 初始化栈
void initStack(Stack *stack) {
    stack->top = NULL;
}
// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == NULL;
}
// 入栈
void push(Stack *stack, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}
// 出栈
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow!\n");
        return -1; // 或者返回其他错误值
    }
    Node *temp = stack->top;
    int value = temp->data;
    stack->top = temp->next;
    free(temp);
    return value;
}
// 获取栈顶元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is Empty!\n");
        return -1; // 或者返回其他错误值
    }
    return stack->top->data;
}
int main() {
    Stack stack;
    initStack(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    printf("Top element: %d\n", peek(&stack));
    printf("Popped: %d\n", pop(&stack));
    printf("Popped: %d\n", pop(&stack));
    printf("Top element: %d\n", peek(&stack));
    return 0;
}

优点：

容量可以动态扩展，不需要预先指定大小。 灵活性高，可以方便地插入和删除元素。

缺点：

实现相对复杂，代码量较多。 访问速度相对较慢，因为链表元素在内存中不是连续存储的。 需要额外的内存空间来存储指针。

数组栈和链表栈在性能上有哪些差异？

在性能方面，数组栈通常比链表栈更快。这是因为数组元素在内存中是连续存储的，可以利用CPU缓存的局部性原理，提高访问速度。而链表元素在内存中是分散存储的，访问时需要通过指针来查找，会导致更多的内存访问，降低速度。

但是，在某些情况下，链表栈的性能可能更好。例如，如果需要频繁地进行入栈和出栈操作，并且栈的容量需要动态扩展，那么链表栈的优势就体现出来了。因为数组栈在扩展容量时需要重新分配内存，并将原来的元素复制到新的内存空间，这会消耗大量的时间。

如何选择数组栈和链表栈？

选择数组栈还是链表栈，需要根据具体的应用场景来考虑。

如果栈的容量事先已知，并且不需要频繁地进行扩展，那么数组栈是一个不错的选择。例如，在编译器的语法分析中，可以使用数组栈来存储操作符和操作数。 如果栈的容量事先未知，或者需要频繁地进行扩展，那么链表栈更适合。例如，在浏览器的历史记录中，可以使用链表栈来存储用户访问过的页面。 如果对性能要求非常高，并且栈的容量不大，那么可以考虑使用循环数组来实现栈。循环数组可以避免数组栈在扩展容量时重新分配内存的开销。