栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
"栈"的常见接口实现
- InitST:初始化栈
- STPush:入栈
- STPop:出栈
- STEmpty:判空(判断是否为空栈)
- PrintSTTop:打印栈顶元素
- STTop:返回栈顶元素(返回值类型:stacktype)
一、顺序栈
"顺序栈"的类型定义
如果友友们学过顺序表,这种类型可以随便拿捏.😄😄
代码:
typedef struct stack { stacktype* data;//一个指向连续内存空间的指针 int top;//记录栈顶元素的下标 int capacaity; }ST;
1.1 初始化栈
top指针:
由于数组的下标是从0开始,所以我们初始化"栈"时,可以将top指针(栈顶指针)初始化为-1,这样即可代表"栈"中无数据.
capacaity :
同顺序表一样,我们可以设置初始最大容量,后续不够可以扩容.
void InitST(ST* ps) { assert(ps); ps->top = -1;//此时栈中无数据 ps->capacaity = 4;//设置初始最大容量 ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype)); }
此处初始化后:
1.2 入栈(压栈,向"栈"中插入数据)
学到这里(顺序表和链表),对于"栈"的压栈操作很简单.
- 由于是顺序表实现栈,所以在进行插入操作之前要先进行"判满"操作,如果栈满了,要进行扩容.
- top是指向栈顶下标,需要将其往后移动一位,使其指向待插入位置.
- 将新元素插入.此时刚好top为新的栈顶的下标.
图解:
代码:
void STPush(ST* ps, stacktype x)//压栈 { assert(ps); if (ps->top+1 == ps->capacaity)//检查"栈"满 { ps->capacaity *= 2;//扩容 stacktype* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype)); if(tmp == NULL) { printf("增容失败\n"); } ps->data = tmp; } //将"栈顶指针"指向待插入位置 ps->top++; //将元素压栈 ps->data[ps->top] = x; }
1.3 “出栈”,删除"栈"中的数据
步骤:
- 删除数据时,需要判断"栈"是否为空.
- 将top向前(下)移动一位,即表示有效数据位减1.
代码:
void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; }
1.4 判空(判断"栈"是否为空)
当栈为空时,top为初始状态-1.
bool STEmpty(ST* ps)//判断是否为空栈,是空返回真 { assert(ps); if (ps->top == -1) { return true; } return false; }
1.5 打印"栈顶"元素
void PrintSTTop(ST* ps) { assert(ps); printf("%d", ps->data[ps->top]); }
1.6 返回"栈顶"元素
stacktype STTop(ST* ps)//返回栈顶元素 { assert(ps); return ps->data[ps->top]; }
1.7 "栈"的销毁
栈的销毁操作,因为malloc开辟出来的是连续的空间,所以只需要释放一次即可.
void STDestory(ST* ps) { assert(ps); free(ps->data); ps->data = NULL; ps->top = -1; ps->capacaity = 0; }
二、链栈
"链栈"的类型定义
typedef int stacktype; // 链栈的类型 typedef struct SLStackNode { stacktype data; struct SLStackNode* next; }SLStackNode;
其实我们不难发现,"链栈"的类型与单链表很相似,通过对"栈"的基本知识了解,"栈"只在一端进行"插入"和"删除"操作,为了用单链表实现这一要求.
同时为了提高效率:
| 链表 | 分析 |
| 尾插，尾删 | 效率低，因为需要找尾巴 |
| 头插，头插 | 效率高,只需要改变头指针的指向 |
综上:我们利用不带头单链表的"头插(入栈)和头删(出栈)"来完成栈的各项基本操作.并且"栈"不需要进行随机访问其中的元素,只能从栈顶访问,链表是可以完成的.
2.1 初始化"链栈"
对于链表实现的栈,如果不带头结点:
我们不需要特意去写一个初始化函数.只需要创建一个栈顶指针,将其初始化指向NULL即可.(下面的代码是采用这种形式)
//创建一个栈顶指针,并完成初始化 SLStackNode* SLStack = NULL;
如果是带头结点的单链表:
我们可以定义一个初始化函数,申请一个头结点(头结点的数据域不存数据),将头结点返回.
//stack.c SLStackNode* InitStack() { SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode)); if (newnode == NULL) { perror("newnode malloc fail"); } return newnode; } //test.c SLStackNode* SLStack = InitStack();
2.2 入栈(压栈,向"栈"中插入数据)
步骤:(与单链表的头插类似)
- 创建一个新节点.
- 将新节点的next指针指向原"栈"的顶点
- 更新栈顶指针(将栈顶指针指向新节点)
图解:
代码:
//入栈 void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插 { assert(pps); //获取新的结点 SLStackNode* newnode = BuyNode(x); newnode->next = *pps;//将新节点的next指针指向原"栈"的顶点 *pps = newnode;//更新栈顶 }
2.3 “出栈”,删除"栈"中的数据
步骤:(与链表的头删操作类似)
- 判空,防止空链栈的删除操作
- 记录原栈顶元素的地址.
- 更新栈顶.(将栈顶指针指向原栈顶的下一个结点↓).
- 释放原栈顶空间
图解:
void STPop(SLStackNode** pps)//出栈 { assert(pps);//二级指针不可能为空,如果为空就一定是传错了 assert(*pps);//防止空链栈的删除操作 SLStackNode* head = *pps;//记录栈顶元素的地址 *pps = (*pps)->next;//更新栈顶,即原来栈顶的下一个结点 free(head);//释放原栈顶空间 }
