709994. Insert an Element at the Bottom of a Stack
Insert an Element at the Bottom of a Stack
Slug: insert-an-element-at-the-bottom-of-a-stack
Difficulty: Easy
Id: 709994
Topic Tags: Recursion, Stack, implementation, Data Structures, Algorithms
Company Tags: None
Summary
The problem is about implementing a stack data structure and inserting an element at the bottom of the stack. This requires manipulating the existing elements in the stack to make room for the new element, which involves recursive operations.
Detailed Explanation
To solve this problem, we will implement a stack using a linked list, where each node represents an element in the stack. We will create a function pushBottom that takes the new element as input and inserts it at the bottom of the stack.
Here's the step-by-step breakdown:
- Start with the current top element of the stack.
- If the stack is empty (i.e., there are no elements), simply push the new element to become the first element in the stack.
- Otherwise, recursively call
pushBottomon the next element until you reach the bottom of the stack. - At the bottom of the stack, insert the new element and return.
Here's an ASCII art diagram representing the stack:
+---------------+
| Top Element |
+---------------+
| ... |
+---------------+
| Bottom |
+---------------+
When inserting a new element at the bottom, it will look like this:
+---------------+
| New Element |
+---------------+
| Top Element |
+---------------+
| ... |
+---------------+
| Old Bottom |
+---------------+
Time complexity: O(n), where n is the number of elements in the stack, as we need to traverse the entire stack to insert a new element at the bottom. Space complexity: O(1), as we are only using a constant amount of space to store the new element.
Optimized Solutions
Java
public class Stack {
public void pushBottom(int x) {
Node newNode = new Node(x);
if (isEmpty()) {
firstElement = newNode;
} else {
pushBottomHelper(firstElement, newNode);
}
}
private void pushBottomHelper(Node current, Node newNode) {
if (current.next == null) {
current.next = newNode;
} else {
pushBottomHelper(current.next, newNode);
}
}
}