数据结构之栈:使用数组和vector实现栈

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
611
文章
12
评论
2018年3月24日21:18:55 评论

栈是一种“先进后出”的数据结构,最先进入栈的元素位于栈的底端,最后进入的位于顶端。

其主要的接口函数为:

  • pop(): 弹出顶端元素
  • size(): 返回栈容量
  • empty(): 判断栈是否为空
  • push(T data): 添加元素到栈顶
  • top(): 返回顶端元素

注意事项

对于栈的top()pop()方法,使用前应该通过empty()手动判断栈是否为空,确认栈中有元素再进行操作。

同样,对于有容量限制的栈来说,压栈时应该也先判断栈的容量是否已满,避免占空间溢出。

当数据类型T是指针时,栈对象析构时不会制动释放所有的数组对象,需要自己对元素的生存周期负责。

一、使用数组实现栈

类模板声明为:

使用时需要指定类型名和栈空间大小:

1.1 构造和析构函数

1.2 压栈操作push()

压栈时注意不要数组越界:

1.3 出栈操作pop()

有些时候pop只用于出栈,并不用返回被出栈的元素,使用前应当先判断栈是否为空。

1.4 返回栈顶元素top

1.5 返回栈长度size(),判断栈是否为空empty()

二、使用vector实现栈

使用动态数组vector创建栈的好处在于能栈自动扩容和缩小,无需手动指定大小,插入元素时会自动扩容。

2.1 stack.h

2.2 stack.cpp

马谦马谦马谦
  • 本文由 发表于 2018年3月24日21:18:55
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/create-stack-with-array-and-vector.html
二叉树的后序遍历 数据结构和算法

二叉树的后序遍历

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

二叉树的中序遍历

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

发表评论

匿名网友 填写信息

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