顺序栈及其(C++)实现
现在来研究一个 IntStack 类,它存储了一个静态的整数栈并将执行刚才讨论过的栈操作。该类具有的成员变量如表 1 所示。
该类的成员函数如表 2 所示:
如果在代码执行过程中,遇到了代码无法按既定任务执行的情况,则称该代码段出现异常。在顺序栈的情况下,如果栈中没有更多的空间,则在调用 push 压栈的过程中就会发生溢出异常。同样,如果在调用 pop 出栈时栈内却没有任何内容可以返回,则会发生下溢异常。
代码在检测到异常发生之后,会立即通知程序的其余部分,方法是创建描述异常的值并使用 throw 语句将该值传递给程序的其余部分。
例如,push 函数可通过执行以下语句来通知发生溢出异常:
IntStack 构造函数可分配一个指定容量的数组,并将成员变量 top 设置为 0。所有的栈函数都使用 top,使它始终指向栈数组中的下一个可用槽。当 top 等于 capacity 时,没有更多的槽用于存储值,下一次 push 的调用就会拋出异常。
同样,当 top 为零时,栈就是空的,对 pop 的调用会抛出一个异常。因为在程序中没有任何规定来捕捉这两个异常,所以它们中的任何一个都会以错误信息终止程序。注意,在向栈中添加一个值之后,push 会递增 top 的值;而在返回存储在 stackArray[top] 中的值之前,pop 会递减 top 的值。
下面的程序演示了栈类及其成员函数的使用。请注意,在出栈的时候,其顺序刚好和值入栈的顺序相反。
图 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 函数使栈顶的值出栈并复制到形参中
成员变量 | 描 述 |
---|---|
stackArray | 指向整数数组的 unique_ptr 独占指针。当构造函数执行时,它使用 stackArray 动态分配数组的存储 |
capacity | 一个保存栈的大小的整数。这是栈最多可以保存的元素的个数,而不是当前栈中元素的最大值 |
Top | 用来标记栈顶的整数。它指定将被添加到栈的下一个项目的位置 |
该类的成员函数如表 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
图 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 函数使栈顶的值出栈并复制到形参中
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频