TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
push
, pop
, peek
, and is_empty
.pop
method should return the value at the top of the stack and remove it.peek
method should return the value at the top of the stack without removing it.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`.
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:
push
adds a node to the front, pop
removes the front node, and peek
returns the value of the front node.front
pointer always points to the top of the stack.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
front
pointer correctly after push
and pop
.pop
and peek
.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
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
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.
O(1)
for all operations (push
, pop
, peek
, and is_empty
) because they all involve only a constant number of operations.O(N)
because the space used by the stack is proportional to the number of elements in the stack.