加载中

手写数据结构·线性表03:顺序栈

顺序栈(ArrayStack)

template<class T, int MAXN>
class ArrayStack {
    T data[MAXN];
    int topIndex;   // 栈顶元素下标;空栈为 -1
public:
    ArrayStack(): topIndex(-1) {}
    bool empty() const { return topIndex==-1; }
    bool full() const { return topIndex==MAXN-1; }
    int size() const { return topIndex+1; }

    bool push(const T& x){
        if(full()) return false;
        data[++topIndex]=x;
        return true;
    }

    bool pop(){
        if(empty()) return false;
        topIndex--;
        return true;
    }

    T& top(){
        if(empty()) throw underflow_error("ArrayStack::top on empty stack");
        return data[topIndex];
    }

    void clear(){ topIndex=-1; }
};

工程细节

  • topIndex 表示栈顶元素下标,空栈为 -1,元素数为 topIndex + 1;不要与“栈顶指针指向下一空位”的约定混用。
  • 入栈先递增下标,再写入元素;出栈只递减下标。空栈 pop() 和满栈 push() 返回 false。
  • 空栈读取 top() 抛出 underflow_error;clear() 将 topIndex 恢复为 -1。

跳转

下一个:普通顺序队列

上一个:动长数组

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/aa0cf01a/

版权声明:本文采用 CC BY-NC-SA 4.0 许可协议