首页 > 编程笔记 > C++笔记 阅读:521

顺序栈及其(C++)实现

现在来研究一个 IntStack 类,它存储了一个静态的整数栈并将执行刚才讨论过的栈操作。该类具有的成员变量如表 1 所示。
表 1 栈类的成员变量
成员变量 描 述
stackArray 指向整数数组的 unique_ptr 独占指针。当构造函数执行时,它使用 stackArray 动态分配数组的存储
capacity 一个保存栈的大小的整数。这是栈最多可以保存的元素的个数,而不是当前栈中元素的最大值
Top 用来标记栈顶的整数。它指定将被添加到栈的下一个项目的位置

该类的成员函数如表 2 所示:
表 2 栈类的成员函数
成员函数 描 述
构造函数 该类的构造函数将接受一个整数参数,该参数指定了栈的大小。这个大小的整数数组被动态分配存储并赋值给 stackArray。另外,变量 top 被初始化为 0,表示栈当前为空
push push 函数接受一个整数参数,该参数将被压入栈顶
pop pop 函数使用一个整数引用形参。栈顶部的值被删除并复制到引用形参中
isEmpty 如果栈为空则返回 true,否则返回 false。top 设置为 0 时则栈为空

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

该类的代码显示如下:
//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,所以该栈是空的。

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

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

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

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

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

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

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