【35天从0开始备战蓝桥杯 -- Day9】
🫧个人主页：小年糕是糕手
💫个人专栏：《C++》《Linux》《数据结构》《C语言》
🎨你不能左右天气，但你可以改变心情；你不能改变过去，但你可以决定未来！
目录
一、栈和stack
1.1、栈的概述
一句话来说：栈是一种只允许在一端进行插入和删除的线性表
进行数据插入或删除的一端称为栈顶，另一端称为栈底。不含元素的栈称为空栈。进栈就是往栈中放入元素，出栈就是将元素弹出栈顶。
如果定义了一个栈结构，那么添加和删除元素只能在栈顶进行。不能随意位置添加和删除元素，这是栈这个数据结构的特性，也是规定。
大家要想深入学习可以参考下面一篇博客：
【数据结构】栈“0”基础知识讲解 + 实战演练-ZEEKLOG博客https://blog.ZEEKLOG.net/2501_91731683/article/details/153419511
1.2、模拟实现
本质还是线性表，因此可以创建一个足够大的数组，充当栈结构再定义一个变量 n，用来记录栈中元素的个数，同时还可以标记栈顶的位置。
由于栈比较简单，这里直接就模拟实现了，大家没看懂可以直接看代码中的注释结合图片理解（这里依旧舍弃下标为0的位置，有效元素从1开始记录）：
#include<iostream> using namespace std; const int N = 1e5 + 10; //创建栈 int stk[N], n;//n代表的就是有效元素个数 //进栈 -- 其实本质就是顺序表的尾插操作 //时间复杂度 -- O(1) void push(int x) { n++; stk[n] = x; } //出栈 -- 其实本质就是顺序表尾删操作 //时间复杂度 -- O(1) void pop() { n--; } //查询栈顶元素 //时间复杂度 -- O(1) int top() { return stk[n]; } //判断栈是否为空 //时间复杂度 -- O(1) bool empty() { //判断栈是否为空就是是否有有效元素 return (n == 0); } //查询有效元素个数 //时间复杂度 -- O(1) int size() { return n; } int main() { for (int i = 1; i <= 10; i++) { push(i); } //当这个栈不为空 while (!empty()) { //输出栈顶元素并删除 cout << top() << endl; pop(); } return 0; }有了前面的知识铺垫大家发现学习后面的知识是越来越得心应手的
1.3、stack
学习了前面的vector和list，相信这个容器的学习大家也是会非常轻松的：
1°创建
stack<T> st;
T 可以是任意类型的数据
2°size / empty
size：返回栈里实际元素的个数；empty：返回栈是否为空。时间复杂度：O(1)。
3°push / pop
push：进栈；pop：出栈。时间复杂度：O(1)。
4°top
top：返回栈顶元素，但是不会删除栈顶元素。时间复杂度：O(1)。
5°总结
#include<iostream> #include<stack> using namespace std; int main() { stack<int> st; //进栈 for (int i = 1; i <= 10; i++) { st.push(i); } while (st.size()) { cout << st.top() << endl; st.pop(); } return 0; }其实这段代码的本质和我们之前写的模拟实现没区别
1.4、算法题
二、队列和queue
2.1、队列的概述
一句话来说：队列也是一种特殊的线性表，它只允许在表的一端进行插入操作，另一端进行删除操作；其实举个最简单的例子，队列就很像我们去食堂打饭排的队伍，取完餐的人从前面走，想吃饭的在后面排队
允许插入的一端称为队尾，允许删除的一端称为队头。先进入队列的元素会先出队，故队列具有先进先出 (First In First Out) 的特性。
大家要想深入学习可以参考下面一篇博客：
【数据结构】队列“0”基础知识讲解 + 实战演练-ZEEKLOG博客https://blog.ZEEKLOG.net/2501_91731683/article/details/153790449
2.2、模拟实现
其实队列和栈一样结构也是非常简单，我们下面来讲解一下创建细节，后续操作便可一步到位：
一个足够大的数组充当队列；一个变量h标记队头元素的前一个位置；一个变量t标记队尾元素的位置。
两个变量(h, t]是一种左开右闭的形式（这样设定是因为我的老师是这样教我的，我用的多了习惯了也就这样写了，大家也可以按照自己的想法来，只要代码不出bug）
#include<iostream> using namespace std; const int N = 1e5 + 10; //创建 int q[N]; int h, t;//h指向队列第一个元素的前一个位置,t指向最后一个元素的位置,左开右闭 //其实这样设计的好处是t可以代表有效元素个数 //入队 //时间复杂度 -- O(1) void push(int x) { t++; q[t] = x; } //出队 //时间复杂度 -- O(1) void pop() { h++; } //查询队头元素 //返回队列中的第一个元素 //时间复杂度 -- O(1) //注意这里不能直接返回h int front() { return q[h + 1]; } //查询队尾元素 //返回队列中的最后一个元素 //时间复杂度 -- O(1) int back() { return q[t]; } //判空 //时间复杂度 -- O(1) bool empty() { return (t == h); } //有效元素个数 //时间复杂度 -- O(1) int size() { return t - h; } int main() { for (int i = 1; i <= 10; i++) { push(i); } while (size()) { cout << front() << " " << back() << endl; pop(); } return 0; }2.3、queue
1°创建
queue<T> q;
T 可以是任意类型的数据。
2°size / empty
size：返回队列里实际元素的个数；empty：返回队列是否为空。时间复杂度：O (1)。
3°push / pop
push：入队；pop：出队。时间复杂度：O (1)。
4°front / back
front：返回队头元素，但不会删除；back：返回队尾元素，但不会删除。时间复杂度：O (1)。
5°总结
#include <iostream> #include <queue> using namespace std; typedef pair<int, int> PII; int main() { // 测试 queue queue<PII> q; for (int i = 1; i <= 10; i++) { q.push({ i, i * 10 }); } while (q.size()) // while(!q.empty()) { auto t = q.front(); q.pop(); cout << t.first << " " << t.second << endl; } return 0; } 2.4、算法题
P1540 [NOIP 2010 提高组] 机器翻译 - 洛谷
2.5、双端队列和deque
双端队列也是一种特殊线性结构，其允许两端都可以进行数据元素入队和出队操作。
双端队列将队列的两端分别称为前端和后端，两端都可以进行数据入队和出队。
1°创建
deque<T> q;
T 可以是任意类型的数据。
2°size / empty
size：返回队列里实际元素的个数；empty：返回队列是否为空。时间复杂度：O (1)。
3°push_front / push_back
push_front：头插；push_back：尾插。时间复杂度：O (1)。
4°pop_front / pop_back
pop_front：头删；pop_back：尾删。时间复杂度：O (1)。
5°front / back
front：返回队头元素，但不会删除；back：返回队尾元素，但不会删除。时间复杂度：O (1)。
6°clear
clear：清空队列。时间复杂度：O (N)。
7°总结
#include <iostream> #include <deque> using namespace std; struct node { int x, y, z; }; int main() { deque<node> q; // 头插 for (int i = 1; i <= 5; i++) { q.push_front({ i, i * 2, i * 3 }); } // 头删 while (q.size()) { auto t = q.front(); q.pop_front(); cout << t.x << " " << t.y << " " << t.z << endl; } // 尾插 for (int i = 1; i <= 5; i++) { q.push_back({ i, i * 2, i * 3 }); } // 尾删 while (q.size()) { auto t = q.back(); q.pop_back(); cout << t.x << " " << t.y << " " << t.z << endl; } return 0; }
