Program to Insert an Element at the Bottom of a Stack

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();
        }
        
}

You can also try this code with Online C++ Compiler

Run Code

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