数据结构入门——队列
关于设置关注可见
设置这个就是为了卡一下网上的各种搬运,可以关注之后再取关,这样就可以看了hh
0.序
如果在这一块遇见啥问题可以留言讨论
while(keep) ability++;
1. 前言
对刚开始学算法与数据结构的人来说,队列应该是在栈之后要学的东西(或者是数组or链表)。不过也就是洒洒水的事情~还是不难的。
队列
概念
首先我们知道:
- 队列是一个线性的数据结构(应该很好懂),同时队列是一个受限制的线性数据结构。
- 我们只能在一端添加元素,另一端删除元素(和数组相比实在是太弱了)
- 能添加元素的一端称为队尾,删除元素的一端称为队头。
- 这时我们就能发现,这是一个先进先出的结构,就像是排队一样,从尾巴进去 从头上出来hh
队列的操作
- 添加
- 删除
(在上面已经提到了hh)
关于实现一个队列
队列的实现形式大概上有两种——数组,链表
head:记录队头的位置
tail:记录队尾的位置
当tail<head时,表示队列中没有元素
int head = 1, tail = 0;int q[100000 + 10];void push(int x) {q[++tail] = x;}int pop() {return q[head++];}
如果你是高贵的带模板的语言的用户 such as C++
queue q;q.push(x);q.pop();
举个栗子
#include #include #include const int N = 1000000 + 10;using namespace std;int q[N], head = 1, tail = 0;void push(int x) { q[++tail] = x;}int pop() { return q[head++];}int main(){ int n; cin >> n; string s; for (int i = 1; i <= n; i++) { cin >> s; if (s == "push") { int x; cin >> x; push(x); } else if (s == "pop") { pop(); } else if (s == "empty") { if (tail < head) { cout << "YES" << '\n'; } else puts("NO"); } else { cout << q[head] << '\n'; } } return 0;}
一点高级的东西——单调队列(or滑动窗口?)
有些时候我们需要一些具有特殊性质的队列,来更好的完成题目要求。
举个栗子
给定一个大小为 n ≤ 1 0 6 n≤10^6 n≤106 的数组。
有一个大小为 k k k 的滑动窗口,它从数组的最左边移动到最右边。
你只能在窗口中看到 k k k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子:
该数组为 [1 3 -1 -3 5 3 6 7]
, k k k 为 3 3 3。
窗口位置 | 最小值 | 最大值 |
---|---|---|
[1 3 -1] -3 5 3 6 7 | -1 | 3 |
1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n n n 和 k k k,分别代表数组长度和滑动窗口的长度。
第二行有 n n n 个整数,代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出,从左至右,每个位置滑动窗口中的最小值。
第二行输出,从左至右,每个位置滑动窗口中的最大值。
输入样例:
8 31 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 33 3 5 5 6 7
啥叫单调队列
顾名思义啊,和单调栈差不多。就是队列里的元素是单调递增或者单调递减的,所以叫他单调队列。
为啥要用单调队列
因为…单调队列的复杂度是 O ( n ) O(n) O(n)的,可以肥肠愉悦的通过 1 0 6 10^6 106的数据范围
为啥会是 O ( n ) O(n) O(n)嘞
参考关于单调栈的解释=。=
怎么搞一个单调队列
在保持队列内元素单调递增/单调递减的前提下(如果队头元素大于要入队的元素,将其弹出),将新元素入队。
#include #include #include const int N = 1000000 + 10;using namespace std;int n, k, a[N];int q[N], head = 1, tail = 0;int p[N];void print_min() {head = 1;tail = 0;for (int i = 1; i <= n; i++) {while (head = a[i]) {tail--;}q[++tail] = a[i];p[tail] = i;while (p[head] = k) {printf("%d ", q[head]);}}puts("");}void print_max() {head = 1;tail = 0;for (int i = 1; i <= n; i++) {while (head <= tail && q[tail] <= a[i]) {tail--;}q[++tail] = a[i];p[tail] = i;while (p[head] = k) {printf("%d ", q[head]);}}puts("");}int main(){ cin >> n >> k; for (int i = 1; i > a[i]; } print_min(); print_max(); return 0;}