C语言---栈
在C语言中，栈是一种数据结构，主要用于管理函数调用和局部变量。以下是栈的基本概念：
1. **栈的结构**：栈是一种后进先出（LIFO）的数据结构，最后压入栈的元素最先被弹出。
2. **函数调用**：每当一个函数被调用时，系统会在栈上为该函数分配一个栈帧（stack frame），用于存储函数的参数、局部变量和返回地址。
3. **局部变量**：函数内部定义的变量通常存储在栈中，这些变量在函数执行结束后会被自动释放。
4. **栈的增长**：栈通常从高地址向低地址增长，随着函数的调用，栈指针（stack pointer）向下移动。
5. **栈溢出**：如果函数递归调用过深或分配过多局部变量，可能导致栈溢出（stack overflow），引发程序崩溃。
6. **效率**：栈的操作（入栈和出栈）非常快速，时间复杂度为O(1)。
栈在程序执行过程中起着重要作用，尤其是在函数调用和局部变量管理方面。
在C语言中，栈可以通过顺序存储和链式存储两种方式实现。下面是这两种实现的基本概念和示例代码。
### 1. 顺序存储实现
顺序存储栈使用数组来存储元素。其基本操作包括入栈、出栈和查看栈顶元素。
**示例代码**：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = -1;
}// 判断栈是否为空
bool isEmpty(Stack *s) {return s->top == -1;
}// 判断栈是否满
bool isFull(Stack *s) {return s->top == MAX_SIZE - 1;
}// 入栈
bool push(Stack *s, int value) {if (isFull(s)) {return false;}s->data[++(s->top)] = value;return true;
}// 出栈
bool pop(Stack *s, int *value) {if (isEmpty(s)) {return false;}*value = s->data[(s->top)--];return true;
}// 查看栈顶元素
bool peek(Stack *s, int *value) {if (isEmpty(s)) {return false;}*value = s->data[s->top];return true;
}int main() {Stack s;initStack(&s);push(&s, 10);push(&s, 20);int value;if (peek(&s, &value)) {printf("栈顶元素: %d\n", value);}pop(&s, &value);printf("出栈元素: %d\n", value);return 0;
}
### 2. 链式存储实现
链式存储栈使用链表来存储元素。每个节点包含数据和指向下一个节点的指针。
**示例代码**：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int data;struct Node *next;
} Node;typedef struct {Node *top;
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = NULL;
}// 判断栈是否为空
bool isEmpty(Stack *s) {return s->top == NULL;
}// 入栈
bool push(Stack *s, int value) {Node *newNode = (Node *)malloc(sizeof(Node));if (!newNode) {return false; // 内存分配失败}newNode->data = value;newNode->next = s->top;s->top = newNode;return true;
}// 出栈
bool pop(Stack *s, int *value) {if (isEmpty(s)) {return false;}Node *temp = s->top;*value = temp->data;s->top = temp->next;free(temp);return true;
}// 查看栈顶元素
bool peek(Stack *s, int *value) {if (isEmpty(s)) {return false;}*value = s->top->data;return true;
}int main() {Stack s;initStack(&s);push(&s, 10);push(&s, 20);int value;if (peek(&s, &value)) {printf("栈顶元素: %d\n", value);}pop(&s, &value);printf("出栈元素: %d\n", value);return 0;
}### 总结
- **顺序存储**：使用数组，简单易实现，但大小固定，可能导致栈溢出。
- **链式存储**：使用链表，动态分配内存，灵活性高，但需要额外的内存管理。
这两种实现各有优缺点，选择时应根据具体需求。