Stack

What is a stack? (LIFO)

A Stack is a data structure with two key functions push and pop. The push function will insert an item onto the top of the stack and a pop function will remove an item at the top of the stack.

Stacks operate on a Last In First Out basis meaning that the most recently pushed item will be the next one to be returned when popped.

This can be visualized as putting chips back into a Pringles can. When you need to take one out the last one in goes out first.

Another example is the browser back and forward button. Hitting the back arrow pops the most recently visited website off your history and returns it to the main screen.

Operation Stack State - Top of the Stack is on the right
Initialize Empty stack []
stack.push(1) [1]
stack.push(2) [1,2]
stack.push(2) [1,2]
stack.push(3) [1,2,3]
stack.pop() [1,2]: returns 3
stack.pop() [1]: returns 2
stack.push(4) [1,4]
stack.push(5) [1,4,5]
stack.pop() [1,4]: returns 5

Python list

The built in list data-type supports all stack operations. The only difference is that the .push() is called .append()

my_stack = []
my_stack.append(1)
my_stack.append(2)
my_stack.append(3)
my_stack.pop() #3
my_stack.pop() #2
my_stack.append(4)
my_stack.append(5)
my_stack.pop() #5

Implementing a stack in Python

Under the hood stacks are implemented using linked-lists in Python.

Top of the stack
self.head 5 self.head points to the top of the stack
self.head.next 4 When removing element from stack, set self.head = self.head.next
3
2
1

Stack class implementation, this uses a Python list under the hood.

class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def get_items(self):
        return self.items

    def is_empty(self):
        return self.items == []

    # Returns the top most element of the stack or last popped on item, this is
    # the last element on a list.
    def peek(self):
        if not self.is_empty():
            return self.items[-1]


if __name__ == "__main__":
    s1 = Stack()
    s1.push("a")
    s1.push("b")
    s1.push("c")
    print("peeking", s1.peek())
    s1.pop()
    print(s1.get_items())
    print(s1.is_empty())

Time Complexity

Pop - O(1)
Push - O(1)
Top/peek - O(1)