《数据结构》C++版：顺序栈的实现与操作

"3.2 栈的顺序存储结构" 栈是一种抽象的数据结构，它遵循“后进先出”（LIFO，Last In First Out）的原则。在计算机科学中，栈广泛应用于各种算法和程序设计中，如递归、表达式求解、内存管理等。顺序栈是栈的一种常见实现方式，它利用数组来存储栈元素。 顺序栈的基本思想是将栈中的元素顺序地存储在一个固定大小的数组中，并设置一个栈顶指针（top）来指示当前栈顶元素的位置。数组的某个端被设定为栈底，而另一端通常是栈顶。在栈为空时，top值为-1；当栈满时，top值等于数组的最大索引减1，即MAX_SIZE-1，其中MAX_SIZE通常是一个预定义的常量，表示数组的容量。 在顺序栈的操作中，进栈（Push）操作是在栈顶指针所指向的位置存入新元素，并将top加1。例如，如果初始时top为0，当元素a1入栈后，top变为1；接着元素a2和a3依次入栈，top会分别变为1和2。而出栈（Pop）操作则是取出栈顶元素，并将top减1。当尝试出栈时，如果top为-1，表示栈为空，此时抛出“溢出”异常；同样，当尝试进栈且top等于MAX_SIZE-1时，表示栈已满，也会抛出“溢出”异常。 以下是一个C++模板类的实现，用于表示顺序栈： ```cpp const int MAX_SIZE = 100; template <class DataType> class seqStack { public: seqStack(); // 构造函数 ~seqStack(); // 析构函数 void Push(DataType x); // 入栈操作 DataType Pop(); // 出栈操作 DataType GetTop(); // 获取栈顶元素但不删除 bool Empty(); // 检查栈是否为空 private: DataType data[MAX_SIZE]; // 存储栈元素的数组 int top; // 栈顶指针 }; ``` 顺序栈的入栈操作`Push()`实现如下： ```cpp template <class DataType> void seqStack<DataType>::Push(DataType x) { if (top == MAX_SIZE - 1) throw "溢出"; top++; data[top] = x; } ``` 出栈操作`Pop()`实现如下： ```cpp template <class DataType> DataType seqStack<DataType>::Pop() { if (top == -1) throw "溢出"; DataType x = data[top--]; return x; } ``` 除了单一顺序栈外，还可以实现共享栈，即将一个数组用于存储两个独立的栈。这种情况下，一个栈的栈底位于数组的开始，另一个栈的栈底位于数组的末尾，两个栈各自向数组的中心扩展。这种方法可以有效地节省空间，尤其在内存资源有限的情况下。 在实际应用中，顺序栈的效率较高，因为数组访问的时间复杂度为O(1)，但在栈深度接近数组大小时，可能会频繁发生数组扩容或缩容，导致额外的性能开销。因此，在设计系统时需要根据需求合理预估栈的大小，或者使用动态扩容的数据结构，如链表实现的链式栈，以适应不确定的元素数量。