Stacks (last-in, first-out) in Intro to Computing - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a stack in computing?

A stack is a way to store items where the last item added is the first one to be removed. This is called Last-In, First-Out (LIFO). Imagine a stack of plates: you add plates on top and take plates from the top.

beginner

What does 'Last-In, First-Out' (LIFO) mean?

It means the last item you put in is the first one you take out. Like a stack of books, you add new books on top and remove the top book first.

beginner

Name two main operations of a stack.

1. Push: Add an item to the top of the stack.
2. Pop: Remove the item from the top of the stack.

intermediate

What happens if you try to pop from an empty stack?

This is called 'underflow'. It means there is nothing to remove because the stack is empty.

beginner

Give a real-life example of a stack.

A stack of trays in a cafeteria. You put trays on top and take trays from the top, so the last tray placed is the first one taken.

What operation adds an item to the top of a stack?

A Push

B Pop

C Peek

D Insert

Push means adding an item to the top of the stack.

If you have a stack with items A, B, C (C on top), which item will be removed first?

A A

B B

C C

D None

The last item added (C) is removed first in a stack.

What is the term for trying to remove an item from an empty stack?

A Overflow

B Underflow

C Stacking

D Push error

Underflow happens when you try to pop from an empty stack.

Which of these is NOT a stack operation?

A Push

B Pop

C Peek

D Sort

Sort is not a basic stack operation.

Stacks follow which order principle?

A Last-In, First-Out

B First-In, First-Out

C Random Access

D First-In, Last-Out

Stacks follow Last-In, First-Out (LIFO) order.

Explain how a stack works using a real-life example.

Think about how you add and remove items from a pile.

Describe what happens step-by-step when you push and then pop items from a stack.

Imagine adding and removing books from a stack.

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