Queues

Preserve arrival order

A queue processes the oldest waiting item first. Adding an item places it at the back. Removing an item takes it from the front. This is first-in, first-out order. A line of customers is a useful model because a later arrival must not jump ahead of earlier arrivals.

Separate the stored items from the facts you need to report. One problem asks which items remain. Another asks how many items are waiting after every event. Another asks for the largest queue size ever reached. The same queue operations support all three questions, but the recorded result differs.

A complete example

This example records the largest number of jobs waiting during a sequence of arrivals and removals.

from collections import deque

waiting = deque()
largest = 0
events = [("add", 8), ("add", 3), ("remove", 0), ("add", 5)]

for action, value in events:
    if action == "add":
        waiting.append(value)
    else:
        waiting.popleft()
    largest = max(largest, len(waiting))

print(list(waiting))
print(largest)

[3, 5]
2

The states are [8], [8, 3], [3], and [3, 5]. The oldest value, 8, leaves first. The largest size is two even though the queue changes four times.

deque supports adding at the back and removing at the front efficiently. Each of these operations is O(1). Processing n events is O(n), and storing the waiting items takes O(n) space in the worst case.

A queue with a list

You can represent a queue using a list and a front index. Append every arrival. To remove the first waiting item, increase the index. The waiting values are the list entries at or after that index. The size is len(values) - front.

Calling pop(0) on a Python list moves the remaining entries and takes linear time. Repeating it can make the total quadratic. The first exercise has small bounds, but understanding this cost matters before using the same code with a large input.

Reading operation lines

An operation line can have one token or two. Read it with parts = input().split(). Inspect parts[0] to decide whether a value exists in parts[1]. Do not attempt to unpack two values from a removal line containing only one.

Some exercises explicitly ask for queue.Queue. Its put method adds and get method removes. Use the required library in those exercises. queue.Queue is designed for coordination between threads, so deque is usually simpler for ordinary single-threaded contest code.

Boundaries and invariants

After each processed event, the queue must contain exactly the arrivals that have not yet been removed, in their original order. That invariant explains both removal correctness and the remaining-item output.

The listed exercises guarantee that removal never occurs on an empty queue. If a different statement lacks that guarantee, decide how empty removal must behave before calling popleft or get. Keep the maximum-size update after every event so the record includes each new state.

Practice

Start with the raw queue implementation, then count waiting customers, use the required library, and compute peak waiting size. The optional puzzle exercise practices representing a board and moving its empty square. It does not itself require queue search. Treat it as a state-representation extension, not evidence that a queue solves every puzzle.

Draw the queue for a small example and check every event against the drawing before submitting.