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

栈是一种 「先进后出」 的数据结构，最先进入栈的元素位于栈的底端，最后进入的位于顶端。

其主要的接口函数为：

• 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