顺序栈及其（C++）实现

该类的成员函数如表 2 所示：

注意，即使构造函数会动态地为栈数组分配存储，但是它仍然被视为一个顺序栈，因为一旦分配完毕，该栈的大小就不能改变。

该类的代码显示如下：

//IntStack.h 的内容
#include <memory>
using namespace std;
class IntStack
{
    unique_ptr<int[]>stackArray;
    int capacity;
    int top;
  public:
    // Constructor
    IntStack(int capacity);
    // Member functions
    void push(int value);
    void pop (int &value);
    bool isEmpty() const;
    // Stack Exceptions
    class Overflow {};
    class Underflow {};
};

除了表 2 中描述的栈成员之外，IntStack 类还定义了两个名为 Overflow 和 Underflow 的内部类，用作栈异常。

如果在代码执行过程中，遇到了代码无法按既定任务执行的情况，则称该代码段出现异常。在顺序栈的情况下，如果栈中没有更多的空间，则在调用 push 压栈的过程中就会发生溢出异常。同样，如果在调用 pop 出栈时栈内却没有任何内容可以返回，则会发生下溢异常。

代码在检测到异常发生之后，会立即通知程序的其余部分，方法是创建描述异常的值并使用 throw 语句将该值传递给程序的其余部分。

例如，push 函数可通过执行以下语句来通知发生溢出异常：

throw InstStack::Overflow();

而 pop 函数则可以执行以下语句：

throw IntStack::Underflow();

该语句通知程序发生了下溢异常。默认情况下，当程序的任何部分抛出异常时，程序将终止并显示错误消息。这个默认行为可以通过一个被称为捕获异常的进程来改变。

IntStack 构造函数可分配一个指定容量的数组，并将成员变量 top 设置为 0。所有的栈函数都使用 top，使它始终指向栈数组中的下一个可用槽。当 top 等于 capacity 时，没有更多的槽用于存储值，下一次 push 的调用就会拋出异常。

同样，当 top 为零时，栈就是空的，对 pop 的调用会抛出一个异常。因为在程序中没有任何规定来捕捉这两个异常，所以它们中的任何一个都会以错误信息终止程序。注意，在向栈中添加一个值之后，push 会递增 top 的值；而在返回存储在 stackArray[top] 中的值之前，pop 会递减 top 的值。

//IntStack.cpp 的内容
#include "intstack.h"
IntStack::IntStack(int capacity)
{
    stackArray = make_unique<int[]>(capacity);
    this->capacity = capacity;
    top = 0;
}
void IntStack::push(int value)
{
    if (top == capacity)
        throw IntStack::Overflow();
    stackArray[top] = value;
    top++;
}
bool IntStack::isEmpty() const
{
    return top == 0;
}
void IntStack::pop(int &value)
{
    if (isEmpty()) throw IntStack::Underflow();
    top--;
    value = stackArray[top];
}

下面的程序演示了栈类及其成员函数的使用。请注意，在出栈的时候，其顺序刚好和值入栈的顺序相反。

// This program illustrates the IntStack class.
#include "intstack.h"
#include <iostream>
using namespace std;
int main()
{
    IntStack stack(5);
    int values[] = { 5, 10, 15, 20, 25 };
    int value;
    cout << "Pushing. . . /n";
    for (int k = 0; k < 5; k++)
    {
        cout << values[k] << " ";
        stack.push(values[k]);
    }
    cout << "/nPopping. . ./n";
    while (!stack.isEmpty())
    {
        stack.pop(value);
        cout << value << " ";
    }
    cout << endl;
    return 0;
}

程序输出结果：

Pushing. . .
5 10 15 20 25
Popping. . .
25 20 15 10 5

在此程序中，使用参数 5 调用构造函数，这将如图 1 所示设置成员变量。由于 top 被设置为 0，所以该栈是空的。

图 1 使用构造函数和参数 5 创建的栈

图 2 显示了第一次调用 push 函数（以 5 为参数）后的成员变量的状态。top 的值现在是 1。

图 2 调用 push 函数（以 5 为参数）压栈之后栈的状态

图 3 显示了 5 次调用 push 函数后的成员变量的状态。现在最高有 5 个值，该栈已满。

图 3 调用 push 函数执行 5 次压栈操作之后的状态

注意看 pop 函数，它使用了一个引用形参 value。出栈的值将被复制到 value 中，以便稍后在程序中使用。图 4 描述了在调用 pop 函数使第一个值出栈之后，类成员和 value 参数的状态。

图 5 调用 pop 函数使栈顶的值出栈并复制到形参中