C语言中怎样实现栈结构 C语言栈的数组与链表实现对比-C#.Net教程-PHP中文网

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

尼克

发布： 2025-09-15 09:20:01

原创

285人浏览过

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

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

栈，简单来说，是一种后进先出（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;
}

登录后复制

优点：

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

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

缺点：

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

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

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

#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;
}

登录后复制

优点：