c++怎么实现一个栈stack_c++栈结构的实现方法

答案：C++中基于动态数组实现栈，支持push、pop、top等操作，采用模板类封装，具备动态扩容、异常处理和RAII内存管理机制，适用于任意数据类型。

在C++中实现一个栈，可以使用数组或链表来存储数据，同时遵循“后进先出”（LIFO）的原则。下面是一个基于动态数组的栈实现，包含常用操作：入栈（push）、出栈（pop）、查看栈顶元素（top）、判断是否为空（empty）以及获取大小（size）。

1. 使用类封装栈结构

#include 
#include 

template
class Stack {
private:
    T* data;          // 动态数组存储元素
    int capacity;     // 当前容量
    int topIndex;     // 栈顶索引

    void resize() {
        capacity *= 2;
        T* newData = new T[capacity];
        for (int i = 0; i < topIndex; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
    }

public:
    // 构造函数
    Stack(int initCapacity = 4) : capacity(initCapacity), topIndex(0) {
        data = new T[capacity];
    }

    // 析构函数
    ~Stack() {
        delete[] data;
    }

    // 拷贝构造函数
    Stack(const Stack& other) : capacity(other.capacity), topIndex(other.topIndex) {
        data = new T[capacity];
        for (int i = 0; i < topIndex; ++i) {
            data[i] = other.data[i];
        }
    }

    // 赋值操作符
    Stack& operator=(const Stack& other) {
        if (this != &other) {
            delete[] data;
            capacity = other.capacity;
            topIndex = other.topIndex;
            data = new T[capacity];
            for (int i = 0; i < topIndex; ++i) {
                data[i] = other.data[i];
            }
        }
        return *this;
    }

    // 入栈
    void push(const T& value) {
        if (topIndex == capacity) {
            resize();
        }
        data[topIndex++] = value;
    }

    // 出栈
    void pop() {
        if (empty()) {
            throw std::underflow_error("Stack is empty!");
        }
        --topIndex;
    }

    // 获取栈顶元素
    T& peek() {
        if (empty()) {
            throw std::underflow_error("Stack is empty!");
        }
        return data[topIndex - 1];
    }

    // 是否为空
    bool empty() const {
        return topIndex == 0;
    }

    // 获取元素个数
    int size() const {
        return topIndex;
    }
};

2. 使用示例

int main() {
    Stack s;

    s.push(10);
    s.push(20);
    s.push(30);

    std::cout << "Top element: " << s.peek() << std::endl;  // 输出 30
    std::cout << "Size: " << s.size() << std::endl;         // 输出 3

    s.pop();
    std::cout << "After pop, top: " << s.peek() << std::endl; // 输出 20

    while (!s.empty()) {
        std::cout << s.peek() << " ";
        s.pop();
    }
    // 输出：20 10

    return 0;
}

3. 关键点说明

• 动态扩容：当数组满时自动扩容为原来的两倍，保证插入效率。
• 异常处理：对空栈调用pop或peek时抛出异常，避免非法访问。
• 模板支持：可适用于int、double、std::string等类型。
• RAII管理资源：通过析构函数自动释放内存，防止泄漏。

基本上就这些。自己实现栈有助于理解底层原理，实际项目中也可以直接使用std::stack。

LALAL.AI

AI人声去除器和声乐提取工具

下载