栈详解

栈

栈的概念及结构

栈：一种特殊的线性表(数据是挨着储存,是连续的)，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

注意栈顶不能叫做头,栈底不能叫做尾

栈的实现

栈分为两种
数组栈:数组通常让首元素的空间为栈底,末尾为栈顶(因为栈的规则是后进先出,数组让末尾为栈顶的尾删效率更高)

链式栈:
双向链表实现的话栈顶可以是头节点或者尾借点,用头节点当栈顶就是头插或者头删,尾节点当栈顶就是尾插尾删
单链表实现的话通常用头节点当栈顶,尾节点当栈底(因为单链表头插头删的时间复杂度低,而尾插尾删需要遍历一遍链表,时间复杂度高)

数组栈和链式栈相比,数组栈相对来说更好一点,因为数组栈简单快捷,虽然数组栈有时需要扩容,但是这种情况相对来说比较少,因为一次扩容就是2倍左右(不是规定必须2倍,只是2倍相对来说更合理)
对于两个链式栈相比,单链表会更合适一点,因为双向链表实现起来更复杂一点

数组栈的实现

typedef struct stack
{int* a;int top;//栈顶int capacity;空间
}ST;

数组栈功能的实现

栈的初始化void STInit(ST* pst)

初始化的时对于指针a和capacity，我们很容易就会想到a=NULL，capacity=0

而对于top的初始化就需要注意

初始化情况一

如果top为数组的下标，当top初始化为0时就会出现歧义
当数组为空时，top=0
当数组中有一个元素时，top也为0
为了避免这种情况，我们将top初始化成-1

初始化情况二

我们也可以认为top代表数据个数，或者理解成指向栈顶元素的下一个位置
这样top就可以初始化成0

代码

void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0//或者pst->top = -1;
}

后面的代码我们讨论top初始化为0的情况

栈的插入void STPush(ST* pst, STDataType x)

栈的插入和之前我写的顺序表还有链表方式都差不多，有疑惑的可以去看看我之前写的文章

代码

void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}

栈的删除void STPop(ST* pst)

栈的删除要注意不能让top=0，因为top=0后就代表栈没有元素可以删除，所以要断言

代码

void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}

栈获取数据STDataType STTop(ST* pst)

因为top初始化为0，所以top为栈顶元素的下一个的下标

代码

STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}

判断栈是否为空bool STEmpty(ST* pst)

bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

求栈的元素个数int STSize(ST* pst)

int STSize(ST* pst)
{return pst->top;
}

栈的销毁void STDestory(ST* pst)

void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}

栈的打印方式

由于栈遵循后进先出,在访问栈的元素时,我们需要做到访问一个栈的元素就删除一个栈的元素,当栈访问完一遍后,栈的元素就全没了,也就是栈为空

int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}printf("\n");return 0;
}

栈溢出问题

栈有两种
数据结构的栈:存储数据

操作系统的栈:内存区域的划分(malloc,realloc…)

栈溢出中的栈是指操作系统的栈,发生的情况一般为递归出现返回条件错误,导致一直调用函数建立函数栈帧