AI Hints
Home›DSA in Python Tutorial›Stacks and Queues
DSA in Python · Lesson 31 of 132

Stacks

Last in, first out.

⏱ 2 min read▶ Video at 35:59🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A stack is like a pile of plates. You put a plate on top, and you take a plate from the top. The last one in is the first one out. Your browser's back button, and undo in an editor, both work like a stack.

Stacks
From the video: Stacks
  • A pile of plates
  • Last in, first out
  • Back button, undo

A list as a stack

A Python list makes a perfect stack. Append pushes onto the top, and pop removes from the top. Both are O of one, because they work at the end of the list. The last item, at index minus one, lets you peek without removing. Run it. The pages come back in reverse order, just like pressing back.

stack.pypython
history = []
history.append("home")
history.append("search")
history.append("product")
print("top:", history[-1])

while history:
    print("back to", history.pop())
Output
top: product
back to product
back to search
back to home

Stack operations

Every stack has the same small set of operations. Push adds to the top. Pop removes the top. Peek looks at the top. And is empty checks whether anything is left. All of them are O of one. Never add or remove from the front of a list for a stack, because that's O of N.

keyvalue
pushappend(x)
poppop()
peekstack[-1]
is emptynot stack

Summary

A stack is last in, first out. With a Python list, append and pop at the end are both O of one. Next, a classic stack problem. Balanced brackets.

Key takeaways
  • Last in, first out
  • append / pop
  • Undo and back buttons
Next up: Practice: Balanced Brackets — every opener has a closer