Stack 'Em Up! - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10-20 mins
• 🛠️ Topics: Stack, Linked List, LIFO

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What does the problem ask for?
  • A: The problem asks to implement a stack using a singly linked list.
  • A: The stack should support standard stack operations like push, pop, peek, and is_empty.
• Q: What should be returned?
  • A: The pop method should return the value at the top of the stack and remove it.
  • A: The peek method should return the value at the top of the stack without removing it.
  • A: The is_empty method should return True if the stack is empty and False otherwise.

HAPPY CASE
Input: 
    - stack = Stack()
    - stack.push(('Educated', 'Tara Westover'))
    - stack.push(('Gone Girl', 'Gillian Flynn'))
    - stack.push(('Dune', 'Frank Herbert'))
Output: 
    - Dune -> Gone Girl -> Educated
    - Peek: ('Dune', 'Frank Herbert')
    - Pop: ('Dune', 'Frank Herbert')
    - Pop: ('Gone Girl', 'Gillian Flynn')
    - Is Empty: False
    - Pop: ('Educated', 'Tara Westover')
    - Is Empty: True

EDGE CASE
Input: 
    - stack = Stack()
    - Pop: None
    - Peek: None
    - Is Empty: True
Output: 
    - None
Explanation: 
    - The stack is empty, so `pop` and `peek` return `None`, and `is_empty` returns `True`.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Stack, Linked List, etc.

For Stack problems involving Linked List, we want to consider the following approaches:

• Node Management: Manage the nodes of the linked list such that push adds a node to the front, pop removes the front node, and peek returns the value of the front node.
• Pointer Handling: Ensure that the front pointer always points to the top of the stack.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will implement the stack using a singly linked list where the front pointer always points to the top of the stack.

1) Implement the `Node` class to create nodes for the linked list.
2) Implement the `Stack` class with the following methods:
    - `__init__`: Initialize an empty stack with `front` set to `None`.
    - `is_empty`: Return `True` if `front` is `None`, otherwise return `False`.
    - `push`: Create a new node, link it to the current `front`, and update `front`.
    - `pop`: Remove and return the value of the node at `front`. Update `front` to point to the next node.
    - `peek`: Return the value of the node at `front` without removing it.

⚠️ Common Mistakes

• Forgetting to update the front pointer correctly after push and pop.
• Incorrectly handling the empty stack case in pop and peek.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class Stack:
    def __init__(self):
        self.front = None

    def is_empty(self):
        return self.front is None

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.front
        self.front = new_node

    def pop(self):
        if self.is_empty():
            return None
        popped_node = self.front
        self.front = self.front.next
        return popped_node.value

    def peek(self):
        if self.is_empty():
            return None
        return self.front.value

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Example: Use the provided stack operations to verify that the class methods behave as expected.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of elements in the stack.

• Time Complexity: O(1) for all operations (push, pop, peek, and is_empty) because they all involve only a constant number of operations.
• Space Complexity: O(N) because the space used by the stack is proportional to the number of elements in the stack.