您现在的位置是:首页 >技术教程 >c语言实现栈(顺序栈,链栈)网站首页技术教程
c语言实现栈(顺序栈,链栈)
?个人主页:? :✨✨✨初阶牛✨✨✨
?推荐专栏: ???C语言进阶
?个人信条: ?知行合一
?本篇简介:>:讲解用c语言实现:“数据结构之"栈”,分别从"顺序栈"和"链栈"的接口讲解.
金句分享:
✨不是每一场雨后都有彩虹,但是晴天总是会到来!✨
前言
栈
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出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;//扩容
ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
if(tmp == NULL)
{
printf("增容失败
");
}
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);//释放原栈顶空间
}
2.4 判空(判断"栈"是否为空)
链栈(不带头版本的)的初始状态是栈顶指针指向NULL
.
bool STEmpty(SLStackNode* ps)//判断是否为空栈
{
if (ps == NULL)
{
return true;
}
else
return false;
}
2.5 打印"栈顶"元素
栈顶元素即,栈顶指针指向的结点的数据域
.
void PrintSTTop(SLStackNode* ps)//打印栈顶元素
{
assert(ps);
printf("%d ", ps->data);
}
2.6 返回"栈顶"元素
stacktype STTop(SLStackNode* ps)//返回栈顶元素
{
assert(ps);
return ps->data;
}
2.7 返回"链栈"的长度(有效数据的个数)
遍历这个栈即可求出栈的长度.(但其实一般情况下,栈是不允许遍历的,栈顶元素不出去,我们原则上不能访问栈顶下面的元素).
代码:
int LengthStack(SLStackNode* ps)
{
int count = 0;
if (ps == NULL)//如果栈顶指针指向NULL,表示栈中没有元素
{
return 0;
}
SLStackNode* tail = ps;//代替头指针遍历
while (ps)
{
count++;//如果该结点不为空,则有效数据个数+1
ps = ps->next;
}
return count;//返回有效数据的个数
}
2.8 "链栈"的销毁
与"链表"销毁类似.
void STDestory(SLStackNode* ps)//栈的销毁
{
SLStackNode* del = ps;
SLStackNode* next = ps;//用于记录下一个结点
while (next)
{
next = next->next;
free(del);
del = next;
}
//保持习惯置空
next == NULL;
del = NULL;
}
总结:
但是如果了解过寄存器的小伙伴,应该知道,如果数据在物理上是连续存储的,更加有利于数据的读取.
寄存器:
寄存器是CPU内部用来存放数据的一些小型存储区域,用来暂时存放参与运算的数据和运算结果。
因为cpu不是直接从硬盘读取数据的(嫌弃硬盘太慢了),而是通过寄存器(访问速度很快).
数据先被加载到缓存,此时如果数据在物理上是连续存储的,则在加载数据到缓存时,刚好将后面要读的数据也读走了,这样再读下一个数据时,就不需要再去硬盘读了.
?栗子:
综上,还是稍微建议使用顺序栈
有一点点优势.
希望这篇文章对大家有帮助。欢迎小伙伴们私信提意见和提问哦!
最后,小伙伴们的点赞就是给牛牛最大的支持,能不能给牛牛来一个一键三连呢?谢谢支持。
总代码
"顺序栈"总代码
声明区(stack.h)
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int stacktype;
typedef struct stack
{
stacktype* data;
int top;
int capacaity;
}ST;
void InitST(ST* ps);
void STPush(ST* ps, stacktype x);//压栈
void STPop(ST* ps);//出栈
void PrintSTTop(ST* ps);//打印栈顶元素
bool STEmpty(ST* ps);//判断是否为空栈
stacktype STTop(ST* ps);//返回栈顶元素
void STDestory(ST* ps);//栈的销毁
接口实现区( stack.c)
#include "stack.h"
//初始化栈
void InitST(ST* ps)
{
assert(ps);
ps->top = -1;
ps->capacaity = 4;
ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));
}
//压栈
void STPush(ST* ps, stacktype x)
{
assert(ps);
if (ps->top+1 == ps->capacaity)
{
ps->capacaity *= 2;
ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
if(tmp == NULL)
{
printf("增容失败
");
}
ps->data = tmp;
}
ps->top++;
ps->data[ps->top] = x;
}
//出栈
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
//打印栈顶元素
void PrintSTTop(ST* ps)
{
assert(ps);
printf("%d", ps->data[ps->top]);
}
//判断是否为空栈,是空返回真
bool STEmpty(ST* ps)
{
assert(ps);
if (ps->top == -1)//如果"栈"为空,则栈顶的下标为-1;
{
return true;
}
return false;
}
//返回栈顶元素
stacktype STTop(ST* ps)
{
assert(ps);
return ps->data[ps->top];//反追栈顶元素
}
//栈的销毁
void STDestory(ST* ps)
{
assert(ps);
free(ps->data);//释放栈空间
ps->data = NULL;
ps->top = -1;
ps->capacaity = 0;
}
测试区(test.c)
#include "stack.h"
void test1()
{
ST st1;
InitST(&st1);
STPush(&st1, 1);//压栈
STPush(&st1, 2);//压栈
STPush(&st1, 3);//压栈
STPush(&st1, 4);//压栈
int a=STTop(&st1);
printf("栈顶元素为%d
", a);
while (!STEmpty(&st1))
{
PrintSTTop(&st1);//打印栈顶元素
STPop(&st1);
}
STDestory(&st1);
}
int main()
{
test1();
return 0;
}
"链栈"总代码:
声明区(SLStack.h)
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int stacktype;
// 链栈的类型
typedef struct SLStackNode
{
stacktype data;
struct SLStackNode* next;
}SLStackNode;
//SLStackNode* InitStack();
void STPush(SLStackNode** pps, stacktype x);//压栈
void STPop(SLStackNode** pps);//出栈
void PrintSTTop(SLStackNode* ps);//打印栈顶元素
bool STEmpty(SLStackNode* ps);//判断是否为空栈
stacktype STTop(SLStackNode* ps);//返回栈顶元素
int LengthStack(SLStackNode* ps);//返回栈的长度
void STDestory(SLStackNode* ps);//栈的销毁
接口实现区(SLStack.c)
#include "SLStack.h"
//SLStackNode* InitStack()
//{
// SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
// if (newnode == NULL)
// {
// perror("newnode malloc fail");
// }
// return newnode;
//}
SLStackNode* BuyNode(stacktype x)//创建新结点
{
SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
assert(newnode);//防止申请结点失败
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//入栈
void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插
{
assert(pps);
//获取新的结点
SLStackNode* newnode = BuyNode(x);
newnode->next = *pps;
*pps = newnode;
}
void STPop(SLStackNode** pps)//出栈
{
assert(pps);//二级指针不可能为空,如果为空就一定是传错了
assert(*pps);//防止空链栈的删除操作
SLStackNode* head = *pps;//记录栈顶元素的地址
*pps = (*pps)->next;//将栈顶向下移动一位
free(head);//释放栈顶空间
}
void PrintSTTop(SLStackNode* ps)//打印栈顶元素
{
assert(ps);
printf("%d ", ps->data);
}
bool STEmpty(SLStackNode* ps)//判断是否为空栈
{
if (ps == NULL)
{
return true;
}
else
return false;
}
stacktype STTop(SLStackNode* ps)//返回栈顶元素
{
assert(ps);
return ps->data;
}
int LengthStack(SLStackNode* ps)
{
int count = 0;
if (ps == NULL)
{
return 0;
}
SLStackNode* tail = ps;
while (ps)
{
count++;
ps = ps->next;
}
return count;
}
void STDestory(SLStackNode* ps)//栈的销毁
{
SLStackNode* del = ps;
SLStackNode* next = ps;//用于记录下一个结点
while (next)
{
next = next->next;
free(del);
del = next;
}
//保持习惯置空
next == NULL;
del = NULL;
}
测试区(test.c)
#include "SLStack.h"
void test1()
{
SLStackNode* SLStack = NULL;
//SLStackNode* SLStack = InitStack();
STPush(&SLStack, 1);//压栈
STPush(&SLStack, 2);//压栈
STPush(&SLStack, 3);//压栈
STPush(&SLStack, 4);//压栈
STPush(&SLStack, 5);//压栈
STPush(&SLStack, -1);//压栈
STPush(&SLStack, -2);//压栈
int a = STTop(SLStack);
printf("栈顶元素为%d
", a);
int length = LengthStack(SLStack);
printf("链表的长度为:%d
", length);
while (!STEmpty(SLStack))
{
PrintSTTop(SLStack);//打印栈顶元素
STPop(&SLStack);
}
STDestory(SLStack);
}
int main()
{
test1();
return 0;
}