1.
Introduction
2.
Approach
2.1.
PseudoCode
2.2.
CODE IN C++
2.3.
Complexity Analysis
3.
3.1.
How to approach a problem like this?
3.2.
What is the mechanism followed by stack?
3.3.
What are the prerequisites for this problem?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Program to Insert an Element at the Bottom of a Stack

Urwashi Priya
0 upvote

## 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.

### How to approach a problem like this?

First, understand the problem. The best way is to use diagrams. Then write your algorithm. Then start with the Brute Force method. Lastly, try to optimize your code.

### What is the mechanism followed by stack?

First In Last Out & Last In First Out.

### What are the prerequisites for this problem?

We should have a thorough understanding of recursion.