Writing the Stack Functions

1The five functions

def isEmpty(stack):
    if len(stack) == 0:
        return True
    else:
        return False

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

def pop(stack):
    if isEmpty(stack):
        print('Underflow')
        return None
    else:
        return stack.pop()

def peek(stack):
    if isEmpty(stack):
        print('Stack is empty')
        return None
    else:
        return stack[-1]

def display(stack):
    if isEmpty(stack):
        print('Stack is empty')
    else:
        for i in range(len(stack) - 1, -1, -1):
            print(stack[i])

marks = []
push(marks, 78)
push(marks, 91)
push(marks, 65)
display(marks)
print('top    :', peek(marks))
print('popped :', pop(marks))
print('now    :', marks)

65
91
78
top    : 65
popped : 65
now    : [78, 91]

2Why push() needs no return

push() ends without a return, and yet the caller's list grows:

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

s = []
push(s, 5)
push(s, 8)
print(s)

[5, 8]

When push(s, 5) runs, the parameter stack is not a copy of s. It is a second name for the same list. append() changes that one list, so the change is there when the function ends.

Now write the push the tempting way, with a new list:

def push(stack, item):
    stack = stack + [item]

s = []
push(s, 5)
push(s, 8)
print(s)

[]

Nothing was pushed. stack + [item] builds a brand-new list, and stack = moves only the function's own name onto it. The caller's list is never touched, and the new list is thrown away when the function ends. There is no error to warn you.

3When the stack is a global list

Many board questions do not pass the stack in at all. They name it — “a stack named status” — and ask for Push_element() with empty brackets. Then the list is made at the top of the program and the function uses it by name:

names = ['Ravi', 'Meera', 'Amit']
status = []

def Push_element():
    for n in names:
        status.append(n)

Push_element()
print(status)

['Ravi', 'Meera', 'Amit']

No global statement is needed. status.append(n) only reads the name status to find the list, then changes the list. It never assigns to the name. Assign to it, and the function breaks:

names = ['Ravi', 'Meera', 'Amit']
status = []

def Push_element():
    for n in names:
        status = status + [n]

Push_element()
print(status)

Traceback (most recent call last):
  File "global_trap.py", line 8, in <module>
    Push_element()
  File "global_trap.py", line 6, in Push_element
    status = status + [n]
             ^^^^^^
UnboundLocalError: cannot access local variable 'status' where it is not associated with a value

Because status = appears inside the function, Python treats status as a local name for the whole function — and the local one has no value yet when the right-hand side tries to read it. That is the UnboundLocalError from the scope lesson, and append() avoids it completely.

4Underflow: the message is printed, the None is returned

The board's wording is usually “pop the topmost item and return it; if the stack is empty, display Underflow”. Follow that exactly, and see what the caller gets:

def pop(stack):
    if len(stack) == 0:
        print('Underflow')
    else:
        return stack.pop()

s = [10]
print(pop(s))
print(pop(s))

10
Underflow
None

The second call prints Underflow itself, then ends without returning anything — so it hands back None, and the print() around the call prints that. Nothing is wrong. The question asked for a message and a value, and those are two separate things. Writing return None yourself, as in section 1, just makes the second one visible.

5Displaying a stack: top first, and without popping

stack = [78, 91, 65]

print('for item in stack:')
for item in stack:
    print(item)

print('top first, by position:')
for i in range(len(stack) - 1, -1, -1):
    print(stack[i])

print('top first, with a slice:')
for item in stack[::-1]:
    print(item)

for item in stack:
78
91
65
top first, by position:
65
91
78
top first, with a slice:
65
91
78

for item in stack walks the list from position 0, which is the bottom. The other two start from the top. Both are correct; the slice stack[::-1] makes a reversed copy and leaves the stack alone.

One more way looks right and is not:

stack = [78, 91, 65]

while len(stack) > 0:
    print(stack.pop())

print('after displaying:', stack)

65
91
78
after displaying: []

6Try it

def isEmpty(stack):
    return len(stack) == 0

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

def pop(stack):
    if isEmpty(stack):
        print('Underflow')
        return None
    return stack.pop()

def display(stack):
    for i in range(len(stack) - 1, -1, -1):
        print(stack[i])

books = []
push(books, 'Godan')
push(books, 'Gitanjali')
push(books, 'Malgudi Days')
display(books)
print('popped:', pop(books))
print('popped:', pop(books))
print('popped:', pop(books))
print('popped:', pop(books))

This version of isEmpty() is one line: len(stack) == 0 is already True or False, so it can be returned directly. Both versions do the same job.

7Recap