栈的C++数组实现

栈是一种后进先出（LIFO）的数据结构，它只允许在一端（称为栈顶）进行插入和删除操作。在C++中，我们可以使用数组来实现栈的基本功能。本文将介绍如何使用C++数组来实现一个简单的栈，并通过代码示例详细解释栈的基本操作。

一、栈的基本概念

栈（Stack）是一种特殊的线性数据结构，它具有以下特性：

• 只能在栈顶进行插入和删除操作。
• 栈是后进先出（Last In First Out, LIFO）的数据结构。

栈的基本操作包括：

• push：在栈顶插入一个元素。
• pop：删除并返回栈顶的元素。
• top：返回栈顶的元素，但不删除。
• isEmpty：检查栈是否为空。

二、使用C++数组实现栈

在C++中，数组是一种内置的数据结构，我们可以使用它来模拟栈的行为。

类定义

class Stack {  
private:  
    int topIndex; // 栈顶索引，-1表示栈空  
    const int maxSize; // 栈的最大容量，由构造函数设置并保持不变  
    int* stackArray; // 指向整数数组的指针，该数组用于存储栈中的元素  

public:  
    // 构造函数
    Stack(int size); 
    // 析构函数
    ~Stack();
    // 入栈操作
    void push(int value);
    // 出栈操作
    int pop();
    // 查看栈顶元素
    int top() const;
    // 检查栈是否为空
    bool isEmpty() const;
};

构造函数

Stack::Stack(int size) : maxSize(size), topIndex(-1) {  
    stackArray = new int[maxSize];  
}

构造函数接收一个整数size作为参数，并初始化maxSize和topIndex。使用new运算符动态分配一个整数数组，其大小为maxSize，并让stackArray指向它。

析构函数

Stack::~Stack() {  
    delete[] stackArray;  
}

析构函数在对象被销毁时调用，用于释放stackArray指向的动态分配的内存。

入栈操作（push）

void Stack::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。

出栈操作（pop）

int Stack::pop() {  
    if (isEmpty()) {  
        throw std::out_of_range("Stack is empty!");  
    }  
    return stackArray[topIndex--];  
}

首先调用isEmpty函数检查栈是否为空。如果栈非空，则返回当前topIndex位置的元素，并将topIndex减1。

查看栈顶元素（top）

int Stack::top() const {  
    if (isEmpty()) {  
        throw std::out_of_range("Stack is empty!");  
    }  
    return stackArray[topIndex];  
}

同样先检查栈是否为空。如果栈非空，则返回当前topIndex位置的元素，但不修改topIndex。

检查栈是否为空（isEmpty）

bool Stack::isEmpty() const {  
    return topIndex == -1;  
}

如果topIndex等于-1，则栈为空，返回true；否则返回false。

主函数（main）

int main() {  
    try {  
        Stack stack(5); // 创建一个容量为5的栈实例  
        // ... 执行栈操作，包括push、pop和top  
    } catch (const std::out_of_range& e) {  
        std::cerr << "Error: " << e.what() << std::endl;  
        return 1;  
    }  
    return 0;  
}

在main函数中，使用try-catch块来捕获可能由栈操作抛出的std::out_of_range异常。创建一个Stack对象，并对其进行一系列操作，包括入栈、出栈和查看栈顶元素。

总结

这个简单的栈实现使用C++数组作为底层数据结构，并通过封装提供了栈的基本操作接口。它遵循栈的后进先出（LIFO）原则，并通过异常处理机制提供了错误检查。在实际应用中，这种数据结构对于需要按照特定顺序处理元素的场景非常有用。