顺序栈及其（C++）实现
发布时间：2020-12-16 07:36:46 所属栏目：百科 来源：网络整理
导读：现在来研究一个 IntStack 类，它存储了一个静态的整数栈并将执行刚才讨论过的栈操作。该类具有的成员变量如表 1 所示。 表 1 栈类的成员变量 成员变量 描?述 stackArray 指向整数数组的 unique_ptr 独占指针。当构造函数执行时，它使用 stackArray 动态分配数
现在来研究一个 IntStack 类，它存储了一个静态的整数栈并将执行刚才讨论过的栈操作。该类具有的成员变量如表 1 所示。
该类的成员函数如表 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. . .  图 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 函数使栈顶的值出栈并复制到形参中 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |