Back
Close
  • 17

What will I learn?

QueueStackPriority Queue

Statement

 Goal

There is a mysterious data structure. This structure is like a bag which allows putting data in and taking data out. But it is a magic bag that sometimes behaves in ways you can hardly imagine. You have to guess, as far as possible, what structure it is by looking at its behaviors.

To keep it simple, we limit our analysis to only three known data structures:
Queue (First In First Out)
Stack (First In Last Out)
Priority Queue (Bigger data come out first)

We use only two operators to try out the structure:
i - input data, similar to [add, put, push, insert, ...]
o - output data, similar to [pop, poll, pull, delete, ...]

The data are simple integers.

At the beginning, the data structure is empty. A sequence of i/o operations is then done on the structure. Analyze the result then tell what data structure it is.
Input
There are multiple data structures and operation sequences in each test case.

Line 1: An integer N for the number of operation sequences for your analysis.
Next N lines: each line represents one data structure and a sequence of operations carried out on it.
» Operations are space separated.
» Each operation starts with a character i or o, followed by an integer

For example,
i2 means input 2 into the structure
o2 means asking the structure to output a data, and we got 2 as the output.

Important for your analysis - we got NO ERROR in all the operations.
Output
Output N lines, corresponding to the inputs.
Each line shall be one of the options in the "answer" column below.

┌────────────────┬───────────────────────────────────────────────────┐
│ answer │ meaning │
├────────────────┼───────────────────────────────────────────────────┤
│ queue │ it is a Queue │
│ stack │ it is a Stack │
│ priority queue │ it is a Priority Queue (bigger data has priority) │
│ unsure │ it can be two or more of the above options │
│ mystery │ it belongs to none of the above options │
└────────────────┴───────────────────────────────────────────────────┘
Constraints
1 ≤ N ≤ 100
0 ≤ value of data in each operation < 10
0 < number of operations in a sequence ≤ 100
Example
Input
5
i1 i2 i3 o1 o2 o3
i3 i2 i1 o1 o2 o3
i2 i1 i3 i1 o3 o2
i1 i1 i1 o1 o1 o1
i1 o2
Output
queue
stack
priority queue
unsure
mystery
Solve it

A higher resolution is required to access the IDE

codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants