顺序栈

【概述】

顺序栈是采取顺序方式存储的栈，利用一组地址连续的存储单元自栈底到栈顶存放数据元素，并通过栈指针来指示当前栈顶元素位置

对于存储空间的分配，若采用静态分配方式，一经分配不可修改，若采用动态分配方式，分配后在 $O(n)$ 的时间复杂度内可以更改

顺序栈的实现类如下：

#define N 50 + 5 //申请空间个数
template <typename T> 
class SeqStack {
  public:
    SeqStack();           //初始化栈
    int getLen();         //求栈长
    bool empty();         //判空
    bool full();          //判满
    bool pop(T &elem);    //出栈
    bool push(T elem);    //入栈
    bool getTop(T &elem); //取栈顶
    void print();         //输出
  private:
    T data[N];            //栈空间
    int top;              //栈指针
};

【初始化】

初始化时，栈为空栈，栈中无元素，此时栈指针 top 一般设为 -1，有时也可令 top=0，以表明 top 指向栈顶元素的下一存储单元

template <typename T> 
SeqStack<T>::SeqStack() { //初始化栈
    top = -1;
}

【求栈长】

由于栈指针指示了栈顶元素位置，因此栈的长度即为栈指针的大小，需要注意的是，当栈指针初始化为 -1 时，最终的栈长要 +1

template <typename T> 
int SeqStack<T>::getLen() { //求栈长
    return top + 1;
}

【判空】

判空时，只需判断栈指针 top 是否为初始值即可

template <typename T> 
bool SeqStack<T>::empty() { //判空
    if (top == -1)
        return true;
    return false;
}

【判满】

判满时，只需要判断栈指针 top 是否达到最大栈空间即可

template <typename T> 
bool SeqStack<T>::full() { //判满
    if (top == N - 1)
        return true;
    return false;
}

【出栈】

在出栈时，要进行下溢判断，即在栈已空的情况下，再进行出栈操作，会发生溢出

template <typename T> 
bool SeqStack<T>::pop(T &elem) { //出栈
    if (empty())                 //下溢判断
        return false;
    elem = data[top--];
    return true;
}

【入栈】

由于顺序栈的存储空间有限，因此在入栈时，要进行上溢判断，即在栈已满的情况下，再进行入栈操作时，会发生溢出

template <typename T> 
bool SeqStack<T>::push(T elem) { //入栈
    if (full())                  //上溢判断
        return false;
    data[++top] = elem;
    return true;
}

【取栈顶】

在取栈顶时，要进行下溢判断，以确保不会在栈已空的情况下取到元素

template <typename T> 
bool SeqStack<T>::getTop(T &elem) { //取栈顶
    if (empty())                    //下溢判断
        return false;
    elem = data[top];
    return true;
}

【输出】

在输出时，从栈顶开始，将栈中所有元素依次出栈，进行输出即可

template <typename T> 
void SeqStack<T>::print() { //输出
    int elem;
    while (!empty()) { //将所有元素依次出栈进行输出
        pop(elem);
        cout << elem << " ";
    }
    cout << endl;
}