Stack operations (push, pop, peek) in Data Structures Theory - Time & Space Complexity

Time Complexity: Stack operations (push, pop, peek)

O(1)

Understanding Time Complexity

When working with stacks, it is important to know how fast basic actions like adding or removing items happen.

We want to understand how the time to do these actions changes as the stack grows.

Scenario Under Consideration

Analyze the time complexity of the following stack operations.

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

This code shows how to add, remove, and look at the top item of a stack using a list.

Identify Repeating Operations

Each operation works on the end of the list without loops or recursion.

• Primary operation: Adding or removing one item at the end of the list.
• How many times: Each operation happens once per call, no repeated steps inside.

How Execution Grows With Input

Each push, pop, or peek takes about the same time no matter how many items are in the stack.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time stays constant even as the stack grows larger.

Final Time Complexity

Time Complexity: O(1)

This means each stack operation takes the same short time no matter how many items are in the stack.

Common Mistake

[X] Wrong: "Pop or push takes longer when the stack is very big."

[OK] Correct: These operations only touch the top item, so their time does not grow with stack size.

Interview Connect

Knowing that stack operations are quick and constant time helps you explain why stacks are useful in many programs.

Self-Check

"What if the stack was implemented using a linked list instead of a list? How would the time complexity change?"

Practice

1. What does the pop operation do in a stack?

easy

A. Shows the bottom item without removing it

B. Adds a new item to the bottom of the stack

C. Removes and returns the top item from the stack

D. Clears all items from the stack

Solution

1. Step 1: Understand the pop operation

   The pop operation removes the last item added to the stack, which is the top item.

2. Step 2: Confirm the behavior of pop

   It returns this top item and removes it from the stack, following last-in, first-out order.

3. Final Answer:

   Removes and returns the top item from the stack -> Option C

4. Quick Check:

   pop = remove top item [OK]

Hint: Pop always removes the last item added [OK]

Common Mistakes:

• Thinking pop adds an item
• Confusing pop with peek
• Assuming pop removes bottom item

2. Which of the following is the correct way to add an item 5 to a stack named s using the push operation?

easy

A. s.pop(5)

B. s.push(5)

C. s.peek(5)

D. s.add(5)

Solution

1. Step 1: Identify the push syntax

   Push adds an item to the top of the stack, usually called with push(item).

2. Step 2: Match the correct method call

   Only s.push(5) correctly adds 5 to the stack.

3. Final Answer:

   s.push(5) -> Option B

4. Quick Check:

   push = add item [OK]

Hint: Push means add, so look for push() method [OK]

Common Mistakes:

• Using pop instead of push
• Using peek to add items
• Using add which is not standard for stacks

3. Given the following stack operations:

s.push(10)
s.push(20)
s.pop()
s.push(30)
top = s.peek()

What is the value of top after these operations?

medium

A. 30

B. 20

C. None

D. 10

Solution

1. Step 1: Trace the stack changes step-by-step

   After push(10), stack = [10]. After push(20), stack = [10, 20]. After pop(), top 20 is removed, stack = [10]. After push(30), stack = [10, 30].

2. Step 2: Determine the top item with peek

   Peek returns the top item without removing it, so top = 30.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Last pushed after pop is 30 [OK]

Hint: Track stack after each operation carefully [OK]

Common Mistakes:

• Forgetting pop removes top
• Assuming peek removes item
• Mixing order of operations

4. Consider this code snippet for a stack:

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

What is the error in this code?

medium

A. stack is not initialized correctly

B. pop() does not return the top item

C. stack.pop() removes the bottom item, not top

D. push() is not a method of list in Python

Solution

1. Step 1: Check stack initialization

   The stack is initialized as an empty list, which is correct in Python.

2. Step 2: Verify method usage on list

   Python lists use append() to add items, not push(). Using push() causes an error.

3. Final Answer:

   push() is not a method of list in Python -> Option D

4. Quick Check:

   Python list uses append(), not push() [OK]

Hint: Remember Python list uses append(), not push() [OK]

Common Mistakes:

• Assuming push() works on Python lists
• Confusing pop() behavior
• Thinking stack initialization is wrong

5. You want to reverse a list [1, 2, 3] using a stack. Which sequence of stack operations correctly reverses the list?

hard

A. Push all items in order, then pop all items to get reversed list

B. Pop all items first, then push them back in order

C. Peek all items, then push them again

D. Push items in reverse order, then pop all items

Solution

1. Step 1: Understand stack reversal logic

   Pushing items in original order stores them with last item on top. Popping all items removes them in reverse order.

2. Step 2: Apply push then pop to reverse list

   Push 1, then 2, then 3. Popping returns 3, 2, 1, which is the reversed list.

3. Final Answer:

   Push all items in order, then pop all items to get reversed list -> Option A

4. Quick Check:

   Push then pop reverses order [OK]

Hint: Push in order, pop all to reverse list [OK]

Common Mistakes:

• Pushing in reverse order first
• Using peek to reverse
• Popping before pushing