Stack
Created : January 27, 2021
Written in Python.
- Linear data structure
- LIFO (Last In First Out)
- Insertion/Deletion: only on same end
-
Example
- stacked plates
- undo (Ctrl + z)
Basic Operations
-
push: Add an item.
- If the stack is full → Overflow condition
append(item)
-
pop: Remove an item.
- If the stack is empty → Underflow condition
pop()
- peek or top: Return top element of stack.
- isEmpty: Return true if stack is empty, else false.
- size: Return the size of the stack
Big-O Complexity for Stack
-
Time complexity
- Insertion/Deletion: O(1)
- Access/Search: O(n)
- Space complexity: O(n)
Implementation
# Create stack class
class Stack:
# Initialize
def __init__(self):
self.items = []
# Push an item to the end
def push(self, item):
self.items.append(item)
# Pop an item from the end
def pop(self):
# Check if stack is not empty
if not self.isEmpty():
return self.items.pop()
else:
print('Stack underflow')
exit()
# Return top element of stack
def peek(self):
# Check if stack is not empty
if not self.isEmpty():
return self.items[-1]
else:
print('Stack underflow')
exit()
# Check if stack is empty
def isEmpty(self):
return len(self.items) == 0
# Return size of stack
def size(self):
return len(self.items)