##

Last in, first out (LIFO)

Stacks can be made with arrays

Stacks can be visualized as a vertical/length structure and is best with DFS.

conversion from postfix to prefix:

  1. accept a postfix string
  2. start scanning the string from left to right one character at a time
  3. if it is an operand, push it in stack
  4. if it is an operator, pop operand1, operand2, and concat them in the order (operator, operand1, operand2), then push the result in the stack
  5. repeat these steps until array of input postfix string ends
  6. pop the remaining element of the stack, which is the required prefix notation equivalent to a given postfix notation

Basic Stack Code

class Stack:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return len(self.items) == 0
    
    def push(self, item):
        self.items.append(item)
        
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None
            
    def peek():
        if not self.is_empty():
            return self.items[-1]
        else:
            return None
    
    def size(self):
        return len(self.items)

Play around with it:

my_stack = Stack()
print(my_stack.is_empty())

Append will push to the end of the list (say, [1, 2, 3]) Pushing 4 will give you [1, 2, 3, 4]

Basically, elements added last (end of list) and the ones to be removed first

Runtime Complexity

lookup O() append insert delete

push pop peek size isFull isEmpty

Space Complexity

Exercises

  • Find the minimum element in a stack in O(1) time.
  • Write a function that sorts a stack.
  • Write a function that sorts a stack in place without extra memory.
  • Implement a queue using 2 stacks.