Just for Life.

明月更几时

0%

C++数据结构篇『四』容器适配器：栈、队列与优先级队列

发表于 更新于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

容器适配器是依赖顺序容器的受限版本，处理特殊情况。如：

  • stack：栈，后入先出
  • queue，队列，先入先出
  • priority_queue，优先级队列，元素出队顺序取决于优先级

stack

栈是一种先入先出的数据结构，可以很好的利用这一特性解决问题。常用方法如下：

1
2
3
4
5
6
7
stack<int> s;
// 压栈
s.push(1)
// 查看栈顶元素
s.top()
// 弹栈
s.pop()

例题

Given some segments of rope, you are supposed to chain them into one rope. Each time you may only fold two segments into loops and chain them into one piece, as shown by the figure. The resulting chain will be treated as another segment of rope and can be folded again. After each chaining, the lengths of the original two segments will be halved.

Your job is to make the longest possible rope out of $N$ given segments.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer $N (2≤N≤10^​4)$. Then $N$ positive integer lengths of the segments are given in the next line, separated by spaces. All the integers are no more than $10^4$.

Output Specification:

For each case, print in a line the length of the longest possible rope that can be made by the given segments. The result must be rounded to the nearest integer that is no greater than the maximum length.

输入样例：

1
2
8
10 15 12 3 4 13 1 15

输出样例：

1
14

求解

题目大意很简单，两个绳子对折后成为一个新的绳子，这个新的绳子对折后和另外一个对折的绳子组成新的绳子，求最终绳子能有多长。使用栈这种结构会比vector插入删除元素要快上一倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include<cmath>

using namespace std;

vector <float> arr;

int cmp(int a, int b)
{
    return a > b;
}

int main(int argc, char const *argv[])
{
    int n, a;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        arr.push_back(a);
    }
    sort(arr.begin(), arr.end(), cmp);
    float temp, temp1, temp2;
    stack <float> s;
    // 按照降序压栈 先折短的 在折长的
    for (int i = 0; i < arr.size(); i++)
        s.push(arr[i]);
    while (s.size() != 1)
    {
        // 取两个栈顶元素
        temp1 = s.top();
        s.pop();
        temp2 = s.top();
        temp = temp1 / 2 + temp2 / 2;
        s.pop();
        // 压入对折后的长度
        s.push(temp);
    }
    cout << floor(s.top());
    return 0;
}

还有其他栈的应用，如『判断元素入栈出栈顺序』

queue

区别于deque，只能在队首取出元素，只能在队尾加入元素；不能在队首加入元素，不能在队尾删除元素。常用操作为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 返回队首第一个元素
front()
// 返回队尾最后一个元素
back()
// 队尾添加元素
push()
// 队首删除元素
pop()
// 大小
size()
// 是否为空
empty()
// 交换
swap()

这里需要注意的是，queue没有迭代器，只能通过队首、队尾的操作访问元素，但deque有。

priority_queue

优先级队列，同queue的使用，需要先引入头文件#include<queue>才能使用。计算机专业的人可能经常听到『优先级队列』这个词汇，尤其是在操作系统中。按照元素的优先级，决定对其进行的操作，是调用，还是继续等待。这里来直接看一个题目。

题目

Suppose a bank has $K$ windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.

Now given the arriving time $T$ and the processing time $P$ of each customer, you are supposed to tell the average waiting time of all the customers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: $N (≤10^4$) - the total number of customers, and $K (≤100)$ - the number of windows. Then $N$ lines follow, each contains 2 times: HH:MM:SS - the arriving time, and P - the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.

Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.

Output Specification:

For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.

求解

首先创建一个优先级队列，因为这个几个窗口是处理完用户就可以处理下一个用户，用户早到早处理完就早走，所以优先级设置为小，即小的元素先出队。队列的数量就是窗口的个数。然后将用户的到达时间进行排序，逐步入队。

  • 若到达时有窗口空闲，直接入队
  • 若到达时无窗口空闲，计算最少需要等待的时间，计算平均等待时间

而判断是否有空闲的方法是：判断到达时间与队首元素的值，若大于，说明到达时间大于处理完的时间，说明有空闲，否则无空闲。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 10005;
struct person {
    int come, time;
} p[maxn];
int cmp(person p1, person p2) { return p1.come < p2.come; }
int n, k, cnt, total;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int hh, ss, mm, tt;
        scanf("%d:%d:%d %d", &hh, &mm, &ss, &tt);
        int sum = hh * 3600 + mm * 60 + ss;
        if (sum > 61200) 
            continue;
        // 处理的时间
        p[++cnt].time = tt * 60;
        // 来的时间
        p[cnt].come = sum;
    }
    // 按照来的时间排序
    sort(p + 1, p + 1 + cnt, cmp);
    // 优先级队列，类型，容器类型，小的先出队
    priority_queue<int, vector<int>, greater<int> > q;
    // k 个窗口
    for (int i = 1; i <= k; ++i) 
        q.push(28800);
    for (int i = 1; i <= cnt; ++i) {
        // 来的时候有空闲，丝滑处理，无需等待
        if (q.top() <= p[i].come) {
            // 压入截止时间
            q.push(p[i].come + p[i].time);
            q.pop();
        } else {
            // 来的时候窗口有人 ，就是等待时间
            total += q.top() - p[i].come;
            // 新的截止时间
            q.push(q.top() + p[i].time);
            q.pop();
        }
    }
    (!cnt) ? printf("0.0\n") : printf("%.1lf", ((double)total/60.0)/(double) cnt);
    return 0;
}
1
2
3
4
//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;
本文相关
感谢上学期间打赏我的朋友们。赛博乞讨：我，秦始皇，打钱。

欢迎订阅我的文章