Push Operation on Stack in DSA Rust

Mental Model

A stack is like a pile where you add new items only on top. Pushing means putting a new item on the top of this pile.

Analogy: Imagine stacking plates in a cupboard. When you add a new plate, you always put it on the top of the stack.

Top -> null

Dry Run Walkthrough

Input: stack: empty, push values 1, then 2, then 3

Goal: Add values one by one on top of the stack so the last pushed is on top

Step 1: push 1 onto empty stack

Top -> [1] -> null

Why: First item becomes the top of the stack

Step 2: push 2 onto stack

Top -> [2] -> [1] -> null

Why: New item goes on top, previous top moves down

Step 3: push 3 onto stack

Top -> [3] -> [2] -> [1] -> null

Why: Keep adding new items on top, last in first out order

Result:

Top -> 3 -> 2 -> 1 -> null

Annotated Code

DSA Rust

use std::fmt;

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

struct Stack {
    top: Option<Box<Node>>,
}

impl Stack {
    fn new() -> Self {
        Stack { top: None }
    }

    fn push(&mut self, val: i32) {
        // create new node with value and next pointing to current top
        let new_node = Box::new(Node {
            value: val,
            next: self.top.take(),
        });
        // update top to new node
        self.top = Some(new_node);
    }

    fn to_string(&self) -> String {
        let mut result = String::new();
        let mut current = &self.top;
        while let Some(node) = current {
            result.push_str(&format!("{} -> ", node.value));
            current = &node.next;
        }
        result.push_str("null");
        result
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    println!("Top -> {}", stack.to_string());
}

let new_node = Box::new(Node { value: val, next: self.top.take() });

create new node with value and link it to current top

self.top = Some(new_node);

update top pointer to new node -- new item is now on top

Output

Top -> 3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(1) because push adds a new node directly on top without traversal

Space: O(1) because only one new node is created per push

vs Alternative: Compared to array-based stack where resizing may be needed, linked list push is always constant time without resizing overhead

Edge Cases

pushing onto an empty stack

top becomes the new node with no next

DSA Rust

self.top = Some(new_node);

When to Use This Pattern

When you see a problem requiring last-in-first-out order with frequent adds/removes at one end, reach for stack push/pop operations because they efficiently manage the top element.

Common Mistakes

Mistake: Not updating the top pointer to the new node after push
Fix: Assign the new node to top after linking it to the previous top

Mistake: Linking new node's next to None instead of current top
Fix: Set new node's next to current top to keep the stack chain

Summary

Adds a new item on top of the stack.

Use when you need to store items in last-in-first-out order.

The new item always points to the previous top, then becomes the new top.

Practice

1. What does the push operation do in a stack data structure?

easy

A. Removes the top element from the stack

B. Adds an element to the top of the stack

C. Returns the bottom element of the stack

D. Checks if the stack is empty

Solution

1. Step 1: Understand stack behavior

   A stack follows Last In First Out (LIFO) principle, where elements are added or removed from the top.

2. Step 2: Define push operation

   The push operation adds a new element on top of the existing elements in the stack.

3. Final Answer:

   Adds an element to the top of the stack -> Option B

4. Quick Check:

   Push = Add top element [OK]

Hint: Push always adds to the top of the stack [OK]

Common Mistakes:

• Confusing push with pop operation
• Thinking push removes elements
• Assuming push adds to the bottom

2. Which of the following is the correct Rust syntax to push an element 5 onto a stack implemented as a Vec<i32> named stack?

easy

A. stack.push(5);

B. stack.add(5);

C. stack.insert(5);

D. stack.append(5);

Solution

1. Step 1: Recall Rust Vec push method

   In Rust, Vec has a method push to add elements at the end (top of stack).

2. Step 2: Check method names

   add, insert, and append have different meanings or require different parameters.

3. Final Answer:

   stack.push(5); -> Option A

4. Quick Check:

   Vec push method = stack.push(5); [OK]

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

Common Mistakes:

• Using .add() which does not exist for Vec
• Confusing .insert() which needs index
• Using .append() which merges vectors

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

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

medium

A. [10, 20, 30]

B. [30, 20, 10]

C. [10, 20]

D. Compilation error

Solution

1. Step 1: Trace push operations

   Elements 10, 20, and 30 are pushed in order, so stack contains [10, 20, 30].

2. Step 2: Understand Vec print format

   Printing with {:?} shows elements in insertion order, so output is [10, 20, 30].

3. Final Answer:

   [10, 20, 30] -> Option A

4. Quick Check:

   Push order preserved in Vec print [OK]

Hint: Vec prints elements in insertion order [OK]

Common Mistakes:

• Assuming stack prints top element first
• Confusing push order with pop order
• Expecting reversed output

4. Identify the error in this Rust code that tries to push an element onto a stack:

let stack = Vec::new();
stack.push(100);

medium

A. Missing semicolon after push

B. Vec::new() is incorrect syntax

C. push method does not exist for Vec

D. stack is immutable, cannot push

Solution

1. Step 1: Check variable mutability

   The variable stack is declared immutable by default, so push cannot modify it.

2. Step 2: Understand push method requirements

   push requires the vector to be mutable to add elements.

3. Final Answer:

   stack is immutable, cannot push -> Option D

4. Quick Check:

   Mutable vector needed for push [OK]

Hint: Declare stack as mutable with 'mut' to push [OK]

Common Mistakes:

• Forgetting to add 'mut' keyword
• Thinking Vec::new() is wrong syntax
• Assuming push is not a Vec method

5. You want to implement a stack using a Rust Vec<i32> and push elements 1, 2, 3 in that order. After pushing, you want to print the stack from top to bottom. Which code snippet correctly achieves this?

hard

A. let mut stack = Vec::new();
stack.push(1);
stack.push(2);
stack.push(3);
for i in stack.iter() {
println!("{}", i);
}

B. let mut stack = Vec::new();
stack.push(3);
stack.push(2);
stack.push(1);
for i in stack.iter() {
println!("{}", i);
}

C. let mut stack = Vec::new();
stack.push(1);
stack.push(2);
stack.push(3);
for i in stack.iter().rev() {
println!("{}", i);
}

D. let mut stack = Vec::new();
stack.push(1);
stack.push(2);
stack.push(3);
for i in stack.into_iter() {
println!("{}", i);
}

Solution

1. Step 1: Push elements in order

   Elements 1, 2, 3 are pushed in order, so stack is [1, 2, 3] with 3 at top.

2. Step 2: Print from top to bottom

   To print from top (last pushed) to bottom, iterate in reverse order using iter().rev().

3. Final Answer:

   Code snippet with stack.iter().rev() -> Option C

4. Quick Check:

   Reverse iteration prints top to bottom [OK]

Hint: Use .iter().rev() to print stack top to bottom [OK]

Common Mistakes:

• Printing in normal order shows bottom to top
• Pushing elements in reverse order
• Using into_iter() which consumes the stack