## Introduction

In this blog, we will discuss a stack problem that has been asked frequently in Interviews.

The problem is to **insert an element at the Bottom of a Stack.**

I am starting with what is a stack.

**Stack** is a data structure following a specific order in which the operations are performed. It follows two mechanisms: Last in First Out & First in Last Out.

To know more about the stack, refer here.

Now, coming to the question.

We are given N elements in a stack, and we are asked to insert an element at the bottom of the stack.

Say we need to insert 7 at the bottom of the stack

It would look like this:

## Approach

Now we will discuss the** approach** to inserting an element at the Bottom of a Stack.

If the stack is empty, push the element given into the stack.

â¬‡

Else, perform the below-mentioned operation.

- Make a temporary variable, and store the topmost element of the stack in it.
- Pop out the stored element.
- Continue this recursively till the stack becomes empty.
- Now, again push all the popped-out elements in the stack after pushing the element to be inserted. This makes sure that the push operation follows the first in last out operation.

â¬‡

Define the main function, Enter the number of elements in the stack and their content and push it in the stack. Enter element to be inserted at the bottom. Recursively call insert at bottom function and print the stack.

Time Complexity = n.

Since all elements are traversed once.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

And solve some related problems on the Stack.

Some Commonly asked problems on the stack.

If you could not solve how to insert an element at the Bottom of a Stack., donâ€™t be sad. This is part of the learning process.

Please have a look at the algorithm, and then again, you must give it a try.

### PseudoCode

**Algorithm**

___________________________________________________________________

**procedure** insert an element at the Bottom of a Stack(stack<int> st, int x ):

___________________________________________________________________

**1.** If st.empty():

st.push(x)

**2. **Else:

a=st.top()

st.pop()

st=insert_at_bottom(st,x)

st.push(a)

**3.** Return st.

**end procedure**

___________________________________________________________________

### CODE IN C++

```
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//Function to insert element at the bottom of stack
stack<int> insert_at_bottom(stack<int> st, int x){
//if stack is empty, push the element
if(st.empty()){
st.push(x);
}
else{
//stores the top element
int a= st.top();
//pop the stored top element
st.pop();
//Perform same operation with remaining element
st=insert_at_bottom(st, x);
//push the previous top element again
st.push(a);
}
return st;
}
int main()
{
int n,x;
//Enter number of elements in the stack and their content and push it in the stack
cin>>n;
stack<int> st;
for(int i=0; i<n; i++){
int value;
cin>>value;
st.push(value);
}
//enter element to be inserted at the bottom
cin>>x;
//recursively call insert at bottom function
st=insert_at_bottom(st, x);
//print the stack
while (!st.empty()) {
cout<<st.top()<<" ";
st.pop();
}
}
```

**Output**

```
Input:
5
5
4
3
2
1
7
Output: 1 2 3 4 5 7
```

### Complexity Analysis

**Time Complexity:** **O(n).**

**Analyzing Time Complexity:**

In the worst case, all elements are to be traversed once.

âˆ´n.

**Space complexity**: O(1) since no extra variable is used.

Must Read __Stack Operations__