数据结构：第十八节-顺序栈

顺序栈是一种使用数组实现的栈。它的特点是存储在一段连续的内存空间中，并且栈顶元素位于数组的末尾。顺序栈通常会有一个指针来指示栈顶元素的位置，称为栈顶指针（top），栈底指针记为base。若栈空时，栈顶指针通常指向特殊的位置（-1），或者说base==top，表示没有元素存储在栈中。当向栈中压入元素时（push），栈顶指针会向后移动一个位置（top++），并将元素存储在该位置上。当从栈中弹出元素时（pop），栈顶指针会向前移动一个位置（top--），指向上一个压入的元素。当栈中元素数量达到数组的最大容量时，就认为栈满（top-base==stacksize）。此时通常需要进行扩容操作或者报错。

顺序栈使用数组作为底层数据结构，实现简单直接，操作效率高。但是由于初始化分配了固定的空间，可能会造成空间浪费或者溢出。当我们向栈中压入元素时，如果容器已满，会导致数组越界，从而产生溢出错误，此时发生了上溢。要避免顺序栈的溢出，可以在进行压栈操作之前，先检查栈是否已满，如果已满则不进行压栈操作，或者在进行压栈操作时动态扩展栈的容量。除此之外，当我们从栈中弹出元素时，如果容器已空，则无法再弹出元素，此时发生了下溢，因此我们在弹栈之前要做判空。

我们先看顺序栈是如何定义的？

const int MAX_SIZE = 100; // 定义顺序栈的最大容量


// 定义顺序栈的结构体
struct SeqStack {
    int data[MAX_SIZE]; // 用数组存储栈元素
    int top; // 栈顶指针，指向栈顶元素的位置
    }；

以上我们定义了一个包含数组和栈顶指针的结构体，用于表示顺序栈。

下面我们来看顺序栈的基本操作：

1.InitStack(&S)：初始化一个空栈S。

SeqStack() : top(-1) {} // 初始时栈顶指针为-1，表示栈为空

我们先创建了一个具有固定大小的数组作为顺序栈的存储空间，然后初始化栈顶指针为-1，表示栈为空。我们就完成了顺序栈的初始化操作，可以进行顺序栈的其他操作了。

2.IsEmpty(S)：判断栈S是否为空，若为空则返回真，否则返回假。

bool isEmpty(int top) {
    return top == -1; // 如果栈顶指针等于-1，则栈为空
}

3.stackLength(top)：求顺序栈的长度。

int stackLength(int top) {
    return top + 1; // 栈的长度等于栈顶指针加上1
}

假设栈的初始值为-1，栈的长度即为栈顶指针加上1。如果栈顶指针为-1，则栈为空，长度为0，如果栈不为空，栈的长度等于栈顶指针加上1。

4.isFull(&S)：检查顺序栈是否已满。

bool isFull(const SeqStack& stack) {
    // 如果栈顶指针等于数组的最大索引值，则栈满
    return stack.top == MAX_SIZE - 1;
}

顺序栈的满条件通常是栈顶指针达到了数组的最大索引值。

5.Push(&S, x)：将元素x压入栈S。

void push(SeqStack& stack, int value) {
    // 检查栈是否已满
    if (isFull(stack)) {
        cout << "栈已满！无法添加元素！" << endl;
        return;
    }
    // 将元素放入栈顶位置
    stack.data[++stack.top] = value;
}

我们首先检查栈是否已满，如果已满，则输出提示信息并退出函数，如果未满，则将元素放入栈顶位置，然后将栈顶指针加一。最后一行代码合并了两个操作，先将栈顶指针递增（++stack.top)，然后将元素存储到递增后的栈顶指针所指向的位置(stack.data[stack.top] = value)，从而实现了将元素压入栈的操作。

6.Pop(&S, &x)：从栈S中弹出栈顶元素，并将其存储到变量x中。

int pop(SeqStack& stack) {
    // 检查栈是否为空
    if (isEmpty(stack)) {
        cout << "栈已空！无法删除元素！" << endl;
        return -1; 
    }
    // 取出栈顶元素，并将栈顶指针减一
    int e = stack.data[stack.top--];
    // 返回被移除的栈顶元素
    return e;
}

首先检查栈是否为空，然后取出栈顶元素并将栈顶指针减一，最后返回被移除的栈顶元素。

7.ClearStack(&S)：清空栈S，使其成为一个空栈。

void clearStack(SeqStack& stack) {
    stack.top = -1; // 将栈顶指针设置为初始值
}

清空顺序栈的算法可以通过将栈顶指针重置为初始值来实现，我们通常设置初始值为-1。

8.DestroyStack(&S)：销毁栈S，释放内存空间。

void destroyStack(SeqStack& stack) {
    // 释放栈中所有元素所占用的内存空间
    for (int i = 0; i <= stack.top; ++i) {
        delete stack.data[i];
    }
    // 将栈底指针设置为初始值
    stack.top = -1;
}

我们要销毁顺序栈，需要释放栈中所有元素占用的内存空间，并将栈底指针设置为初始值。

以上就是顺序栈的基本操作，感谢观看！欢迎各位的点赞与关注！您的点赞和关注是我学习更新的动力！如有问题，可下方留言！