【数据结构】-- 栈

栈

引入：

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的元素遵循先进后出的原则，先入栈的元素总是先后出栈。 压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。 出栈：栈的删除操作叫做出栈。 出数据也在栈顶 。

注意：入栈顺序是DCBA，出栈顺序不一定是ABCD，可以边入边出

所以，入栈顺序是DCBA ，出栈顺序有很多种。

栈的实现：

数组，单向链表，双向链表都能够实现栈：

数组：

单链表：

用单链表实现栈有一个问题，单链表不能回头，如图这么设计，在压栈之后，不方便出栈。

所以我们可以以开头作为栈顶，然后对链表头插来实现栈，出栈的时候使用头删。

双向链表：

 双向链表可以通过前一个元素直接访问上一个元素，这使得在双向链表中实现栈的出栈功能更加高效和方便。因为双向链表可以从尾部直接访问到最后一个元素，从而实现了栈的后进先出（LIFO）特性。

由于CPU的高速缓存，在这里我们使用数组来实现栈 。

头文件：

#define _CRT_SECURE_NO_WARNINGS 1#pragma once#include #include #include #include typedef int STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;void STInit(ST* pst);//初始化void STDestory(ST* pst);//销毁void STPush(ST* pst, STDataType x);//压栈void STPop(ST* pst);//出栈STDataType STTop(ST* pst);//获取栈顶的元素bool STEmpty(ST* pst);//判断栈是否为空int STSize(ST* pst);//判断栈里面有多少中数据(数据个数)

实现文件：

初始化栈的时候可以开辟空间也可以后面再开辟，在初始化top的时候有两种写法。

把top初始化为0：

这时，top指向栈顶元素的下一位

把top初始化-1：

这时，top指向栈顶元素。

不必过分在意top,无论top指向哪里，top只是一个数字，数据依然从栈顶开始存储。只不过，第一种方法有了第一个数据的时候top的值是1，第二种方法有了第一个数据时top的值为0。

在这里我们选择第一种写法。

#define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"//初始化void STInit(ST* pst){assert(pst);pst->a = NULL;//top指向栈顶数据的下一个位置pst->capacity = 0;pst->top = 0;//top指向栈顶数据//pst->top = -1;}//销毁void STDestory(ST* pst){assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;}//压栈void STPush(ST* pst, STDataType x){assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;}//出栈void STPop(ST* pst){assert(pst);pst->top--;}//获取栈顶的元素STDataType STTop(ST* pst){assert(pst);return pst->a[pst->top - 1];}//判断栈是否为空bool STEmpty(ST* pst){assert(pst);return pst->top == 0;}//判断栈里面有多少中数据(数据个数)int STSize(ST* pst){assert(pst);return pst->top;}

 测试文件：

#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"int main(){ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);printf("%d \n", STTop(&s));//列出栈中元素while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}return 0;}