链栈
栈存储结构
栈和链表的区别
同顺序表和链表一样,栈也是用来存储逻辑关系为 "一对一" 数据的线性存储结构
从图 1 我们看到,栈存储结构与之前所学的线性存储结构有所差异,这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求:
1.栈只能从表的一端存取数据,另一端是封闭的;
2.在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。
拿图 1 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。
栈的定义
栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。
通常,栈的开口端被称为栈顶;相应地,封口端被称为栈底。因此,栈顶元素指的就是距离栈顶最近的元素,拿图 2 来说,栈顶元素为元素 4;同理,栈底元素指的是位于栈最底部的元素,图 2 中的栈底元素为元素 1。
进栈和出栈
基于栈结构的特点,通常只会对栈执行以下两种操作:
- 向栈中添加元素,此过程被称为"进栈"(入栈或压栈);
- 从栈中提取出指定元素,此过程被称为"出栈"(或弹栈);
链栈
链表的头部作为栈顶,意味着:
- 在实现数据"入栈"操作时,需要将数据从链表的头部插入;
- 在实现数据"出栈"操作时,需要删除链表头部的首元节点;
链接表示栈基本运算的实现
算法 创建空栈
PLinkStack createEmptyStack_link(void)
算法 判断栈是否为空栈
int isEmptyStack_link( PLinkStack plstack )
算法进栈
void push_link( PLinkStack plstack, DataType x )
算法 出栈
void pop_link( PLinkStack plstack )
算法 取栈顶元素
DataType top_link( PLinkStack plstack )
链栈结构体
typedef char DataType;
struct Node
{
DataType data;
Node* next;
};
typedef Node* LinkStack;
创建空链栈
PLinkStack createEmptyStack(){
PLinkStack plstack= (PLinkStack)malloc(sizeof(Node));
plstack->next=NULL;
return plstack;
}
判断栈是否为空栈
int isEmptyStack_link( PLinkStack plstack ){
return plstack->next==NULL;
}
进栈:采用头插法
例如,将元素 1、2、3、4 依次入栈,等价于将各元素采用头插法依次添加到链表中,每个数据元素的添加过程如图 2 所示:
void push_link( PLinkStack& plstack, DataType x ){
PLinkStack q = (PLinkStack)malloc(sizeof(Node));
q->data=x;
q->next=plstack->next;
plstack->next=q;
}
出栈
例如,图 2e) 所示的链栈中,若要将元素 3 出栈,根据"先进后出"的原则,要先将元素 4 出栈,也就是从链表中摘除,然后元素 3 才能出栈,整个操作过程如图 3 所示:
void pop_link( PLinkStack plstack ){
if (plstack->next==NULL)
{
cout<<"Empty"<<endl;
return;
}
plstack->next=plstack->next->next;
free(plstack->next);
}
取栈顶元素
DataType top_link( PLinkStack plstack ){
if (plstack->next==NULL)
{
cout<<"Empty"<<endl;
return -1;//空栈
}
return plstack->next->data;
}
相关文章
- Docker高级篇:Redis集群实战!从4主4从缩容到3主3从,该怎么处理?
- Redis 单线程模型 精讲
- Redis6.0使用了多线程还能保证线程安全么?-Redis6.0 多线程精讲
- Redis 搞懂缓存击穿、缓存穿透、缓存雪崩 产生原因及产线常用的解决方案
- 这样讲Redis哨兵机制Sentinel的工作原理,或许你真的能听懂~
- 这样讲Redis Cluster的工作原理,或许你真的能听懂~
- 实战:常见的延时队列解决方案及代码实现,真的很全:MQ、Redis、JDK队列、Netty时间轮~
- 这样讲Redis 主从复制的工作原理,或许你真的能听懂~
- 为什么有的人学完Netty 都还不知道BIO|NIO|AIO 的区别?
- 10分钟快速入门Netty 比写NIO爽百倍
- 熬夜手绘netty线程模型图 如果还不懂的话,那我...
- Netty 是如何解决拆包和 粘包问题 ?最后一种方案最香
- Netty 如何通过心跳检测机制实现空闲自动断开
- .NET Core如何通过认证机制访问Kafka?
- .net 温故知新:【10】.NET ORM框架EFCore使用入门之CodeFirs、DBFirst
- 一次 Redis 事务使用不当引发的生产事故
- 安卓项目五子棋代码详解(三)
- 安卓项目五子棋代码详解(二)
- 安卓项目五子棋代码详解(一)
- 【深入浅出Seata原理及实战】「入门基础专题」探索Seata服务的AT模式下的分布式开发实战指南(2)