Python Data Structure — Stack

A stack is a useful data structure in programming. It is just like a pile of books kept on top of each other.

Image: codingtutorial4u

Think about the things you can do with such a pile of plates

• Put a new plate on top
• Remove the top plate

If you want the plate at the bottom, you must first remove all the plates on top. Such an arrangement is called Last In First Out — the last item that is the first item to go out.

Image: Programiz/dsa

Basic Operations of Stack

A stack is an object (an abstract data type — ADT) that allows the following operations:

• Push: Add an element to the top of a stack
• Pop: Remove an element from the top of a stack
• IsEmpty: Check if the stack is empty
• GetStack: Returns the entire stack
• Peek: Get the value of the top element without removing it

Stack Implementations in Python

Image: Atom/AshwinPC

Stack Time Complexity

For the array-based implementation of a stack, the push and pop operations take constant time, i.e. O(1)

Applications of Stack Data Structure

Although stack is a simple data structure to implement, it is very powerful. The most common uses of a stack are:

• To reverse a word — Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
• In compilers — Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.
• In browsers — The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed.