Skip to main content

Stack

  • LIFO (last in first out) data structure
  • Underflow: pop or peek on empty stack
  • Overflow: push on a full stack
  • Applications: recursive function calls; balanced parenthesis; undo/redo

List implementation​

s = []
s.append(10) # push
s.pop() # pop
s[-1] # peek
len(s) # size

Deque implementation​

from collections import deque
s = deque()
s.append(10) # push
s.pop() # pop
s[-1] # peek
len(s) # size
tip

Use deque for stack; better performance (uses doubly linked list)

note

python also has LIFO queue; but its used in multithreading

from queue import LifoQueue

Linked List implementation​

class Stack:
    def __init__(self):
        self.head = None
        self.len = 0
    
    def push(self, x):
        # insert at beginning and increment size
    
    def pop(self):
        # check empty; delete beginning and decrement size
        
    def peek(self):
        # check empty; return head value