Stack, queue and list comprehensions

Part of the free LogicWiz Python course, Module 5: Lists and tuples. The examples and practice run in the app.

Shankar bhaiya stacks clean plates: the last plate washed is the first one used. At the counter it is the opposite: first in line, first served. Both are just lists used in a disciplined way.

You'll learn to

• Use a list as a stack (push with append, pop from the end)
• Use a list or deque as a queue (first in, first out)
• Write list comprehensions like `[x * x for x in nums if x > 0]`

Learn

Stack: last in, first out (LIFO)

A stack adds and removes at one end only, the top.

• Push (put on top): stack.append(x)
• Pop (take from top): stack.pop() removes and returns the last item
• Peek (look at the top): stack[-1]
• Empty? len(stack) == 0, or simply if not stack:

Popping an empty stack is called underflow. On a list it raises IndexError, so check first. Stacks power the undo button, the browser back button and the call stack of functions.

The plate stack

plates = []
plates.append("plate 1")
plates.append("plate 2")
plates.append("plate 3")
print(plates[-1])
top = plates.pop()
print(top, plates)

CBSE style: push and pop functions

def push(stack, item):
    stack.append(item)

def pop_item(stack):
    if len(stack) == 0:
        return "Underflow"
    return stack.pop()

books = []
push(books, "Maths")
push(books, "Physics")
print(pop_item(books))
print(pop_item(books))
print(pop_item(books))

The third pop finds the stack empty and reports "Underflow" instead of crashing.

Queue: first in, first out (FIFO)

A queue adds at the rear and removes from the front, like the canteen line.

• Enqueue (join the line): queue.append(x)
• Dequeue (serve the front): queue.pop(0)

pop(0) has to shift every other item one place left, which is slow for a long line. Python's collections.deque has popleft(), which is fast at both ends. For small lists in exams, pop(0) is fine.

The canteen line

from collections import deque

line = ["Aarav", "Meher"]
line.append("Riya")
print(line.pop(0), "is served")
print(line)

tokens = deque([101, 102])
tokens.append(103)
print(tokens.popleft(), list(tokens))

List comprehensions

A comprehension builds a list in one line:

[expression for item in list if condition]

Read it as: "the expression, for each item, if the condition holds." The if part is optional. It does exactly what this loop does:

result = []
for item in list:
    if condition:
        result.append(expression)

Use it when you are making a new list from an old one: squares, filtered marks, prices with GST.

Loop vs comprehension

nums = [-2, 3, -1, 4]
squares = []
for x in nums:
    if x > 0:
        squares.append(x * x)
print(squares)

print([x * x for x in nums if x > 0])
names = ["aarav", "meher"]
print([n.title() for n in names])
print([p + 5 for p in [20, 15, 40]])

CBSE Class 12 asks a 3-mark stack question almost every year: "Write Push(Arr) to push the numbers divisible by 5 from a list onto a stack, and Pop() to pop and display them; print 'Underflow' / 'Stack empty' when nothing is left." Use append for push, pop() for pop, and always check for empty first.

Two slips: stack.pop(0) takes from the bottom (that's a queue, not a stack), and if stack == None: never catches an empty stack, because an empty list is [], not None. Use if not stack: or len(stack) == 0.

In one line

Stack: append + pop() (LIFO); queue: append + pop(0) or deque.popleft() (FIFO); [f(x) for x in xs if cond] builds a new list.