数据结构之栈（三）：顺序栈实现

马谦马谦马谦

615
文章

17
评论

2018年3月25日12:14:53数据结构和算法评论1,010字数 572阅读1分54秒阅读模式

顺序栈的实现和使用数组实现原理一样，都是预先申请一段连续的地址块作为数据域，通过栈顶下标或指针移动完成压栈、出栈等操作。不同的是，使用指针的顺序栈支持栈满时扩容操作，原理更倾向于vector的实现。

顺序栈初始化时申请一块固定大小内存空间保存数据，栈顶指针在内存区域来回移动：

要注意的是，初始时栈为空，bottom和cursor指针都是指向同一个区域，每插入一个元素，给cursor所在的元素赋值，然后cursor后移一位。

不难发现，cursor指针所指向的区域是空的，它所在位置的前一个元素才是真正的栈顶元素，所以每次取栈顶元素或者执行出栈操作时，要先把指针前移一位，然后再弹出cursor所指向的元素。

所以根据这个原则，当栈满的时候，cursor实际所指向的地址已经越界，它位于最后一个元素地址空间的下一个：

此时虽然指针已经非法，但是实际上并不会取到这个地址上的值，所以也不会导致内存错误。这也要求在处理压栈、出栈操作时要小心，不要取向非法内存地址上的值。

对于这个问题也有一个解决的方法，就是在申请内存空间时多申请一个地址，最后多的一个数据块出来存放栈满后的cursor，相对来说这个方法更为安全保险。

类定义

#ifndef _UNSIGNED_INT_
#define uint unsigned int
#endif // !_UNSIGNED_INT_

template <typename T, unsigned N>
class CSeqStack {
public:
    CSeqStack();
    ~CSeqStack();
    void push(const T& data);
    T pop();
    T& top() const;
    uint size() const;
    bool empty() const;
private:
    T * bottom;
    T* cursor;
    uint cap;
};

#ifndef _UNSIGNED_INT_

#define uint unsigned int

#endif // !_UNSIGNED_INT_

template <typename T, unsigned N>

class CSeqStack {

public:

CSeqStack();

~CSeqStack();

void push(const T& data);

T pop();

T& top() const;

uint size() const;

bool empty() const;

private:

T * bottom;

T* cursor;

uint cap;

};

类实现

template<typename T, unsigned N>
inline CSeqStack<T, N>::CSeqStack()
{
    bottom = new T[N] + 1;
    // bottom = new T[N]; 
    cursor = bottom;
    cap = N;
}

template<typename T, unsigned N>
inline CSeqStack<T, N>::~CSeqStack()
{
    delete[]bottom;
}

template<typename T, unsigned N>
inline void CSeqStack<T, N>::push(const T & data)
{
    // 容量不足了，重新申请
    if (cursor - bottom == cap) {
        uint newCap = cap + 1;
        // 根据当前容量的两倍扩容
        T* tmp = new T[newCap * 2 + 1]; // 多申请一个内存空间
        // T* tmp = new T[newCap * 2]; 

        // 拷贝内存
        memcpy(tmp, bottom, sizeof(T)*cap);
        // 对栈顶指针重新赋值
        cursor = tmp + (cursor - bottom);
        delete[]bottom;
        // 重新赋值栈底指针
        bottom = tmp;
        cap = newCap * 2;
    }
    *(cursor++) = data;
}

template<typename T, unsigned N>
inline T CSeqStack<T, N>::pop()
{
    // 栈顶元素时cursor指向的前一个元素
    T tmp = *(--cursor);
    return tmp;
}

template<typename T, unsigned N>
inline T & CSeqStack<T, N>::top() const
{
    // 栈顶元素时cursor指向的前一个元素
    return *(cursor - 1);
}

template<typename T, unsigned N>
inline uint CSeqStack<T, N>::size() const
{
    // 两个指向同一数组的指针相减得到两个元素间的距离
    return cursor - bottom;
}

template<typename T, unsigned N>
inline bool CSeqStack<T, N>::empty() const
{
    return cursor == bottom;
}