UVa 11995 - WinDaLex/Programming GitHub Wiki

I Can Guess the Data Structure!

from Chapter 3. Data Structures :: Fundamental Data Structures :: Examples

Problem

给你一个像“背包”一样的数据结构，支持两种操作：

• 1 x - 放入一个元素x到包中
• 2 (x) - 从包中拿出一个元素（取出的元素是x）

给出一个操作序列（含结果），请你猜猜这个包是以下哪种数据结构：

• stack（后进先出的栈）
• queue（先进先出的队列）
• priority queue（每次取出的元素都是最大值的优先队列）
• impossible（以上三种都不是）
• not sure（无法确定是以上哪一种情况）

Solution

利用STL中现成的stack、queue、priority_queue，判断取出来的元素与这三种数据结构是否一致即可。需要注意的是，有一个impossible的情况是，当前取元素的次数比拿元素的次数还多。这就要求在取元素之前应该判断数据结构是否为空，否则会发生运行错误。