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

马谦马谦马谦 2018年3月25日12:14:53 发表评论

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

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

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

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

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

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

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

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

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

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

类定义

类实现

本文共执行48次查询,耗时0.770秒!
马谦马谦马谦

发表评论

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