栈在c语言中可用数组或链表实现，各有优劣。1. 数组栈实现简单、访问速度快，但容量固定、扩展性差；2. 链表栈灵活可扩展、无需预设大小，但实现较复杂、访问速度慢且需额外内存存指针。性能上，数组栈通常更快因其内存连续，利于缓存；而链表栈在频繁扩展时更优。选择时若容量已知且稳定，选数组栈；若需动态扩展或不确定容量，选链表栈。此外，也可用动态数组或双端队列实现栈，以兼顾灵活性与性能。
栈，简单来说，是一种后进先出（LIFO）的数据结构。在C语言中，我们可以用数组或者链表来实现它。用数组实现更简单直接，但容量固定；用链表实现更灵活，容量可以动态扩展，但实现起来稍微复杂一点。
数组实现和链表实现各有千秋，选择哪种取决于你的具体需求。
数组栈的实现：简单直接，但容量受限
数组栈的实现非常直观。我们用一个数组来存储栈中的元素，用一个变量（通常称为
top）来记录栈顶的位置。入栈时，将元素放入
top指向的位置，然后
top加1；出栈时，
top减1，然后返回
top指向的元素。
立即学习“C语言免费学习笔记（深入）”；
#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）。
- 动态数组： 动态数组结合了数组和链表的优点，既可以像数组一样快速访问元素，又可以像链表一样动态扩展容量。
- 双端队列： 双端队列是一种可以在两端进行插入和删除操作的队列。可以使用双端队列来实现栈，只需要限制只能在一端进行插入和删除操作即可。
选择哪种实现方式，取决于具体的应用场景和性能要求。一般来说，动态数组是比数组更灵活的选择，而双端队列则提供了更多的功能，可以用于实现更复杂的数据结构。
