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

马谦马谦马谦 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

本文共执行41次查询,耗时0.281秒!
马谦马谦马谦

发表评论

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