Data Structure: Stack — Notes

A data structure is a way of organising data so it can be used efficiently (list, dictionary, stack, queue).

A stack is a linear structure with one open end, the top. Items are added (push) and removed (pop) only at the top, so the item added last is removed first: LIFO, Last In First Out. Everyday examples: a pile of plates or books, bangles on a wrist, the undo history of an editor.

The end of the list is the top. Standard functions:

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

def pop(stk):
    if stk == []:
        return "Underflow"
    return stk.pop()

def peek(stk):
    if stk == []:
        return None
    return stk[-1]

def is_empty(stk):
    return stk == []

Running push twice and pop three times on a list of books gives Diary Diary Atlas Underflow: the third pop reports underflow.

Underflow: pop or peek on an empty stack. With a list, pop() on [] stops the program with IndexError: pop from empty list, so test if stk == []: first and report "Underflow" (then return, so the pop line is not reached).

Overflow: push on a full stack of fixed capacity, tested with len(stk) == capacity. A Python list grows as needed, so overflow does not occur in normal list programs; it matters when a size limit is set (a tray holder for four trays, the last 20 messages).

Display from the top down by counting the index down:

def display(stk):
    if stk == []:
        print("Stack is empty")
    else:
        for i in range(len(stk) - 1, -1, -1):
            print(stk[i])

For [3, 8, 5] it prints 5, 8 and 3 on separate lines.

Tracing: write the stack as a list with the top on the right; push adds on the right, pop removes the rightmost item and returns it. Popped items always come out in reverse order of their pushes.

• Reversing text, a list or the digits of a number: push all, pop all.
• Bracket matching: push opening brackets; for a closing one pop and compare; the stack must be empty at the end.
• Function calls: Python keeps active calls on a call stack; the latest call returns first.
• Undo and back buttons: push each action or page; undo or back pops the latest.
• Postfix evaluation: push numbers; an operator pops the right operand, then the left, and pushes the result. 4 5 + 2 * evaluates to 18.
• Decimal to binary: push remainders of division by 2; popping gives the binary digits (11 gives 1011).

A typical question gives a list or dictionary and asks for two functions:

1. push: loop over the data, test the stated condition, and append the items (or keys) that pass.
2. pop: loop while the stack is not empty, pop and display each item, then print the message asked for (such as "Stack Empty").

def push_cities(towns, stk):
    for name, pin in towns.items():
        if pin % 2 == 1 and len(name) > 4:
            stk.append(name)

def pop_cities(stk):
    while stk != []:
        print(stk.pop(), end=" ")
    print("| None left")

towns = {"Shimla": 171001, "Ooty": 643001, "Kohima": 797002, "Madurai": 625003, "Bhuj": 370001}
S = []
push_cities(towns, S)
print(S)
pop_cities(S)

Output:

['Shimla', 'Madurai']
Madurai Shimla | None left