C++的数据结构(三):栈

发布于:2024-05-15 ⋅ 阅读:(200) ⋅ 点赞:(0)

        栈(Stack)是一种后进先出(LIFO, Last In First Out)的数据结构,它只允许在一端(称为栈顶)进行插入和删除操作。栈的这种特性使得它在解决函数调用、括号匹配、表达式求值等问题时具有天然的优势。在C++中,栈可以通过标准库中的`std::stack`模板类来实现,也可以手动使用数组或链表等数据结构来实现。

        根据底层实现的不同,栈可以分为静态栈和动态栈。静态栈是在编译时确定其大小,通常使用数组来实现;动态栈则是在运行时动态分配内存,大小可以随需调整,通常使用链表或动态数组来实现。

        基于数组的栈通常包括以下几个部分:

        1. 一个数组,用于存储栈中的元素。
        2. 一个整型变量,用于记录栈顶元素的位置(通常指向栈顶元素的下一个位置)。

        当进行入栈操作时,将元素放入数组的末尾,并更新栈顶位置;当进行出栈操作时,从数组的末尾移除元素,并更新栈顶位置。

        下面是一个简单的基于数组的栈操作的C++实现:

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std; 
template <typename T>
class ArrayStack {
private:
    vector<T> elements;

public:
    // 判断栈是否为空
    bool isEmpty() const {
        return elements.empty();
    }

    // 获取栈的大小
    size_t size() const {
        return elements.size();
    }

    // 入栈操作
    void push(const T& value) {
        elements.push_back(value);
    }

    // 出栈操作
    void pop() {
        if (isEmpty()) {
            throw out_of_range("Stack is empty!");
        }
        elements.pop_back();
    }

    // 获取栈顶元素
    T& top() {
        if (isEmpty()) {
            throw out_of_range("Stack is empty!");
        }
        return elements.back();
    }

    // 获取栈顶元素(常量版本)
    const T& top() const {
        if (isEmpty()) {
            throw out_of_range("Stack is empty!");
        }
        return elements.back();
    }
};

int main() {
    ArrayStack<int> stack;

    // 入栈操作
    stack.push(1);
    stack.push(2);
    stack.push(3);

    // 输出栈的大小
    cout << "Size of stack: " << stack.size() << std::endl;

    // 输出栈顶元素
    cout << "Top element: " << stack.top() << std::endl;

    // 出栈操作
    stack.pop();
    stack.pop();

    // 再次输出栈顶元素
    cout << "Top element after popping: " << stack.top() << std::endl;

    return 0;
}

        结果如下所示:

           在这个例子中,我们使用`vector`作为底层数组来实现栈。`push`方法用于入栈操作,将元素添加到数组的末尾;`pop`方法用于出栈操作,移除数组的最后一个元素;`top`方法用于获取栈顶元素。此外,我们还提供了`isEmpty`和`size`方法来检查栈是否为空以及获取栈的大小。在`main`函数中,我们展示了如何使用这个基于数组的栈类进行基本的栈操作。


网站公告

今日签到

点亮在社区的每一天
去签到