C语言栈实现方法及数组链表对比

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

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

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

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

数组栈的实现非常直观。我们用一个数组来存储栈中的元素，用一个变量（通常称为top）来记录栈顶的位置。入栈时，将元素放入top指向的位置，然后top加1；出栈时，top减1，然后返回top指向的元素。

#include 
#include 

#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 
#include 

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缓存的局部性原理，提高访问速度。而链表元素在内存中是分散存储的，访问时需要通过指针来查找，会导致更多的内存访问，降低速度。

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

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

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

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

除了数组和链表，还有其他实现栈的方法吗？

除了数组和链表，还可以使用其他数据结构来实现栈，例如动态数组（如C++中的vector）和双端队列（deque）。

• 动态数组： 动态数组结合了数组和链表的优点，既可以像数组一样快速访问元素，又可以像链表一样动态扩展容量。
• 双端队列： 双端队列是一种可以在两端进行插入和删除操作的队列。可以使用双端队列来实现栈，只需要限制只能在一端进行插入和删除操作即可。

选择哪种实现方式，取决于具体的应用场景和性能要求。一般来说，动态数组是比数组更灵活的选择，而双端队列则提供了更多的功能，可以用于实现更复杂的数据结构。