DSA Stack

Stack Data Structure

After Arrays and Linked Lists, the Stack is one of the easiest and most useful data structures to learn.

You actually use Stacks every single day without realizing it. Let's look at how they work!

1. What is a Stack?

A Stack is exactly what it sounds like.

Think of a stack of dirty plates in your sink. When you add a new plate, you place it on the top of the stack. When you wash a plate, you take it off the top of the stack.

You cannot easily pull a plate from the bottom without the whole stack crashing down!

Real-Life Examples of Stacks:

• The "Undo" button in your text editor (reverses the last action you took).
• Your web browser's "Back" button (takes you to the last page you visited).
• Your computer's Call Stack (manages function calls in programming).

2. Core Stack Operations

A proper Stack only allows you to interact with the Top element. It restricts access to the rest of the data.

Here are the standard terms used in DSA for Stack operations:

1. Push: Add a new element to the top of the stack.
2. Pop: Remove the top element from the stack and return it.
3. Peek (or Top): Look at the top element without removing it.
4. isEmpty: Check if the stack is completely empty.

3. Time Complexity of a Stack

Because a Stack restricts where you can add and remove data, it is incredibly fast.

• Push: O(1) Constant Time.
• Pop: O(1) Constant Time.
• Peek: O(1) Constant Time.
• Search: O(n) Linear Time. (You have to pop off elements one-by-one to find what you are looking for at the bottom).

4. Stack Code Example (Python)

In Python, you do not need to build a complex class to use a Stack. Python's built-in List (Array) already has append() and pop() methods that make it act exactly like a Stack!

# Create an empty stack
stack = []
# 1. PUSH elements onto the stack
print("Pushing elements...")
stack.append("A")
stack.append("B")
stack.append("C")
print("Current Stack:", stack)
# 2. PEEK at the top element
# We use index [-1] to look at the last item
top_element = stack[-1]
print("Top element is:", top_element)
# 3. POP elements off the stack
print("Popping element...")
removed_item = stack.pop()

print("Removed:", removed_item)
print("Stack after Pop:", stack)