I Can Guess the Data Structure!
There is a bag-type data structure, supporting two operations:
1 x
Throw an element x into the bag.
two
Take an element out of the bag.
Given a sequence of operations that return values, you will guess the data structure. It's a stack (last-in, first-out), a queue (first-in, first-out), a priority queue (always take out the big elements first) or anything else you can hardly imagine!
Input
There are many test cases. Each test case starts with the line counting a single integer n (1 <= n <= 1000). Each of the following n lines is a command of type 1, or an integer 2, followed by an integer x. This means that after executing a command of type 2, we get an element x without errors. The value of x is always an integer, positive and not greater than 100. The end of the input is determined by the end of file (EOF). Input file size does not exceed 1MB.
Exit
For each test case, show one of the following:
stack
It's definitely a stack.
queue
It's definitely a queue.
priority queue
It's definitely a priority queue.
impossible
It cannot be a stack, a queue or a priority queue.
not sure
It can be more than one of the three structures mentioned above.
while True:
try:
x = int(input())
except:
break
ts=0
s = []
q = []
pq = []
stack=1
queue=1
prioriq=1
for _ in range(x):
opc, n = input().split()
if int(opc) == 1:
s.append(int(n))
ts+=1
q.append(int(n))
pq.append(int(n))
pq.sort(reverse=True)
else:
if s[ts-1] == int(n) and stack == 1:
ts-=1
del s[ts]
else: stack=0
if q[0] == int(n) and queue == 1: del q[0]
else: queue=0
if pq[0] == int(n) and prioriq == 1: del pq[0]
else: prioriq=0
if (stack == 1 and queue == 1) or (stack == 1 and prioriq == 1) or (queue == 1 and prioriq == 1): print("not sure")
elif stack: print("stack")
elif queue: print("queue")
elif prioriq: print("priority queue")
else: print("impossible")