Stack and queue

A data structure is a way of storing data and performing operations on it. One of the simplest is the stack, which works on the “last in, first out” principle (LIFO). It can be compared to a pile of plates: you put a new plate on top and take only the top one. The main operations are push (add to the top), pop (remove the top element) and peek (look without removing).

A queue works on the “first in, first out” principle (FIFO), just like a line in a shop: a newcomer joins at the end, and service starts with the person at the front. The main operations are enqueue (add to the end) and dequeue (take from the front).

In Python a stack can be built from an ordinary list: s.append(x) adds an element on top, and s.pop() returns the top element and removes it. For a queue, deque from the collections module is convenient: q.append(x) adds to the end and q.popleft() takes from the front. It is better not to use a.pop(0) on an ordinary list for a queue, because it shifts all the remaining elements and is slow on large lists.

Stacks are everywhere: the browser’s “Back” button, undo in a text editor (Ctrl+Z), the order of function calls (including recursion) and checking that brackets in an expression are balanced. Queues are used for documents sent to a printer, network packets and the order in which an operating system runs processes.

Key takeaways

• A stack works as LIFO: the last element added is the first one taken out.
• A queue works as FIFO: the first element added is the first one taken out.
• Stack operations are push, pop and peek; queue operations are enqueue and dequeue.
• In Python a stack is conveniently built on a list and a queue on collections.deque.
• Stacks are used for undo and bracket checking, queues for running tasks in order.