Stack Concept and LIFO Principle in DSA Python

Mental Model

A stack is a collection where the last item added is the first one removed. This is called Last In, First Out (LIFO).

Analogy: Think of a stack of plates: you put new plates on top and take plates from the top only. The last plate you put is the first you take.

Top
 ↑
[3]
[2]
[1]
Bottom

Dry Run Walkthrough

Input: Start with empty stack, push 1, push 2, push 3, then pop one item

Goal: Show how items are added and removed following LIFO

Step 1: Push 1 onto stack

Top
 ↑
[1]
Bottom

Why: We add the first item at the top of the stack

Step 2: Push 2 onto stack

Top
 ↑
[2]
[1]
Bottom

Why: New item goes on top, above the previous one

Step 3: Push 3 onto stack

Top
 ↑
[3]
[2]
[1]
Bottom

Why: Keep adding items on top, last pushed is on top

Step 4: Pop item from stack

Top
 ↑
[2]
[1]
Bottom

Why: Remove the top item, which is the last pushed (3)

Result:

Top
 ↑
[2]
[1]
Bottom
Popped item: 3

Annotated Code

DSA Python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        # Add item to the top of the stack
        self.items.append(item)

    def pop(self):
        # Remove and return the top item if stack is not empty
        if not self.is_empty():
            return self.items.pop()
        return None

    def is_empty(self):
        # Check if stack has no items
        return len(self.items) == 0

    def __str__(self):
        # Show stack from top to bottom
        return 'Top\n ↑\n' + '\n'.join(f'[{item}]' for item in reversed(self.items)) + '\nBottom'

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack)
popped = stack.pop()
print(f'Popped item: {popped}')
print(stack)

self.items.append(item)

Add new item on top of stack

if not self.is_empty():

Check stack is not empty before popping

return self.items.pop()

Remove and return top item following LIFO

Output

Top

 ↑

[3]

[2]

[1]

Bottom

Popped item: 3

Top

 ↑

[2]

[1]

Bottom

Complexity Analysis

Time: O(1) for push and pop because adding/removing from the end of list is constant time

Space: O(n) because stack stores all pushed items

vs Alternative: Compared to a queue where removal is from front (O(n) in list), stack operations are faster and simpler

Edge Cases

Pop from empty stack

Returns None safely without error

DSA Python

if not self.is_empty():

When to Use This Pattern

When you see a problem needing last added item accessed first, use stack and LIFO principle to manage order efficiently.

Common Mistakes

Mistake: Removing items from the start of the list instead of the end
Fix: Use list.pop() without index to remove from the end, preserving LIFO

Summary

Stack stores items so the last added is the first removed (LIFO).

Use stack when you need to reverse order or track recent items first.

Remember: push adds on top, pop removes from top, like a stack of plates.

Practice

1. What does the LIFO principle mean in the context of a stack?

easy

A. Last In, First Out - the first item added is the first to be removed

B. Last In, First Out - the last item added is the first to be removed

C. First In, First Out - the first item added is the first to be removed

D. First In, Last Out - the first item added is the last to be removed

Solution

1. Step 1: Understand LIFO meaning

   LIFO means the last element added to the stack is the first one to be removed.

2. Step 2: Match with options

   Last In, First Out - the last item added is the first to be removed correctly describes this behavior as "Last In, First Out".

3. Final Answer:

   Last In, First Out - the last item added is the first to be removed -> Option B

4. Quick Check:

   LIFO = Last In, First Out [OK]

Hint: Remember stack removes newest item first [OK]

Common Mistakes:

• Confusing LIFO with FIFO
• Thinking first added is removed first
• Mixing order of insertion and removal

2. Which of the following is the correct way to push an element '5' onto a stack named stack in Python?

easy

A. stack.append(5)

B. stack.add(5)

C. stack.push(5)

D. stack.insert(5)

Solution

1. Step 1: Recall Python list methods for stack

   Python uses list's append() method to add elements to the top of the stack.

2. Step 2: Check options for correct method

   Only stack.append(5) uses append(5), which is correct for pushing onto a stack.

3. Final Answer:

   stack.append(5) -> Option A

4. Quick Check:

   Push in Python stack = append() [OK]

Hint: Use append() to push in Python stack [OK]

Common Mistakes:

• Using push() which is not a Python list method
• Using add() which is for sets
• Using insert() which inserts at specific index

3. What will be the output of the following Python code?

stack = []
stack.append(10)
stack.append(20)
stack.append(30)
print(stack.pop())
print(stack.pop())
print(stack)

medium

A. 30
10
[20]

B. 10
20
[30]

C. 20
30
[10]

D. 30
20
[10]

Solution

1. Step 1: Trace stack after each append

   After append(10): [10], append(20): [10, 20], append(30): [10, 20, 30]

2. Step 2: Trace pop operations

   pop() removes last element: first pop() returns 30, second pop() returns 20, stack left is [10]

3. Final Answer:

   30 20 [10] -> Option D

4. Quick Check:

   Stack pops last in first out [OK]

Hint: Pop removes last pushed element first [OK]

Common Mistakes:

• Thinking pop removes first element
• Confusing order of popped elements
• Not updating stack after pop

4. Identify the error in the following code that implements a stack using a Python list:

stack = []
stack.push(1)
stack.push(2)
print(stack.pop())

medium

A. Using push() method which does not exist for Python lists

B. Using pop() method incorrectly

C. Stack should be initialized as a tuple, not list

D. Missing import statement for stack

Solution

1. Step 1: Check methods used on list

   Python lists do not have a push() method; append() is used to add elements.

2. Step 2: Verify pop() usage

   pop() is valid for lists and correctly used here.

3. Final Answer:

   Using push() method which does not exist for Python lists -> Option A

4. Quick Check:

   Python list push() does not exist [OK]

Hint: Use append(), not push(), to add in Python list [OK]

Common Mistakes:

• Assuming push() is valid for Python lists
• Thinking pop() needs arguments
• Confusing list with stack module

5. Given a stack implemented as a Python list, which sequence of operations will reverse the order of elements in the stack?
Assume initial stack is [1, 2, 3] where 3 is the top.
Choose the correct sequence:

hard

A. Append elements to the stack again without popping

B. Use pop() repeatedly and append to the same stack without extra storage

C. Pop all elements into a new stack

D. Sort the stack list in ascending order

Solution

1. Step 1: Understand reversing stack by popping

   Pop elements from original stack and push them into a new stack reverses order.

2. Step 2: Confirm other options

   Appending without popping or sorting does not reverse stack order correctly.

3. Final Answer:

   Pop all elements into a new stack -> Option C

4. Quick Check:

   Two stacks pop/push reverses order [OK]

Hint: Use two stacks to reverse order [OK]

Common Mistakes:

• Trying to reverse by sorting
• Appending without popping
• Using one stack without extra storage