从0开始学C++ 第二十八课 数据结构深入 - 栈和队列

第二十八课：数据结构深入 - 栈和队列

学习目标：

1. 理解栈（Stack）的基本概念和特性。
2. 掌握队列（Queue）的基本概念和特性。
3. 学会在C++中使用栈和队列。
4. 了解栈和队列的典型应用场景。

学习内容：

1. 栈（Stack）

   • 概念：栈是一种后进先出（LIFO, Last In First Out）的数据结构，元素被添加到栈的顶部，并从栈顶部移除。
   • 栈的操作：
     • push：将一个元素放入栈顶。
     • pop：移除栈顶元素。
     • top：访问栈顶元素。
     • empty：检查栈是否为空。
   • 代码示例：

     #include <iostream>
     #include <stack>
     using namespace std;
     
     int main() {
         stack<int> stk;
     
         // 入栈
         stk.push(10);
         stk.push(20);
         stk.push(30);
     
         // 访问栈顶元素
         cout << "Top element: " << stk.top() << endl;
     
         // 出栈
         cout << "Elements: ";
         while (!stk.empty()) {
             cout << stk.top() << " ";
             stk.pop();
         }
         cout << endl;
     
         return 0;
     }
     

   • 预计输出效果：

     Top element: 30
     Elements: 30 20 10
     

   • 使用场景：栈用于解决像浏览器前进后退、函数调用、括号匹配等问题。

2. 队列（Queue）

   • 概念：队列是一种先进先出（FIFO, First In First Out）的数据结构，元素被添加到队列的末尾，并从队列的前端移除。
   • 队列的操作：
     • enqueue 或 push：将一个元素添加到队列末尾。
     • dequeue 或 pop：移除队列前端的元素。
     • front：访问队列前端的元素。
     • empty：检查队列是否为空。
   • 代码示例：

     #include <iostream>
     #include <queue>
     using namespace std;
     
     int main() {
         queue<int> q;
     
         // 入队
         q.push(10);
         q.push(20);
         q.push(30);
     
         // 访问队首元素
         cout << "Front element: " << q.front() << endl;
     
         // 出队
         cout << "Elements: ";
         while (!q.empty()) {
             cout << q.front() << " ";
             q.pop();
         }
         cout << endl;
     
         return 0;
     }
     

   • 预计输出效果：

     Front element: 10
     Elements: 10 20 30
     

   • 使用场景：队列用于任务排队、缓冲处理、打印队列等场景。

练习题：

编写一个C++程序，创建一个栈和一个队列。首先向栈中压入三个整数：1，2，3，然后依次弹出并打印。接着向队列中加入同样的三个整数，并依次从队列中移除并打印。

答案：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

int main() {
    stack<int> s; // 创建栈
    queue<int> q; // 创建队列

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

    cout << "Stack elements (LIFO order): ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;

    // 队列操作
    q.push(1);
    q.push(2);
    q.push(3);

    cout << "Queue elements (FIFO order): ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    return 0;
}

预计输出效果：

Stack elements (LIFO order): 3 2 1
Queue elements (FIFO order): 1 2 3

以上示例和练习涉及到栈和队列的基本操作，通过实际的代码演示帮助你理解这些结构的工作原理。在实际应用中，栈和队列是非常有用的数据结构，对于理解更复杂的数据结构和算法也是非常重要的基础。