CA1-栈的数据结构定义
1. 顺序存储栈实现
| C |
|---|
| #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 100 // 栈的最大容量
// 顺序栈结构定义
typedef struct {
int data[MAXSIZE]; // 存储栈元素的数组
int top; // 栈顶指针，-1表示空栈
} SeqStack;
/**
* 初始化顺序栈
* @return 指向初始化栈的指针
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
SeqStack* initSeqStack() {
SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
if (stack == NULL) {
return NULL; // 内存分配失败
}
stack->top = -1; // 初始化栈顶指针为-1，表示空栈
return stack;
}
/**
* 判断顺序栈是否为空
* @param stack 栈指针
* @return true表示空栈，false表示非空栈
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool isEmpty(SeqStack* stack) {
return stack->top == -1; // 栈顶指针为-1表示空栈
}
/**
* 判断顺序栈是否已满
* @param stack 栈指针
* @return true表示已满，false表示未满
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool isFull(SeqStack* stack) {
return stack->top == MAXSIZE - 1; // 栈顶指针达到最大索引表示已满
}
/**
* 入栈操作
* @param stack 栈指针
* @param element 要入栈的元素
* @return true表示成功，false表示失败
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool push(SeqStack* stack, int element) {
// 检查栈是否已满
if (isFull(stack)) {
printf("栈已满，无法入栈\n");
return false;
}
// 栈顶指针上移，然后存入元素
stack->top++;
stack->data[stack->top] = element;
return true;
}
/**
* 出栈操作
* @param stack 栈指针
* @param element 用于接收出栈元素的指针
* @return true表示成功，false表示失败
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool pop(SeqStack* stack, int* element) {
// 检查栈是否为空
if (isEmpty(stack)) {
printf("栈为空，无法出栈\n");
return false;
}
// 取出栈顶元素，然后栈顶指针下移
*element = stack->data[stack->top];
stack->top--;
return true;
}
/**
* 获取栈顶元素（不删除）
* @param stack 栈指针
* @param element 用于接收栈顶元素的指针
* @return true表示成功，false表示失败
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool getTop(SeqStack* stack, int* element) {
// 检查栈是否为空
if (isEmpty(stack)) {
printf("栈为空，无法获取栈顶元素\n");
return false;
}
// 直接返回栈顶元素，不改变栈顶指针
*element = stack->data[stack->top];
return true;
}
/**
* 获取栈中元素个数
* @param stack 栈指针
* @return 栈中元素个数
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
int getSize(SeqStack* stack) {
return stack->top + 1; // 栈顶指针从-1开始，所以元素个数为top+1
}
/**
* 销毁顺序栈
* @param stack 栈指针
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
void destroySeqStack(SeqStack* stack) {
if (stack != NULL) {
free(stack); // 释放栈结构体内存
}
}
|
2. 链式存储栈实现
| C |
|---|
| // 链式栈节点结构定义
typedef struct StackNode {
int data; // 节点数据
struct StackNode* next; // 指向下一个节点的指针
} StackNode;
// 链式栈结构定义
typedef struct {
StackNode* top; // 栈顶指针
int size; // 栈中元素个数
} LinkStack;
/**
* 创建新节点
* @param element 节点数据
* @return 指向新节点的指针
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
StackNode* createNode(int element) {
StackNode* node = (StackNode*)malloc(sizeof(StackNode));
if (node == NULL) {
return NULL; // 内存分配失败
}
node->data = element;
node->next = NULL;
return node;
}
/**
* 初始化链式栈
* @return 指向初始化栈的指针
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
LinkStack* initLinkStack() {
LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
if (stack == NULL) {
return NULL; // 内存分配失败
}
stack->top = NULL; // 初始化栈顶指针为空
stack->size = 0; // 初始化栈大小为0
return stack;
}
/**
* 判断链式栈是否为空
* @param stack 栈指针
* @return true表示空栈，false表示非空栈
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool isLinkEmpty(LinkStack* stack) {
return stack->top == NULL; // 栈顶指针为空表示空栈
}
/**
* 入栈操作（链式存储）
* @param stack 栈指针
* @param element 要入栈的元素
* @return true表示成功，false表示失败
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool linkPush(LinkStack* stack, int element) {
// 创建新节点
StackNode* newNode = createNode(element);
if (newNode == NULL) {
printf("内存分配失败，无法入栈\n");
return false;
}
// 将新节点插入到链表头部（栈顶）
newNode->next = stack->top;
stack->top = newNode;
stack->size++; // 栈大小加1
return true;
}
/**
* 出栈操作（链式存储）
* @param stack 栈指针
* @param element 用于接收出栈元素的指针
* @return true表示成功，false表示失败
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool linkPop(LinkStack* stack, int* element) {
// 检查栈是否为空
if (isLinkEmpty(stack)) {
printf("栈为空，无法出栈\n");
return false;
}
// 保存栈顶节点
StackNode* temp = stack->top;
// 获取栈顶元素值
*element = temp->data;
// 栈顶指针指向下一个节点
stack->top = temp->next;
// 释放原栈顶节点内存
free(temp);
stack->size--; // 栈大小减1
return true;
}
/**
* 获取栈顶元素（不删除）
* @param stack 栈指针
* @param element 用于接收栈顶元素的指针
* @return true表示成功，false表示失败
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
bool linkGetTop(LinkStack* stack, int* element) {
// 检查栈是否为空
if (isLinkEmpty(stack)) {
printf("栈为空，无法获取栈顶元素\n");
return false;
}
// 直接返回栈顶元素值
*element = stack->top->data;
return true;
}
/**
* 获取栈中元素个数
* @param stack 栈指针
* @return 栈中元素个数
* 时间复杂度: O(1)
* 空间复杂度: O(1)
*/
int getLinkSize(LinkStack* stack) {
return stack->size;
}
/**
* 销毁链式栈
* @param stack 栈指针
* 时间复杂度: O(n)，其中n为栈中元素个数
* 空间复杂度: O(1)
*/
void destroyLinkStack(LinkStack* stack) {
if (stack != NULL) {
// 逐个释放栈中所有节点
StackNode* current = stack->top;
while (current != NULL) {
StackNode* temp = current;
current = current->next;
free(temp);
}
// 释放栈结构体内存
free(stack);
}
}
|
3. 核心函数详解
3.1 顺序栈核心函数
- initSeqStack(): 初始化栈结构，设置栈顶指针为-1
- push(): 入栈操作，先移动栈顶指针再存储元素
- pop(): 出栈操作，先取出元素再移动栈顶指针
- getTop(): 查看栈顶元素但不删除
- isEmpty()/isFull(): 判断栈状态
3.2 链式栈核心函数
- initLinkStack(): 初始化栈结构，栈顶指针设为NULL
- linkPush(): 在链表头部插入新节点
- linkPop(): 删除链表头部节点
- linkGetTop(): 获取头节点数据
- isLinkEmpty(): 判断栈是否为空
4. 复杂度分析
graph TD
A[栈实现方式] --> B[顺序存储]
A --> C[链式存储]
B --> B1[时间复杂度]
B --> B2[空间复杂度]
C --> C1[时间复杂度]
C --> C2[空间复杂度]
B1 --> B11["入栈/出栈: O(1)"]
B1 --> B12["获取栈顶: O(1)"]
B1 --> B13["判断空满: O(1)"]
B2 --> B21["总体: O(n)"]
B2 --> B22["预分配固定空间"]
C1 --> C11["入栈/出栈: O(1)"]
C1 --> C12["获取栈顶: O(1)"]
C1 --> C13["判断空: O(1)"]
C2 --> C21["总体: O(n)"]
C2 --> C22["动态分配空间"]
4.1 顺序存储栈复杂度
时间复杂度：
- 入栈(push): O(1) - 直接在数组末尾添加元素
- 出栈(pop): O(1) - 直接从数组末尾删除元素
- 获取栈顶(getTop): O(1) - 直接访问数组元素
- 判断空/满: O(1) - 简单比较操作
空间复杂度：
- 总体空间: O(n) - 需要预先分配固定大小的数组空间
- 优点: 空间利用率高，无额外指针开销
- 缺点: 容量固定，可能造成空间浪费或溢出
4.2 链式存储栈复杂度
时间复杂度：
- 入栈(linkPush): O(1) - 在链表头部插入节点
- 出栈(linkPop): O(1) - 删除链表头部节点
- 获取栈顶(linkGetTop): O(1) - 访问头节点
- 判断空: O(1) - 检查头指针是否为空
空间复杂度：
- 总体空间: O(n) - 每个节点需要额外的指针空间
- 优点: 动态分配，容量可变，不会浪费空间
- 缺点: 每个节点有额外的指针开销，内存不连续
5. 两种实现方式对比
| 特性 |
顺序存储栈 |
链式存储栈 |
| 内存分配 |
静态分配，预分配固定空间 |
动态分配，按需分配 |
| 空间效率 |
高，无额外指针开销 |
低，每个节点有指针开销 |
| 容量限制 |
固定容量，可能溢出 |
理论上无限制 |
| 访问速度 |
快，数组随机访问 |
快，头节点操作 |
| 内存使用 |
连续内存块 |
非连续内存块 |
| 实现复杂度 |
简单 |
相对复杂 |
选择建议：
- 当栈大小可预估且变化不大时，选择顺序存储栈
- 当栈大小变化较大或无法预估时，选择链式存储栈