Codeforces 704A (队列模拟) Thor

Codeforces是一家知名程式竞赛网站，每周都会有各种比赛和练习赛。在这些比赛中，大部分的题目都是需要用程序解决的算法问题。其中一道经典的题目就是Codeforces 704A (队列模拟) Thor。本文将详细介绍这道经典的算法题目。

题目描述

Codeforces 704A (队列模拟) Thor 的题目描述如下：

Thor 有一个队列，其中一些元素是显示在屏幕上的。每个元素可以被清除，这样将从队列的开头移除元素之后它就会从屏幕上消失。现在，和队列一起用于控制显示的元素的是一列表情。如果 Thor 要增加一个显示元素，则它必须是列表情之一。如果他想清除一个屏幕上的元素，那么它必须是列表情之一。没错，列表情就是本题关键的点。

注意到在一个元素从队列的开头被移除，屏幕上相应的元素也会消失。

你需要用程序模拟这些操作。也就是说，你需要维护这个队列和它上面的显示元素，能够处理以下两种操作之一：

• get 保证队首是显示在屏幕上的元素。将它从队列中移除，并且从屏幕上消失。
• put x 把 x 加入到队列的末尾。如果 x 存在于列表情中，就把它插入在屏幕上；否则不会插入。

你需要编写一个程序，读入一个列表情的字符串（就像题目描述中），并能够处理以上两种操作，输出程序不断操作后最后队列的状态。

输入格式

输入一个列表情的字符串，由若干个整数和字母 'p'，'g' 组成。

输出格式

按 // get p get 输出程序不断操作后最后队列的状态。 的形式输出调用 get 操作后，因为顺序而可能会从屏幕上删除的元素，以及仍然在队列中的元素。如果没有元素在屏幕上的，那么输出字符串 "-"。元素之间的顺序不能被改变。在输出队列中的元素之前，请不要忘记在行末添加换行符。

样例输入

3
put 1
put 2
g
g
g
put 3
put 4

样例输出

1
-
2

解题思路

我们可以用一个双端队列 deque 表示维护队列在尾部加入和头部弹出。同时用一个集合 pset 维护当前屏幕上显示的元素，便于快速判断一个元素是否在屏幕上。

具体实现时，遇到 put 操作，我们首先判断插入的元素是否为列表情中的元素，若是，则将其插入到队列尾部，并在集合 pset 中插入该元素；若否，则只将元素插入到队列尾部。

遇到 get 操作时，我们直接从队列头部弹出元素，并在集合 pset 中删除该元素。

注意：这里的队列操作是 FIFO 先进去的元素先被弹出，而选 【需要被清理（get 操作）的元素】 是 【队列开头】 的元素，因此无论从哪个数据结构中弹出需要被清理的元素都应该是队列开头的元素。

最后输出队列中的剩余元素以及当前屏幕上显示的元素即可。

代码实现详见下方

代码实现

import collections

n = int(input())
pset = set()
dq = collections.deque()
for i in range(n):
    line = input().split()
    if line[0] == 'put':
        dq.append(line[1])
        if line[1].isdigit():
            pset.add(int(line[1]))
    else:
        if not dq: # 如果队列为空，输出 -
            print('-')
        else:
            x = dq.popleft()
            if int(x) in pset: # 如果弹出的元素在屏幕上，就从集合中删除
                pset.remove(int(x))
    if pset: # 如果有元素在屏幕上，输出第一个元素
        print(pset.pop())
    else: # 如果没有元素在屏幕上，输出 -
        print('-')

总结

Codeforces 704A (队列模拟) Thor 是一道经典的算法题目，通过这道题目的练习，我们不仅可以学习队列和集合等数据结构的使用，还可以提高自己的编程技能。希望本文能帮助大家更好地了解这道经典算法题目。