Queue in Programming: First In, First Out With a Game Map

What is a queue in programming? It is a list where the first item you put in is the first item you take out. Think of people in a line at a shop: whoever joined first is served first. This post shows how a queue works, how it differs from a stack, how to use one in Python and C#, and where a tank game's code uses one to check its maps.

Tank City Reboot has two free tank games set inside a computer that play in your browser with no account, and its map checker is a queue at work.

What is a queue in programming?

A queue is a data structure that keeps items in the order they arrived. It supports two main operations. Enqueue adds an item to the back. Dequeue removes the item at the front and hands it to you.

Wikipedia calls this a first-in-first-out data structure, or FIFO: the first element added is the first one removed. Once a new item joins, everything that was already waiting has to leave before it can.

Most queues also offer peek, which shows you the front item without removing it. That is all a queue does. It never lets you reach into the middle.

Why the order matters

You use a queue when fairness or order is the point. Work that arrives first should be done first. A few places queues turn up:

• A print job list, where documents print in the order they were sent.
• A buffer, which holds data that arrives faster than it can be handled. Wikipedia lists this as a main use.
• Breadth-first search, which explores a map one ring of steps at a time.
• A chat or task system where messages wait their turn.

Queue vs stack

A stack is the opposite shape. It is last in, first out, like a pile of plates: you take the plate you put on last. Python's tutorial shows a list used as a stack with append to push and pop to take the top item.

• Queue: add at the back, remove from the front. The oldest item leaves first.
• Stack: add on top, remove from the top. The newest item leaves first.

Pick a queue when you want things handled in the order they came. Pick a stack when you want to undo the latest step first, like an undo button.

Queues in Python and C#

Python

You can use a plain list as a queue, but Python's tutorial warns that lists are not efficient for it. Adding or removing at the end of a list is fast. Doing it at the start is slow, because every other item has to shift by one place.

The tutorial's advice is to use collections.deque, which is built for fast appends and pops from both ends.

• from collections import deque loads it.
• line = deque(["Eric", "John"]) makes a queue with two people in it.
• line.append("Terry") enqueues Terry at the back.
• line.popleft() dequeues the front, which returns "Eric".

C#

Tank City Reboot and Tank City Zero Day are written in C#, which has a ready-made queue. Microsoft's reference describes Queue<T> as a first-in, first-out collection of objects. Its methods have the names you now know: Enqueue, Dequeue and Peek.

The type in the angle brackets says what the queue holds. A Queue<string> holds words. A queue of row and column pairs holds tuples, which brings us to the game.

A worked example: checking a game map

Here is a small job a queue is good at. You have a grid with walls, a start square and a goal, and you want to know if the goal can be reached. Try it on paper:

1. Write the start square on a list. This is your queue.
2. Take the front square off the list.
3. Look at its four neighbours: up, down, left, right. Skip walls and squares you have already seen.
4. Write each new neighbour at the back of the list, and mark it seen.
5. Repeat from step 2. If you reach the goal, it can be reached. If the list empties first, it cannot.

Because squares leave in the order they joined, you explore all squares one step away, then all squares two steps away, and so on. That ring-by-ring order is exactly what breadth-first search is.

The queue inside Tank City Zero Day

Tank City Zero Day draws a fresh arena for every wave: 13 rows of 13 tiles, with the three enemy gates on the top row at columns 0, 6 and 12. Before it accepts one, a check called Arena.Fair asks whether a tank starting beside the core can reach all three gates, going round silicon and coolant. If it cannot, the arena is drawn again.

From the game's code, that check is the paper method above. It keeps a queue of (int r, int c) pairs, row and column. It starts with the tiles beside the core and then repeats a simple loop. It takes one pair off the front with var (r, c) = queue.Dequeue();, tries the four neighbours using the steps (1, 0), (-1, 0), (0, 1) and (0, -1), and queues the open ones it has not seen. If all three gates get reached, the arena is fair.

A queue fits because the order is natural: the tiles found first are explored first, so no tile is forgotten and none is visited twice.

A queue that is not plain

The enemy tanks' route search looks like it could be the same thing, but it is not. Its waiting cells sit in a SortedSet of (distance, cell) pairs, because a step onto firewall costs 4 while an ordinary step costs 1. When steps cost different amounts, the cell with the smallest distance should leave first, not the one that joined first. That is a priority queue. The fairness check treats every step the same, so a plain queue is enough there.

Common mistakes

• Using a list and removing from the front. In Python it works but gets slow as the list grows. Use deque.
• Dequeuing from an empty queue. It raises an error, so check that the queue has items first.
• Forgetting to mark squares as seen. The same square gets queued again and again, and a search on a loop never ends.
• Mixing up queue and stack. Taking from the back instead of the front changes the order of exploration entirely.

Frequently asked questions

What does FIFO mean?

It stands for first in, first out. The first item added to the queue is the first one removed.

What is the difference between a queue and a stack?

A queue removes the oldest item first. A stack removes the newest item first.

What is the difference between enqueue and dequeue?

Enqueue adds an item to the back of the queue. Dequeue removes the item at the front and returns it.

Is a queue the same as a list?

No. A list lets you read or change any position. A queue only lets you add at the back and take from the front.

Get started

A queue makes the most sense when you watch it work on a map. Tank City Reboot is free to play in your browser on a computer or a phone, and its stages are 13 by 13 tile maps.

1. Play one stage and find where the enemies enter along the top and where your core sits.
2. Copy the stage layout onto squared paper.
3. Run the paper method from above: start beside the core, queue each open neighbour, and count how many steps it takes to reach each gate.
4. Write the same loop in Python with deque.

Then open Tank City Zero Day, where every wave gets a new arena, and imagine the fairness check queueing tiles behind the scenes.