> 文档中心 > 数据结构入门——队列

数据结构入门——队列


关于设置关注可见

设置这个就是为了卡一下网上的各种搬运,可以关注之后再取关,这样就可以看了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 n106 的数组。

有一个大小为 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;}