数据结构之栈：使用数组和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