c++怎么实现一个栈stack_c++栈结构的实现方法-C++-PHP中文网

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

裘德小鎮的故事

发布： 2025-10-26 12:08:01

原创

751人浏览过

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

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

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

1. 使用类封装栈结构

定义一个模板类Stack，支持任意数据类型，并使用动态数组管理内存。

#include <iostream>
#include <stdexcept>

template<typename T>
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<int> 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;
}

登录后复制