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

其主要的接口函数为：

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

使用注意事项

对于栈的top()和pop()方法，使用前应该通过empty()手动判断栈是否为空，确认栈中有元素再进行操作。同样，对于有容量限制的栈来说，压栈时应该也先判断栈的容量是否已满，避免占空间溢出。

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

一、使用数组实现栈

类模板声明为：

#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;
};

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

// 声明一个容量为100的元素类型为int的栈
CArrStack<int, 100> s; 

1.1 构造和析构函数

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()

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

template<typename T, uint N>
inline void CArrStack<T, N>::push(T t)
{
    if (cur == N) return;
    data[cur++] = t;
}

1.3 出栈操作pop()

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

template<typename T, uint N>
inline T CArrStack<T, N>::pop()
{
    return data[--cur];
}

1.4 返回栈顶元素top

template<typename T, uint N>
inline T& CArrStack<T, N>::top() const
{
    return data[cur - 1];
}

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

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

#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

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];
}