https://emre.me/data-structures/stacks-and-queues/
Intro
Stack is an ADT that represents an ordered collection of items where the addition of new items and removal of existing items takes place at the same end
LIFO (last-in first-out)
Usage
reverse the order of items
undo/redo actions (Command Pattern) (e.g., web navigation)
nested or recursive function calls
Comparison
Advantages
Disadvantages
Problems
Corner Cases
Implementation
Stack can be implemented using a concrete data structure like a Linked List or a Dynamic Array
| Time Complexity | ||
|---|---|---|
| Operations | Worst case | |
| Stack as Dynamic Array | Stack as Linked List | |
| Top is index 0 | Top is head | |
| push() | O(n) |
O(1) |
| pop() | O(n) |
O(1) |
| peek()/top() | O(1) |
O(1) |
| isEmpty() | O(1) |
O(1) |
| search() | O(n) |
O(n) |
| Top is index n-1 | Top is tail | |
| push() | O(1) |
O(1) |
| pop() | O(1) |
O(n) |
| peek()/top() | O(1) |
O(1) |
| isEmpty() | O(1) |
O(1) |
| search() | O(n) |
O(n) |
| Space Complexity | |
|---|---|
| Implementation | Worst case |
| Stack as Dynamic Array | O(n) |
| Stack as Linked List | O(n) |
n is the number of elements in the stack
Algorithms
Depth-First Search
Patterns
Code
class DynamicArrayStack(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def top(self):
if self.isEmpty():
return None
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedStack:
def __init__(self):
self.head = None
def isEmpty(self):
if self.head == None:
return True
return False
def push(self, data):
if self.head == None:
self.head = Node(data)
newnode = Node(data)
newnode.next = self.head
self.head = newnode
def pop(self):
if self.isEmpty():
return None
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
def peek(self):
if self.isEmpty():
return None
return self.head.data
Resources