KarChunTStack
What is Stack?
Stack is a Last In First Out (LIFO) data structure, meaning that the last element added will be the first element to be removed.
Stack can be implemented using arrays or linked lists.
Key operations of a stack include:
- Push: Add an element to the top of the stack.
- Pop: Remove and return the top element of the stack.
- Peek: Return the top element without removing it.
| Operation | Big-O Time |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek / Top | O(1) |
Real-World Applications of Stack
- Undo/Redo functionality in text editors
- Browser history
- Recursion
Advantages and Disadvantages of Stack
Advantages:
- Simple to implement and use, with O(1) time complexity for push and pop operations
- Efficient for certain algorithms (e.g., depth-first search)
- Useful for specific applications like recursion, expression evaluation, and backtracking
Disadvantages:
- Limited access to elements (only the top element is accessible)
- Fixed size if implemented using arrays (unless using dynamic arrays)
- Not suitable for random access of elements
- Can lead to underflow if popping from an empty stack
Stack Class Implementation
class Stack:
def __init__(self) -> None:
self.items = []
def __len__(self) -> int:
return len(self.items)
def __str__(self) -> str:
return str(self.items)
def is_empty(self) -> bool:
return len(self.items) == 0
def push(self, item: int) -> None:
self.items.append(item)
def pop(self) -> int:
if self.is_empty():
raise IndexError("Stack Underflow: Cannot pop from an empty stack")
return self.items.pop()
def peek(self) -> int:
if self.is_empty():
raise IndexError("Stack Underflow: Cannot pop from an empty stack")
return self.items[-1]
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(len(stack))
print(stack)
print(stack.pop())
print(stack.peek())
print(stack)class Stack:
def __init__(self) -> None:
self.items = []
self.top = -1 # Index of the top element; -1 indicates an empty stack
def __len__(self) -> int:
return self.top + 1
def __str__(self) -> str:
return str(self.items[:self.top + 1])
def is_empty(self) -> bool:
return self.top == -1
def push(self, item: int) -> None:
self.top += 1
self.items += [item] # manually extend the list
def pop(self) -> int:
if self.is_empty():
raise IndexError("Stack Underflow: Cannot pop from an empty stack")
item = self.items[self.top]
self.top -= 1
return item
def peek(self) -> int:
if self.is_empty():
raise IndexError("Stack Underflow: Cannot pop from an empty stack")
return self.items[self.top]
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(len(stack))
print(stack)
print(stack.pop())
print(stack.peek())
print(stack)class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.top = None
self.size = 0
def __len__(self) -> int:
return self.size
def __str__(self) -> str:
result = []
current = self.top
while current:
result.append(current.value)
current = current.next
return str(result)
def is_empty(self) -> bool:
return self.size == 0
def push(self, item: int) -> None:
new_node = Node(item)
new_node.next = self.top
self.top = new_node
self.size += 1
def pop(self) -> int:
if self.is_empty():
raise IndexError("Stack Underflow: Cannot pop from an empty stack")
popped_value = self.top.value
self.top = self.top.next
self.size -= 1
return popped_value
def peek(self) -> int:
if self.is_empty():
raise IndexError("Stack Underflow: Cannot pop from an empty stack")
return self.top.value
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(len(stack))
print(stack)
print(stack.pop())
print(stack.peek())
print(stack)Stack Visualization
Stack Visualization
Top → 0x5008
0x5000
42
0x5004
17
0x5008
89
← TOP
Stack Size: 3 |PeekPushPop
Animation Controls
Stack Operations
Last updated on