DSA Stacks
A stack is a collection where items leave in the reverse order they arrived. The last item pushed in is the first item popped out.
Push and pop on a list
append adds to the end of a list and pop removes from the end. The value 3 entered last and leaves first.
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)
print(stack.pop())
print(stack)Peek leaves the item
Reading the last element peeks at the top. The stack keeps the same items afterwards.
stack = [10, 20, 30]
print(stack[-1])
print(stack)A small stack class
A class wraps the list and names the operations. The calls below peek at the top, pop it and test whether the stack is empty.
class Stack:
def __init__(self):
self.items = []
def push(self, value):
self.items.append(value)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
stack = Stack()
stack.push("a")
stack.push("b")
print(stack.peek())
print(stack.pop())
print(stack.is_empty())Example
class Stack:
def __init__(self):
self.items = []
def push(self, value):
self.items.append(value)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
stack = Stack()
for value in (10, 20, 30):
stack.push(value)
print("push", value, "->", stack.items)
print("peek:", stack.peek())
print("pop:", stack.pop())
print("after pop:", stack.items)
stack.push(40)
print("push 40 ->", stack.items)
print("pop:", stack.pop())
print("pop:", stack.pop())
print("empty at the end:", stack.is_empty())Key points
- Push: add an item to the top of the stack
- Pop: remove and return the top item
- Peek: read the top item without removing it
- Last in, first out means the newest item always leaves first
- A stack is a list used only at its end, so push and pop each touch one item
In this example, a Stack class is driven through pushes, a peek and pops. The items print after each step. The peek reads 30 and removes nothing. The pops then return 30, 40 and 20, always the newest item still present. One item remains at the end, so is_empty reports False.
Note
Python lists already grow and shrink at the end, so a list alone can serve as a stack.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A stack pushes 1, then 2, then 3, and then pops twice. What comes out?