数据结构-------栈

顺序栈：

一、数据结构定义

1. 数据元素 DATATYPE

typedef struct person {char name[32];char sex;int age;int score;
} DATATYPE;

1. 顺序栈结构 SeqStack

typedef struct list {DATATYPE *head;  // 栈空间首地址int tlen;        // 栈总容量（total length）int top;         // 栈顶指针（相当于当前元素计数）
} SeqStack;

二、核心操作接口

1. 创建栈

SeqStack *CreateSeqStack(int size)
{SeqStack *ss = malloc(sizeof(SeqStack));if (NULL == ss){perror("CreateSeqStack malloc error\n");return NULL;}ss->head = malloc(sizeof(DATATYPE) * size);if (NULL == ss){perror("CreateSeqStack malloc2 error\n");return NULL;}ss->tlen = size;ss->top = 0;return ss;
}

• 实现要点：
  • 动态分配结构体内存
  • 分配连续存储空间：head = malloc(size * sizeof(DATATYPE))
  • 初始化tlen = size, top = 0

1. 销毁栈

int DestroySeqStack(SeqStack *ss)
{if (NULL == ss){fprintf(stderr, "DestroySeqStack pamter error\n");return 1;}free(ss->head);free(ss);return 0;
}

• 内存释放顺序：
  1. 释放数据空间 free(ss->head)
  2. 释放控制结构 free(ss)

1. 入栈操作

int PushSeqStack(SeqStack *ss, DATATYPE *data) // add
{if (NULL == ss || NULL == data || IsFullSeqStack(ss)){fprintf(stderr, "PushSeqStack pamter error\n");return 1;}memcpy(&ss->head[ss->top], data, sizeof(DATATYPE));ss->top++;return 0;
}

• 实现流程：

if 栈未满：复制数据到ss->head[top]位置top++返回成功
else：返回失败

1. 出栈操作

int PopSeqStack(SeqStack *ss)
{if (NULL == ss){fprintf(stderr, "PopSeqStack pamter error\n");return 1;}ss->top--;return 0;
}

• 实现逻辑：

if 栈非空：top--返回成功
else：返回失败

1. 判空操作

int IsEmpySeqStack(SeqStack *ss)
{return 0 == ss->top;
}

• 判断条件：top == 0

1. 判满操作

int IsFullSeqStack(SeqStack *ss)
{return ss->tlen == ss->top;
}

• 判断条件：top == tlen

1. 获取栈顶元素

DATATYPE *GetTopSeqStack(SeqStack *ss)
{if (NULL == ss || IsEmpySeqStack(ss)){fprintf(stderr, "GetTopSeqStack pamter error\n");return NULL;}return &ss->head[ss->top - 1];
}

• 注意点：
  • 返回ss->head[top-1]的地址
  • 需先判断栈是否为空

1. 获取栈大小

int GetSizeSeqStack(SeqStack *ss)
{if (NULL == ss ){fprintf(stderr, "GetSizeSeqStack pamter error\n");return 1;}return ss->top;
}

• 直接返回top值

三、存储结构示意图

栈底 → head[0]head[1]...
栈顶 → head[top-1]  ← 当前有效元素head[top]    ← 下一个可用位置（当top<tlen时）...head[tlen-1]

四、时间复杂度分析

操作	时间复杂度	说明
创建栈	O(1)	内存分配操作
销毁栈	O(1)	内存释放操作
入栈/出栈	O(1)	直接操作栈顶指针
获取栈顶元素	O(1)	随机访问特性
获取栈大小	O(1)	直接读取top值

五、优势与局限

1. 优势：

   • 随机访问特性，支持快速定位
   • 内存连续，缓存命中率高
   • 操作时间复杂度均为O(1)

2. 局限：

   • 固定容量，需要预先分配空间
   • 扩容成本高（需要重新分配内存）
   • 可能产生空间浪费（分配未使用的空间）

六、典型应用场景

1. 函数调用栈的实现
2. 表达式求值（中缀转后缀表达式）
3. 括号匹配检测
4. 浏览器的后退操作栈
5. 撤销/重做功能实现

七、实现注意事项

1. 内存管理：

   • 创建时需分配两次内存（控制结构+数据空间）
   • 销毁时需按相反顺序释放

2. 临界条件处理：

   • 入栈前必须检查栈是否已满
   • 出栈前必须检查栈是否为空
   • 获取栈顶元素前必须检查非空