文章目录
- 前言
- 1、栈
- 1.1栈的概念和定义
- 1.1.2栈的基本概念：
- 1.2栈的方法(接口)
- 1.3栈的实现方法
- 1.4栈的性质
- 1.5栈的应用
- 1.6栈的结构
- 2、栈的实现
- 2.1 顺序栈
- 2.1.1 顺序栈的结构体
- 2.1.2 顺序栈的初始化
- 2.1.3 顺序栈的销毁
- 2.1.4 顺序栈的入栈
- 2.1.5 顺序栈的出栈
- 2.1.5 顺序栈的判空
- 2.1.5 顺序栈的栈顶元素
- 2.1.5 顺序栈的有效个数
- 2、顺序栈的完整代码实现
前言
前面讲解了数据结构中的链表、顺序表，接下来就是栈了
1、栈
1.1栈的概念和定义
栈是一种限定仅在表尾进行插入或删除操作的线性表。这一端被称为栈顶（top），相对地，另一端被称为栈底（bottom）。栈顶是允许操作的，而栈底是固定的。栈的插入操作通常称为进栈/压栈/入栈（PUSH），而删除操作则称为退栈/出栈（POP）。
1.1.2栈的基本概念：
栈顶(top)和栈底(bottom)：
- 栈顶：栈顶是栈中最后一个被插入或删除的元素的位置。当新的元素被添加到栈中时，它被放置在栈顶；同样，当元素从栈中被删除时，也是从栈顶开始删除的。
- 栈底：它表示栈的起始位置或者说是最早被插入的元素所在的位置，栈底是固定的。
1.2栈的方法(接口)
Push（入栈/压栈）：在栈顶位置压入一个新数据。Pop（出栈）：从栈顶位置删除一个数据。Top：获取栈顶数据Size：获取栈的有效数据个数Empty：判断栈是否为空
1.3栈的实现方法
栈（Stack）的实现方法主要有两种：基于数组的实现和基于链表的实现。数组实现栈比较简单，需要使用realloc来扩容，使用链表来实现就不需要扩容了，可以按需申请空间，插入和删除操作的时间复杂度都为O(1)。
1.4栈的性质
- 后进先出（LIFO）：栈遵循后进先出（Last In First Out）的原则，即最后进入栈的元素将最先被移出栈。这是栈最显著的特点。
- 集合性：栈是由若干个元素集合而成，当没有元素的空集合称为空栈。
- 线性结构：栈在逻辑上呈现一种线性结构，使用数组的话在物理逻辑上是连续的，但不同于普通的线性表，栈的插入和删除操作仅在一端（栈顶）进行。
- 数学性质：当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔兰数列的计算，即Cn = C(2n, n) / (n+1)，其中n为编号元素的个数，Cn是可能的排列数目。
- 栈的大小限制：栈的大小通常是有限的，当栈满时，不能再进行进栈操作，否则会引发溢出错误；当栈空时，不能再进行出栈操作，否则会引发下溢错误。
1.5栈的应用
- 函数调用：当一个函数调用另一个函数时，操作系统会给每个线程分配一块内存空间，这块内存被组织成栈结构。每个函数调用都需要将当前状态的信息（如函数调用前的参数、局部变量和程序计数器等）保存到栈中，等到函数调用结束后再从栈中弹出这些信息，恢复调用前的状态。这个过程被称作函数的压栈和弹栈操作。
- 表达式求值：在计算机中，对算术表达式进行求值时，通常使用栈来实现。编译器可以通过两个栈来实现，一个栈用来保存操作数，另一个栈用来保存运算符。从左到右遍历表达式，当遇到数字时，将其压入操作数栈；当遇到运算符时，与运算符栈栈顶元素进行比较，根据运算符的优先级进行相应的压栈或出栈操作，并计算表达式的值。
系统调用：在操作系统中，内核通常会将一个系统调用的参数、返回值和程序计数器等状态保存到进程的用户栈中，在系统调用结束后再从栈中弹出这些信息，恢复调用前的状态。
递归实现的非递归化：某些递归算法可以通过使用栈的数据结构转换为非递归形式，通过手动管理栈来模拟递归调用的过程。
1.6栈的结构
2、栈的实现
栈的实现可以使用数组来完成，也可以使用链表来完成，使用数组来完成相对简单，
2.1 顺序栈
顺序栈是使用顺序存储结构（数组）实现的栈，即利用一段连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设一个指针（通常称为栈顶指针）指示当前栈顶元素的位置。顺序栈具有结构简单、操作方便、易于实现等优点，因此在实际应用中非常广泛。
2.1.1 顺序栈的结构体
typedef int SDataType;
typedef struct Stack
{
SDataType* _a;
int _top;
int _capacity;
}Stack;
栈结构里面有三个成员，一个栈顶，一个栈的数组，一个栈的总容量
2.1.2 顺序栈的初始化
void StackInit(Stack* ps)
{
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
这里有两种方法初始化，一个是top始终指向栈顶的下一个元素的索引，一个是top始终是栈顶元素的索引。
2.1.3 顺序栈的销毁
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
2.1.4 顺序栈的入栈
// 入栈
void StackPush(Stack* ps, SDataType data)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
int _newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
SDataType* _new_a = (SDataType*)realloc(ps, _newcapacity * sizeof(SDataType));
if (_new_a == NULL)
{
perror("StackPush()::realloc()");
exit(-1);
}
ps->_a = _new_a;
ps->_capacity = _newcapacity;
}
ps->_a[ps->_top++] = data;
}
2.1.5 顺序栈的出栈
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
ps->_top--;
}
2.1.5 顺序栈的判空
// 判空
void StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0;
}
2.1.5 顺序栈的栈顶元素
// 获取栈顶元素
void StackTop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
return ps->_a[ps->_top - 1];
}
2.1.5 顺序栈的有效个数
// 计算栈内有效个数
void StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
2、顺序栈的完整代码实现
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
typedef int SDataType;
typedef struct Stack
{
SDataType* _a;
int _top;
int _capacity;
}Stack;
// 初始化
void StackInit(Stack* ps)
{
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
// 入栈
void StackPush(Stack* ps, SDataType data)
{
assert(ps);
if (ps->_top == ps->_capacity)
{
int _newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
SDataType* _new_a = (SDataType*)realloc(ps, _newcapacity * sizeof(SDataType));
if (_new_a == NULL)
{
perror("StackPush()::realloc()");
exit(-1);
}
ps->_a = _new_a;
ps->_capacity = _newcapacity;
}
ps->_a[ps->_top++] = data;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
ps->_top--;
}
// 计算栈内有效个数
void StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
// 获取栈顶元素
void StackTop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
return ps->_a[ps->_top - 1];
}
// 判空
void StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0;
}
