C++ 中的栈和队列

在本文中，我们将介绍C++中的栈和队列的概念、特点以及应用。栈和队列是常用的数据结构，它们具有不同的特点和用途，对于程序开发和问题解决非常重要。

阅读更多：C++ 教程

栈(Stack)

栈是一种后进先出（Last-In-First-Out, LIFO）的数据结构。栈的操作只允许在栈顶进行，即只能在栈顶插入（称为入栈或压栈）或从栈顶删除（称为出栈或弹栈）元素。一般来说，栈只允许访问、插入和删除栈顶元素，不允许访问和修改其他元素。

在C++中，可以使用标准库的stack模板类来实现栈。对于栈来说，最常用的操作是push()和pop()。push()用于将元素压入栈顶，pop()用于将栈顶的元素弹出。此外，top()函数用于获取栈顶的元素值，empty()函数用于判断栈是否为空，size()函数用于获取栈的大小。

下面是一个示例代码，演示了如何使用stack实现栈的基本操作：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // 入栈
    s.push(1);
    s.push(2);
    s.push(3);

    // 获取并输出栈顶元素
    std::cout << "栈顶元素：" << s.top() << std::endl;

    // 弹栈
    s.pop();

    // 获取并输出栈顶元素
    std::cout << "弹栈后的栈顶元素：" << s.top() << std::endl;

    // 判断栈是否为空
    if (s.empty()) {
        std::cout << "栈为空" << std::endl;
    } else {
        std::cout << "栈不为空" << std::endl;
    }

    // 获取栈的大小
    std::cout << "栈的大小：" << s.size() << std::endl;

    return 0;
}

在上述代码中，我们首先创建了一个整数类型的栈s，然后通过push()操作入栈了1、2、3三个元素。接着使用top()函数获取并输出了栈顶元素，然后使用pop()操作弹出了栈顶元素。最后使用empty()判断栈是否为空，并使用size()函数获取了栈的大小。

除了基本操作，栈还具有一些其他的应用。例如，在表达式求值、函数调用和深度优先搜索等算法中，栈都有广泛的应用。

队列(Queue)

队列是一种先进先出（First-In-First-Out, FIFO）的数据结构。队列的操作分为两端，即入队（enqueue）和出队（dequeue）操作。新元素只能从一端（一般是队尾）插入队列，而只能从另一端（一般是队头）删除元素。可以将队列想象成排队买票，先到先得的场景。

在C++中，可以使用标准库的queue模板类来实现队列。对于队列来说，最常用的操作是push()和pop()。push()用于将元素加入队列，pop()用于将队头的元素删除。此外，可以使用front()函数获取队头元素的值，back()函数获取队尾元素的值，empty()函数判断队列是否为空，size()函数获取队列的大小。

下面是一个示例代码，演示了如何使用queue实现队列的基本操作：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // 入队
    q.push(1);
    q.push(2);
    q.push(3);

    // 获取并输出队头元素
    std::cout << "队头元素：" << q.front() << std::endl;

    // 出队
    q.pop();

    // 获取并输出队头元素
    std::cout << "出队后的队头元素：" << q.front() << std::endl;

    // 判断队列是否为空
    if (q.empty()) {
        std::cout << "队列为空" << std::endl;
    } else {
        std::cout << "队列不为空" << std::endl;
    }

    // 获取队列的大小
    std::cout << "队列的大小：" << q.size() << std::endl;

    return 0;
}

在上述代码中，我们首先创建了一个整数类型的队列q，然后通过push()操作入队了1、2、3三个元素。接着使用front()函数获取并输出了队头元素，然后使用pop()操作删除了队头元素。最后使用empty()判断队列是否为空，并使用size()函数获取了队列的大小。

与栈类似，队列也具有其他的应用。例如，在广度优先搜索、缓冲区管理和多线程程序等场景中，队列有着重要的作用。