顺序栈的实现和使用数组实现原理一样，都是预先申请一段连续的地址块作为数据域，通过栈顶下标或指针移动完成压栈、出栈等操作。不同的是，使用指针的顺序栈支持栈满时扩容操作，原理更倾向于 vector 的实现。
顺序栈初始化时申请一块固定大小内存空间保存数据，栈顶指针在内存区域来回移动：
要注意的是，初始时栈为空，bottom 和 cursor 指针都是指向同一个区域，每插入一个元素，给 cursor 所在的元素赋值，然后 cursor 后移一位。
不难发现，cursor 指针所指向的区域是空的，它所在位置的前一个元素才是真正的栈顶元素，所以每次取栈顶元素或者执行出栈操作时，要先把指针前移一位，然后再弹出 cursor 所指向的元素。
所以根据这个原则，当栈满的时候，cursor 实际所指向的地址已经越界，它位于最后一个元素地址空间的下一个：
此时虽然指针已经非法，但是实际上并不会取到这个地址上的值，所以也不会导致内存错误。这也要求在处理压栈、出栈操作时要小心，不要取向非法内存地址上的值。
对于这个问题也有一个解决的方法，就是在申请内存空间时多申请一个地址，最后多的一个数据块出来存放栈满后的 cursor，相对来说这个方法更为安全保险。
类定义
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#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; }; |
类实现
|
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
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; } |