C++第二十六弹---stack和queue的基本操作详解与模拟实现

在C++中，stack（栈）和queue（队列）是两个常用的数据结构，它们在计算机程序设计中有着广泛的应用。在这篇文章中，我们将详细介绍它们的基本操作并给出模拟实现的代码示例。

栈（Stack）

栈是一种后进先出（LIFO, Last In First Out）的数据结构。栈的基本操作包括：

1. 入栈（Push）：将一个元素添加到栈的顶部。
2. 出栈（Pop）：移除栈顶的元素。
3. 查看栈顶元素（Top）：返回栈顶的元素，但不移除它。
4. 判断栈是否为空（IsEmpty）：判断栈是否为空。

下面是一个简单的栈的实现：

#include <iostream>
#include <vector>

class Stack {
private:
    std::vector<int> data;

public:
    void push(int value) {
        data.push_back(value);
    }

    void pop() {
        if (!isEmpty()) {
            data.pop_back();
        } else {
            std::cerr << "栈为空，无法出栈！" << std::endl;
        }
    }

    int top() {
        if (!isEmpty()) {
            return data.back();
        } else {
            std::cerr << "栈为空，无法获取栈顶元素！" << std::endl;
            return -1; // 代表错误，实际使用中可以抛出异常
        }
    }

    bool isEmpty() {
        return data.empty();
    }
};

int main() {
    Stack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);

    std::cout << "栈顶元素: " << stack.top() << std::endl; // 输出 3
    stack.pop();
    std::cout << "栈顶元素: " << stack.top() << std::endl; // 输出 2

    return 0;
}

队列（Queue）

队列是一种先进先出（FIFO, First In First Out）的数据结构。队列的基本操作包括：

1. 入队（Enqueue）：将一个元素添加到队列的尾部。
2. 出队（Dequeue）：移除队列前端的元素。
3. 查看队头元素（Front）：返回队头的元素，但不移除它。
4. 判断队列是否为空（IsEmpty）：判断队列是否为空。

下面是一个简单的队列的实现：

#include <iostream>
#include <vector>

class Queue {
private:
    std::vector<int> data;

public:
    void enqueue(int value) {
        data.push_back(value);
    }

    void dequeue() {
        if (!isEmpty()) {
            data.erase(data.begin()); // 从头部移除元素
        } else {
            std::cerr << "队列为空，无法出队！" << std::endl;
        }
    }

    int front() {
        if (!isEmpty()) {
            return data.front();
        } else {
            std::cerr << "队列为空，无法获取队头元素！" << std::endl;
            return -1; // 代表错误
        }
    }

    bool isEmpty() {
        return data.empty();
    }
};

int main() {
    Queue queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    std::cout << "队头元素: " << queue.front() << std::endl; // 输出 1
    queue.dequeue();
    std::cout << "队头元素: " << queue.front() << std::endl; // 输出 2

    return 0;
}

总结

通过以上的代码示例，我们实现了基本的栈和队列数据结构。在实际编程中，栈通常用于解决递归问题、表达式求值等，而队列则常用于任务调度、广度优先搜索等场景。理解这两种数据结构的特性和基本操作，对程序设计及算法的实现具有非常重要的意义。