顺序栈是数据结构中“栈”的一种具体实现方式，我们将从以下几个方面来理解它：
（图片来源网络，侵删）
- 什么是栈？
- 什么是顺序栈？
- 顺序栈的 C 语言实现（完整代码）
- 核心操作的时间复杂度分析
- 顺序栈的优缺点
- 一个更完整的实践示例
什么是栈？
栈是一种后进先出的线性数据结构，你可以把它想象成一个只有一个开口的箱子或者一摞盘子。
- LIFO (Last-In, First-Out)：最后放进去的元素，最先被取出来。
- 基本操作：
push(入栈/压栈)：将一个新元素放到栈顶。pop(出栈/弹栈)：从栈顶取出一个元素。peek(查看栈顶元素)：只看栈顶的元素是什么，但不把它取出来。isEmpty(判空)：检查栈是否为空。isFull(判满)：检查栈是否已满（对于固定大小的栈很重要）。
什么是顺序栈？
顺序栈是使用数组作为底层存储结构来实现栈，它通过一个数组来存放栈中的所有元素，并用一个变量（通常是 top）来记录当前栈顶元素的位置。
- 核心思想：利用数组的连续存储空间和下标访问的便利性。
- 关键变量：
data[]: 存储元素的数组。top: 栈顶指针，它通常指向栈顶元素所在位置的下一个空位，或者指向栈顶元素本身，我们这里采用更常见的“指向下一个空位”的方式，这样top的初始值就是 0，表示栈为空时，第一个元素可以放在data[0]。
顺序栈的 C 语言实现（完整代码）
下面是一个完整的、包含注释的顺序栈实现。
1 定义顺序栈的结构体
我们定义一个结构体来封装栈的所有信息：数组、最大容量和栈顶指针。
（图片来源网络，侵删）
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // 为了使用 bool 类型
// 定义栈中元素的最大容量
#define MAX_SIZE 100
// 定义顺序栈的结构体
typedef struct {
int data[MAX_SIZE]; // 存储元素的数组
int top; // 栈顶指针，指向栈顶元素的下一个位置
} SeqStack;
2 核心操作的函数实现
我们为这个栈结构实现各种基本操作。
2.1 初始化栈
创建一个空栈,只需将 top 指针设置为 0 即可。
// 初始化栈
void initStack(SeqStack *s) {
s->top = 0; // top 指向数组第一个位置，表示栈为空
}
2.2 判断栈是否为空
top 为 0，说明没有任何元素被压入，栈为空。
// 判断栈是否为空
bool isEmpty(SeqStack *s) {
return s->top == 0;
}
2.3 判断栈是否已满
top 等于 MAX_SIZE，说明数组已经全部用完，栈已满。
（图片来源网络，侵删）
// 判断栈是否已满
bool isFull(SeqStack *s) {
return s->top == MAX_SIZE;
}
2.4 入栈操作
将一个元素压入栈顶,需要先检查栈是否已满。
// 入栈操作
bool push(SeqStack *s, int value) {
if (isFull(s)) {
printf("栈已满，无法入栈！\n");
return false; // 入栈失败
}
s->data[s->top] = value; // 将元素存入 top 指向的位置
s->top++; // top 指针向上移动，指向下一个空位
return true; // 入栈成功
}
2.5 出栈操作
从栈顶弹出一个元素,需要先检查栈是否为空。
// 出栈操作
bool pop(SeqStack *s, int *value) {
if (isEmpty(s)) {
printf("栈为空，无法出栈！\n");
return false; // 出栈失败
}
s->top--; // top 指针先向下移动，指向栈顶元素
*value = s->data[s->top]; // 获取栈顶元素的值
return true; // 出栈成功
}
2.6 查看栈顶元素
与出栈类似,只是不移动 top 指针。
// 查看栈顶元素
bool peek(SeqStack *s, int *value) {
if (isEmpty(s)) {
printf("栈为空，无栈顶元素！\n");
return false;
}
// top 指向下一个空位，所以栈顶元素在 top-1 的位置
*value = s->data[s->top - 1];
return true;
}
2.7 打印栈中所有元素
这个操作在标准的栈定义中不是必须的,但为了方便调试和演示，我们通常会实现它。
// 打印栈中所有元素（从栈底到栈顶）
void printStack(SeqStack *s) {
if (isEmpty(s)) {
printf("栈为空，\n");
return;
}
printf("栈内元素 (从栈底到栈顶): ");
for (int i = 0; i < s->top; i++) {
printf("%d ", s->data[i]);
}
printf("\n");
}
核心操作的时间复杂度分析
initStack: O(1) - 只是一个简单的赋值操作。isEmpty,isFull: O(1) - 只是比较一个整数值。push,pop,peek: O(1) - 这些操作都只涉及对top指针和数组的单个元素访问，不涉及循环或遍历。
顺序栈的所有基本操作都是常数时间,效率非常高。
顺序栈的优缺点
优点
- 实现简单：基于数组，逻辑直观，代码容易编写和理解。
- 效率高：所有核心操作的时间复杂度都是 O(1)。
- 内存访问连续：数组在内存中是连续存储，CPU 缓存命中率较高，访问速度比链式实现的栈（基于链表）可能更快。
缺点
- 大小固定：数组的大小在编译时或初始化时就已经确定（
MAX_SIZE），如果元素数量超过这个限制，就会发生栈溢出。 - 空间浪费：如果栈中元素很少，但
MAX_SIZE设置得很大，就会浪费内存空间，反之，如果设置得太小，又不够用。
一个更完整的实践示例
下面是一个 main 函数，演示如何使用上面定义的顺序栈。
int main() {
SeqStack myStack;
int value;
// 1. 初始化
initStack(&myStack);
printf("栈已初始化，\n");
// 2. 入栈操作
printf("\n--- 入栈操作 ---\n");
push(&myStack, 10);
push(&myStack, 20);
push(&myStack, 30);
printStack(&myStack); // 预期输出: 10 20 30
// 3. 查看栈顶元素
printf("\n--- 查看栈顶元素 ---\n");
if (peek(&myStack, &value)) {
printf("栈顶元素是: %d\n", value); // 预期输出: 30
}
// 4. 出栈操作
printf("\n--- 出栈操作 ---\n");
if (pop(&myStack, &value)) {
printf("出栈元素: %d\n", value); // 预期输出: 30
}
if (pop(&myStack, &value)) {
printf("出栈元素: %d\n", value); // 预期输出: 20
}
printStack(&myStack); // 预期输出: 10
// 5. 再次出栈
printf("\n--- 继续出栈 ---\n");
if (pop(&myStack, &value)) {
printf("出栈元素: %d\n", value); // 预期输出: 10
}
printStack(&myStack); // 预期输出: 栈为空。
// 6. 尝试从空栈出栈
printf("\n--- 尝试从空栈出栈 ---\n");
pop(&myStack, &value); // 应该打印 "栈为空，无法出栈！"
// 7. 测试栈满
printf("\n--- 测试栈满 ---\n");
for (int i = 0; i < MAX_SIZE; i++) {
push(&myStack, i + 1);
}
printStack(&myStack); // 预期输出 1 到 100
push(&myStack, 101); // 应该打印 "栈已满，无法入栈！"
return 0;
}
顺序栈是学习栈和数组这两个基础概念的一个绝佳结合,它通过一个简单的结构体和几个核心函数，高效地实现了“后进先出”的逻辑，虽然它有大小固定的局限性，但在许多场景下（如表达式求值、函数调用栈、括号匹配等）都非常实用，如果需要动态大小的栈，可以考虑使用链式栈。
