Stack

Intro

A stack is an Abstract Data Type that uses Last In, First Out (LIFO) operations. The last element added to the stack is the first to be removed, analogous to a stack of plates. Stacks are commonly implemented as arrays or singly linked lists.

A stack of plates

Applications

• Function call stack (recurusion)
• Depth-First Search- explicit stack or implicit via recursion

Core Operations

The below operations run in O(1) time

• push(item)- Add element to top of stack
• pop()- Remove element from top of stack
• peek()- Return the top element without removing it
• isEmpty()

Python Implementations

In Python, stacks can be created using lists or the collections module

Using Lists

https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks

stack = [] 
 
# Push to stack
stack.append(5)
stack.append(10)
stack.append(15)
 
# Pop from stack
print(stack.pop()) #15

Using collections.deque

from collections import deque
 
# Create empty stack
stack = deque()
 
# Push to stack
stack.append(10)
stack.append(20)
 
# Peek
print(stack[-1]) # 20
 
# isEmpty
print(len(stack) == 0) # False
 
# Pop from stack
print(stack.pop()) # 20

Stack Class

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