数据结构之栈(三):顺序栈实现

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
611
文章
12
评论
2018年3月25日12:14:53 评论

顺序栈的实现和使用数组实现原理一样,都是预先申请一段连续的地址块作为数据域,通过栈顶下标或指针移动完成压栈、出栈等操作。不同的是,使用指针的顺序栈支持栈满时扩容操作,原理更倾向于vector的实现。

顺序栈初始化时申请一块固定大小内存空间保存数据,栈顶指针在内存区域来回移动:

数据结构之栈(三):顺序栈实现

要注意的是,初始时栈为空,bottomcursor指针都是指向同一个区域,每插入一个元素,给cursor所在的元素赋值,然后cursor后移一位。

数据结构之栈(三):顺序栈实现

不难发现,cursor指针所指向的区域是空的,它所在位置的前一个元素才是真正的栈顶元素,所以每次取栈顶元素或者执行出栈操作时,要先把指针前移一位,然后再弹出cursor所指向的元素。

所以根据这个原则,当栈满的时候,cursor实际所指向的地址已经越界,它位于最后一个元素地址空间的下一个:

数据结构之栈(三):顺序栈实现

此时虽然指针已经非法,但是实际上并不会取到这个地址上的值,所以也不会导致内存错误。这也要求在处理压栈、出栈操作时要小心,不要取向非法内存地址上的值。

对于这个问题也有一个解决的方法,就是在申请内存空间时多申请一个地址,最后多的一个数据块出来存放栈满后的cursor,相对来说这个方法更为安全保险。

类定义

类实现

历史上的今天
三月
25
马谦马谦马谦
  • 本文由 发表于 2018年3月25日12:14:53
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/the-sequence-stack.html
二叉树的后序遍历 数据结构和算法

二叉树的后序遍历

一、后序遍历 后序遍历逻辑:优先访问左、右子节点,然后访问当前节点。 一个后序遍历的示例,它的后序遍历结果为: 二、非递归实现 后序遍历的非递归实现比前序和中序的非递归实现要复杂很多,因为每个节点都可...
二叉树的中序遍历 数据结构和算法

二叉树的中序遍历

一、中序遍历 中序遍历过程:先访问左子节点,然后访问当前节点,最后访问右子节点。 以下试一次中序遍历过程: 二、非递归实现 非递归方式遍历依赖栈来实现,因为要先访问子节点,然后访问父节点,因此必须要有...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: