栈是一种后进先出(LIFO)的数据结构,它只允许在一端(称为栈顶)进行插入和删除操作。在C++中,我们可以使用数组来实现栈的基本功能。本文将介绍如何使用C++数组来实现一个简单的栈,并通过代码示例详细解释栈的基本操作。
一、栈的基本概念
栈(Stack)是一种特殊的线性数据结构,它具有以下特性:
- 只能在栈顶进行插入和删除操作。
- 栈是后进先出(Last In First Out, LIFO)的数据结构。
栈的基本操作包括:
- push:在栈顶插入一个元素。
- pop:删除并返回栈顶的元素。
- top:返回栈顶的元素,但不删除。
- isEmpty:检查栈是否为空。
二、使用C++数组实现栈
在C++中,数组是一种内置的数据结构,我们可以使用它来模拟栈的行为。下面我将详细解析这个代码中的每个部分:
1.类定义
class Stack {
private:
int topIndex; // 栈顶索引,-1表示栈空
const int maxSize; // 栈的最大容量,由构造函数设置并保持不变
int* stackArray; // 指向整数数组的指针,该数组用于存储栈中的元素
public:
// ... 构造函数、析构函数和成员函数
};
private部分定义了三个成员变量:topIndex(栈顶索引)、maxSize(栈的最大容量)和stackArray(指向栈数组的指针)。
public部分定义了构造函数、析构函数和栈的基本操作函数。
2.构造函数
Stack(int size) : maxSize(size), topIndex(-1) {
stackArray = new int[maxSize];
}
构造函数接收一个整数size作为参数,并初始化maxSize和topIndex。
使用new运算符动态分配一个整数数组,其大小为maxSize,并让stackArray指向它。
3.析构函数
~Stack() {
delete[] stackArray;
}
析构函数在对象被销毁时调用,用于释放stackArray指向的动态分配的内存。
4.入栈操作(push)
void push(int value) {
if (topIndex >= maxSize - 1) {
throw std::out_of_range("Stack is full!");
}
stackArray[++topIndex] = value;
}
首先检查栈是否已满(topIndex >= maxSize - 1)。
如果栈未满,则先将topIndex加1,然后在新的topIndex位置存储value。
5.出栈操作(pop)
int pop() {
if (isEmpty()) {
throw std::out_of_range("Stack is empty!");
}
return stackArray[topIndex--];
}
首先调用isEmpty函数检查栈是否为空。
如果栈非空,则返回当前topIndex位置的元素,并将topIndex减1。
6.查看栈顶元素(top)
int top() const {
if (isEmpty()) {
throw std::out_of_range("Stack is empty!");
}
return stackArray[topIndex];
}
同样先检查栈是否为空。
如果栈非空,则返回当前topIndex位置的元素,但不修改topIndex。
7.检查栈是否为空(isEmpty)
bool isEmpty() const {
return topIndex == -1;
}
如果topIndex等于-1,则栈为空,返回true;否则返回false。
8.主函数(main)
int main() {
try {
Stack stack(5); // 创建一个容量为5的栈实例
// ... 执行栈操作,包括push、pop和top
} catch (const std::out_of_range& e) {
std::cerr