Stacks (last-in, first-out) in Intro to Computing - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ trace

intermediate

Trace the stack operations and find the top element

Consider a stack initially empty. The following operations are performed in order:

1. Push 5
2. Push 10
3. Pop
4. Push 7
5. Push 3
6. Pop

What is the top element of the stack after these operations?

A 3

B 10

C 5

D 7

💡 Hint

Remember, pop removes the last pushed item, and push adds to the top.

Step-by-step stack content:
Push 5 → [5]
Push 10 → [5, 10]
Pop → removes 10, stack is [5]
Push 7 → [5, 7]
Push 3 → [5, 7, 3]
Pop → removes 3, stack is [5, 7]
Top element is 7.

🧠 Conceptual

intermediate

Identify the correct property of a stack

Which of the following best describes the behavior of a stack data structure?

A First-in, first-out (FIFO)

B Last-in, first-out (LIFO)

C Random access to any element

D Sorted order insertion

💡 Hint

Think about which element is removed first when you pop from a stack.

A stack follows Last-in, first-out (LIFO) behavior, meaning the last item added is the first to be removed.

❓ Comparison

advanced

Compare stack and queue behaviors

Which statement correctly compares a stack and a queue?

A Stacks remove elements in LIFO order; queues remove elements in FIFO order.

B Stacks and queues both remove elements in the order they were added.

C Stacks remove elements in FIFO order; queues remove elements in LIFO order.

D Stacks allow random access; queues only allow access to the last element.

💡 Hint

Recall the order in which elements are removed from each data structure.

Stacks remove the last added element first (LIFO). Queues remove the first added element first (FIFO).

❓ identification

advanced

Identify the error in stack operation code

Given the following pseudocode for stack operations:

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

What error will occur when this code runs?

Intro to Computing

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

A AttributeError: 'list' object has no attribute 'push'

B SyntaxError: invalid syntax

C IndexError: popping from empty stack

D No error, code runs successfully

💡 Hint

Check if the method names used for list operations are correct in Python.

In Python, lists do not have a 'push' method. The correct method to add an element is 'append'. Using 'push' causes an AttributeError.

🚀 Application

expert

Determine the output of stack-based expression evaluation

A stack is used to evaluate the postfix expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +

What is the final result after evaluating this expression using a stack?

A 5.5

B Error: invalid expression

C 3.0001220703125

D 7.0

💡 Hint

Evaluate step-by-step using stack: push numbers, pop two for operators, apply operator, push result back.

Step-by-step evaluation:
3 push
4 push
2 push
* pop 2 and 4 → 4*2=8 push 8
1 push
5 push
- pop 5 and 1 → 1-5=-4 push -4
2 push
3 push
^ pop 3 and 2 → 2^3=8 push 8
^ pop 8 and -4 → (-4)^8=65536 push 65536
/ pop 65536 and 8 → 8/65536=0.0001220703125 push 0.0001220703125
+ pop 0.0001220703125 and 3 → 3 + 0.0001220703125 = 3.0001220703125
Final result: 3.0001220703125

Practice

1. What does the term last-in, first-out (LIFO) mean in the context of a stack?

easy

A. The last item added is the first one removed.

B. The first item added is the first one removed.

C. Items are removed in random order.

D. Items are removed based on their size.

Solution

1. Step 1: Understand the order of operations in a stack

   A stack stores items so that the last item you put in is the first one you take out.

2. Step 2: Match the definition to the options

   The last item added is the first one removed correctly describes this behavior as "last item added is first removed".

3. Final Answer:

   The last item added is the first one removed. -> Option A

4. Quick Check:

   LIFO = Last In, First Out [OK]

Hint: Remember: last added is first removed in stacks [OK]

Common Mistakes:

• Confusing LIFO with FIFO (queue behavior)
• Thinking items are removed in the order they were added
• Assuming random removal order

2. Which of the following is the correct way to add an item to a stack?

easy

A. Use the pop operation.

B. Use the peek operation.

C. Use the push operation.

D. Use the enqueue operation.

Solution

1. Step 1: Recall stack operations

   Stacks use push to add items and pop to remove items.

2. Step 2: Identify the correct operation for adding

   Only push adds an item to the stack, so Use the push operation is correct.

3. Final Answer:

   Use the push operation. -> Option C

4. Quick Check:

   Push adds items to stack [OK]

Hint: Push adds, pop removes from stack [OK]

Common Mistakes:

• Confusing pop as adding instead of removing
• Using queue terms like enqueue
• Thinking peek adds items

3. Consider this sequence of stack operations starting with an empty stack:

push(5)
push(3)
pop()
push(2)
pop()
pop()

What is the result of the last pop() operation?

medium

A. 5

B. 3

C. 2

D. Stack is empty

Solution

1. Step 1: Trace each operation on the stack

   Start empty: []
   push(5) -> [5]
   push(3) -> [5, 3]
   pop() removes 3 -> [5]
   push(2) -> [5, 2]
   pop() removes 2 -> [5]
   pop() removes 5 -> []

2. Step 2: Identify the last pop result

   The last pop removes 5, so the result is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Last pop removes 5 [OK]

Hint: Follow push/pop step-by-step to track top item [OK]

Common Mistakes:

• Forgetting the order of pop removes last pushed
• Mixing up which item is on top
• Assuming pop returns the first pushed item

4. The following code tries to pop an item from an empty stack. What is the likely problem?

stack = []
item = stack.pop()

medium

A. It will silently ignore the pop.

B. It will return None.

C. It will add an item instead of removing.

D. It will raise an error because the stack is empty.

Solution

1. Step 1: Understand pop behavior on empty stack

   Calling pop on an empty list (stack) causes an error because there is no item to remove.

2. Step 2: Identify the error type

   In Python, this raises an IndexError indicating the stack is empty.

3. Final Answer:

   It will raise an error because the stack is empty. -> Option D

4. Quick Check:

   Pop on empty stack causes error [OK]

Hint: Pop on empty stack causes error, never returns None [OK]

Common Mistakes:

• Assuming pop returns None if empty
• Thinking pop adds items
• Ignoring runtime errors

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

hard

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

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

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

D. Push and pop items randomly to reverse.

Solution

1. Step 1: Understand stack reverses order by LIFO

   Pushing items in original order puts last item on top. Popping all items returns them in reverse order.

2. Step 2: Match the correct sequence

   Push all items in order, then pop all items to get reversed list describes pushing all items then popping all to reverse the list correctly.

3. Final Answer:

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

4. Quick Check:

   Stack reverses order by push then pop [OK]

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

Common Mistakes:

• Pushing in reverse order then popping returns original order
• Popping before pushing causes error
• Random push/pop does not guarantee reversal