Stack Concept and LIFO Principle in DSA Rust - Time & Space Complexity

Time Complexity: Stack Concept and LIFO Principle

O(1)

Understanding Time Complexity

We want to understand how fast stack operations run as the number of items grows.

How does adding or removing items affect the time it takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Stack {
    items: Vec<i32>,
}

impl Stack {
    fn push(&mut self, item: i32) {
        self.items.push(item);
    }

    fn pop(&mut self) -> Option<i32> {
        self.items.pop()
    }
}
    

This code shows a stack using a vector, adding items on top and removing the last added item.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one item at the end of the vector.
• How many times: Each push or pop happens once per call, no loops inside.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	1 operation per push or pop
100	1 operation per push or pop
1000	1 operation per push or pop

Pattern observation: The time stays about the same no matter how big the stack is.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing an item takes the same short time regardless of stack size.

Common Mistake

[X] Wrong: "Pushing or popping takes longer as the stack grows because it has more items."

[OK] Correct: The stack only adds or removes the last item, so it does not need to look at all items, keeping time constant.

Interview Connect

Knowing stack operations run in constant time shows you understand efficient data handling, a key skill in many coding tasks.

Self-Check

"What if we changed the stack to remove items from the front instead of the end? How would the time complexity change?"

Practice

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

easy

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

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

C. Last In, First Out - the last element added is the first to be removed

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

Solution

1. Step 1: Understand LIFO meaning

   LIFO means the last item added to the stack is the first one to be taken out.

2. Step 2: Match with options

   Last In, First Out - the last element added is the first to be removed correctly states "Last In, First Out" which matches the LIFO principle.

3. Final Answer:

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

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 up order of insertion and removal

2. Which of the following is the correct Rust syntax to push an element 10 onto a stack named stack?

easy

A. stack.push(10);

B. stack.add(10);

C. stack.insert(10);

D. stack.append(10);

Solution

1. Step 1: Recall Rust Vec stack push method

   In Rust, a stack is often implemented using a Vec, and pushing uses the push method.

2. Step 2: Check method names

   Only push is the correct method to add an element at the end of a Vec.

3. Final Answer:

   stack.push(10); -> Option A

4. Quick Check:

   Rust Vec push method = push() [OK]

Hint: Use push() to add elements to Rust Vec stack [OK]

Common Mistakes:

• Using add() which does not exist
• Using insert() without index
• Using append() which expects another collection

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

let mut stack = Vec::new();
stack.push(5);
stack.push(10);
let x = stack.pop();
println!("{:?}", x);

medium

A. Some(10)

B. 10

C. None

D. Some(5)

Solution

1. Step 1: Trace stack push operations

   Stack after pushes: [5, 10] (10 is last pushed)

2. Step 2: Trace pop operation

   Pop removes last element 10 and returns Some(10) because pop returns Option type.

3. Final Answer:

   Some(10) -> Option A

4. Quick Check:

   pop() returns Some(last element) = Some(10) [OK]

Hint: pop() returns Some(last pushed) or None if empty [OK]

Common Mistakes:

• Thinking pop returns raw value, not Option
• Confusing order of elements popped
• Expecting None instead of Some value

4. Identify the error in this Rust code snippet that tries to pop from an empty stack:

let mut stack: Vec<i32> = Vec::new();
let value = stack.pop().unwrap();
println!("{}", value);

medium

A. pop() method does not exist on Vec

B. Calling unwrap() on None causes panic

C. stack is not mutable

D. println! macro syntax is incorrect

Solution

1. Step 1: Understand pop() on empty Vec

   pop() returns None if Vec is empty.

2. Step 2: Effect of unwrap() on None

   Calling unwrap() on None causes a runtime panic (crash).

3. Final Answer:

   Calling unwrap() on None causes panic -> Option B

4. Quick Check:

   unwrap() on None = panic [OK]

Hint: Never unwrap pop() without checking if stack is empty [OK]

Common Mistakes:

• Assuming pop() always returns Some
• Ignoring mutability requirement
• Misreading println! syntax

5. Given a stack implemented as a Rust Vec, what will be the content of the stack after the following sequence of operations?

Operations:
1) push(1)
2) push(2)
3) pop()
4) push(3)
5) push(2)
6) pop()

hard

A. Stack after operations is [1, 2]

B. Stack after operations is [1, 2, 3]

C. Stack after operations is [1, 3, 2]

D. Stack after operations is [1, 3]

Solution

1. Step 1: Simulate each operation step-by-step

   Start: [] 1) push(1) -> [1] 2) push(2) -> [1, 2] 3) pop() removes 2 -> [1] 4) push(3) -> [1, 3] 5) push(2) -> [1, 3, 2] 6) pop() removes 2 -> [1, 3]

2. Step 2: Compare final stack with options

   Final stack is [1, 3], which matches Stack after operations is [1, 3].

3. Final Answer:

   Stack after operations is [1, 3] -> Option D

4. Quick Check:

   Trace pushes and pops carefully [OK]

Hint: Track pushes and pops stepwise to find final stack [OK]

Common Mistakes:

• Ignoring pop removes last pushed element
• Mixing order of push and pop
• Assuming pop removes first element