栈是一种 「先进后出」 的数据结构，最先进入栈的元素位于栈的底端，最后进入的位于顶端。
其主要的接口函数为：
pop(): 弹出顶端元素size(): 返回栈容量empty(): 判断栈是否为空push(T data): 添加元素到栈顶top(): 返回顶端元素
注意事项
对于栈的
top()和pop()方法，使用前应该通过empty()手动判断栈是否为空，确认栈中有元素再进行操作。同样，对于有容量限制的栈来说，压栈时应该也先判断栈的容量是否已满，避免占空间溢出。
当数据类型
T是指针时，栈对象析构时不会制动释放所有的数组对象，需要自己对元素的生存周期负责。
一、使用数组实现栈
类模板声明为：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#pragma once #define uint unsigned int template <typename T, uint N> class CArrStack { public: CArrStack(); ~CArrStack(); void push(T t); T pop(); T& top() const; uint size() const; bool empty() const; private: T data[N]; uint cur; }; |
使用时需要指定类型名和栈空间大小：
|
1 2 |
// 声明一个容量为 100 的元素类型为 int 的栈 CArrStack<int, 100> s; |
1.1 构造和析构函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
template<typename T, uint N> inline CArrStack<T, N>::CArrStack() { memset(data, 0, N * sizeof(T)); cur = 0; } template<typename T, uint N> inline CArrStack<T, N>::~CArrStack() { memset(data, 0, N * sizeof(T)); cur = 0; } |
1.2 压栈操作 push()
压栈时注意不要数组越界：
|
1 2 3 4 5 6 |
template<typename T, uint N> inline void CArrStack<T, N>::push(T t) { if (cur == N) return; data[cur++] = t; } |
1.3 出栈操作 pop()
有些时候 pop 只用于出栈，并不用返回被出栈的元素，使用前应当先判断栈是否为空。
|
1 2 3 4 5 |
template<typename T, uint N> inline T CArrStack<T, N>::pop() { return data[--cur]; } |
1.4 返回栈顶元素 top
|
1 2 3 4 5 |
template<typename T, uint N> inline T& CArrStack<T, N>::top() const { return data[cur - 1]; } |
1.5 返回栈长度 size()，判断栈是否为空 empty()
|
1 2 3 4 5 6 7 8 9 10 11 |
template<typename T, uint N> inline uint CArrStack<T, N>::size() const { return cur; } template<typename T, uint N> inline bool CArrStack<T, N>::empty() const { return cur == 0; } |
二、使用 vector 实现栈
使用动态数组 vector 创建栈的好处在于能栈自动扩容和缩小，无需手动指定大小，插入元素时会自动扩容。
2.1 stack.h
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <vector> #include <assert.h> using namespace std; typedef unsigned int uint; template <typename T> class CStack { public: CStack(); ~CStack(); uint size() const; bool empty() const; void push(const T t); T pop(); T top() const; private: vector<T> data; }; |
2.2 stack.cpp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
template <typename T> CStack<T>::CStack() { } template <typename T> CStack<T>::~CStack() { } template<typename T> inline uint CStack<T>::size() const { return data.size(); } template<typename T> inline bool CStack<T>::empty() const { return data.size() == 0; } template<typename T> inline void CStack<T>::push(const T t) { data.push_back(t); } template<typename T> inline T CStack<T>::pop() { typename vector<T>::iterator it = data.end() - 1; T tmp = *it; data.pop_back(); return tmp; } template<typename T> inline T CStack<T>::top()const { return data[data.size() - 1]; } |