Stack

Stack is just like a pile of books. The last book you put on the pile is the first one you can take off. This is called LIFO (Last In First Out).

Push

To put something on the stack, you use the push method. The item will be added to the top of the stack.

Pop

To take something off the stack, you use the pop method. The item will be removed from the top of the stack.

High Level Implementation

In Python, we can use:

LifoQueue from queue module -> Thread-safe
deque from collections module -> Not thread-safe but faster

Use Cases

Function Call

Function call is a good example of using stack. When a function is called, the program will push the function call to the stack. When the function returns, the program will pop the function call from the stack.

Source: https://nobelsharanyan.wordpress.com/2015/05/17/function-call-stack-implementation/

Source: https://eecs280staff.github.io/notes/02_ProceduralAbstraction_Testing.html

String Reversal

To reverse a string, we can use stack. We push each character of the string to the stack. Then we pop each character from the stack and append it to a new string.

from collections import deque
def reverse(s):
    stack = deque()
    for c in s:
        stack.append(c)
    s = ""
    while len(stack) > 0:
        s += stack.pop()
    return s
print(reverse("hello"))

olleh

Well, it’s obvious that we can just use string[::-1] to reverse a string. But this is just an example of using stack.

Palindrome Checker

Palindrom is a word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.

Example of palindrom in Indonesian: kasur rusak, malam, dan radar.

from collections import deque
def is_palindrom(s):
    stack = deque()
    for c in s:
        stack.append(c)
    for c in s:
        if c != stack.pop():
            return False
    return True

print(is_palindrom('abcba'))
print(is_palindrom('abccba'))
print(is_palindrom('abccbaa'))

True
True
False

Balanced Parentheses Checker

Given the string of parentheses, check if the parentheses are balanced. e.g. - ((())) -> Balanced - (()()) -> Balanced - (() -> Not balanced - (())) -> Not balanced

We can just add the opening parentheses to the stack. When we encounter a closing parentheses, we pop the stack. If the closing parentheses doesn’t match the opening parentheses, then the parentheses are not balanced.

def is_balanced(s):
    stack = deque()
    for c in s:
        if c == '(':
            stack.append(c)
        elif c == ')':
            if len(stack) == 0:
                # no matching
                return False
            stack.pop()
    # if there is no more '(' in stack, then it is balanced
    return len(stack) == 0

print(is_balanced('((()))'))
print(is_balanced('(()))'))
print(is_balanced('(()(()))'))

True
False
True

Well, it’s an overkill to use stack for this problem. We can just use a counter to count the opening and closing parentheses. If the counter is negative, then the parentheses are not balanced.

def is_balanced(s):
    # using counter
    counter = 0
    for c in s:
        if c == '(':
            counter += 1
        elif c == ')':
            counter -= 1
            if counter < 0:
                return False
    return True
            
print(is_balanced('((()))'))
print(is_balanced('(()))'))
print(is_balanced('(()(()))'))

True
False
True

But, if there are many types of parentheses, then we need to use stack.

def is_balanced(s):
    stack = deque()
    pairs = {'(': ')', '[': ']', '{': '}'}
    for c in s:
        # c can be [{(
        if c in '([{':
            stack.append(c)
        elif c in ')]}':
            if len(stack) == 0:
                return False
            if pairs[stack.pop()] != c:
                return False
    return len(stack) == 0

print(is_balanced('((()))'))
print(is_balanced('(()))'))
print(is_balanced('(()(()))'))

print(is_balanced('([{}])'))
print(is_balanced('([{}]))'))
print(is_balanced('([{(})])'))

True
False
True
True
False
False

Undo Mechanism

When you type something in a text editor, the text editor will push the text to the stack. When you undo, the text editor will pop the text from the stack.

class Keyboard:
    def __init__(self):
        self.stack = deque()
    def type(self, c):
        if c == '<':
            if len(self.stack) > 0:
                self.stack.pop()
        else:
            self.stack.append(c)
    def get(self):
        return ''.join(self.stack)

keyboard = Keyboard()
keyboard.type('a')
keyboard.type('b')
keyboard.type('c')
print(keyboard.get())
keyboard.type('<')
print(keyboard.get())
keyboard.type('d')
print(keyboard.get())
keyboard.type('<')
print(keyboard.get())

abc
ab
abd
ab

Recursion

Recursion is a good example of using stack. When a function calls itself, the program will push the function call to the stack. When the function returns, the program will pop the function call from the stack.

def fibonacci(n):
    if n <= 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(1))
print(fibonacci(4))

1
3

Let’s reimplement the fibonacci method using stack

def fibonacci(n):
    stack = deque()
    stack.append(n)
    sum = 0
    while len(stack) > 0:
        n = stack.pop()
        if n <= 2:
            sum += 1
        else:
            stack.append(n - 1)
            stack.append(n - 2)
    return sum

print(fibonacci(1))
print(fibonacci(4))

1
3

Well, both are not efficient (there are many recalculations). But hopefully you get the idea.