第二十八课:数据结构深入 – 栈和队列
学习目标:
- 理解栈(Stack)的基本概念和特性。
- 掌握队列(Queue)的基本概念和特性。
- 学会在C++中使用栈和队列。
- 了解栈和队列的典型应用场景。
学习内容:
栈(Stack)
- 概念:栈是一种后进先出(LIFO, Last In First Out)的数据结构,元素被添加到栈的顶部,并从栈顶部移除。
- 栈的操作:
push
:将一个元素放入栈顶。pop
:移除栈顶元素。top
:访问栈顶元素。empty
:检查栈是否为空。
- 代码示例:
#include #include 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: 30Elements: 30 20 10
- 使用场景:栈用于解决像浏览器前进后退、函数调用、括号匹配等问题。
队列(Queue)
- 概念:队列是一种先进先出(FIFO, First In First Out)的数据结构,元素被添加到队列的末尾,并从队列的前端移除。
- 队列的操作:
enqueue
或push
:将一个元素添加到队列末尾。dequeue
或pop
:移除队列前端的元素。front
:访问队列前端的元素。empty
:检查队列是否为空。
- 代码示例:
#include #include 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: 10Elements: 10 20 30
- 使用场景:队列用于任务排队、缓冲处理、打印队列等场景。
练习题:
编写一个C++程序,创建一个栈和一个队列。首先向栈中压入三个整数:1,2,3,然后依次弹出并打印。接着向队列中加入同样的三个整数,并依次从队列中移除并打印。
答案:
#include #include #include 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 1Queue elements (FIFO order): 1 2 3
以上示例和练习涉及到栈和队列的基本操作,通过实际的代码演示帮助你理解这些结构的工作原理。在实际应用中,栈和队列是非常有用的数据结构,对于理解更复杂的数据结构和算法也是非常重要的基础。
目录
第二十九课 冒泡排序和选择排序