Design and Implement Special Stack Data Structure

You are given n commands. The task is to implement a stack that performs operations based on the following commands:

• push x: Push integer x onto the top of the stack.
• pop: Pop the top element from the stack.
• inc k y: Increment the bottom ‘k‘ elements of the stack by value ‘y‘.

After each operation, print the value at the top of the stack. If the stack is empty print “NULL”.

Examples:

Input: commands[ ]={ “push 5”, “push 7”, “inc 1 3”, “pop”, “pop”}
Output: 5 7 7 8 NULL

Input: commands[ ]={ “push 3”, “push 1”, “pop”, “push 4”, “inc 2 2”, “pop”}
Output: 3 1 3 4 6 5

Illustrations:

Naive Approach: The idea is to maintain a stack. For the increment operations, we just pop all the elements and store them in another container. Then we push the stored elements back to the stack after incrementing the last ‘k‘ elements by ‘y‘. Therefore this approach includes poping all the elements and then pushing back for the increment operation, making it inefficient.
Time Complexity: O(n^2)

Efficient Approach: The idea is to maintain two containers

Below is the implementation of the above approach:

#include <bits/stdc++.h>
using namespace std;

// function to implement push operation
void implement_push(string s, vector<int>& st,
                    vector<int>& incre, int& i)
{
    // extracting 'x' from the command string
    string p = s.substr(5);
    int x = stoi(p);
    // pushing x into the container
    st[i] = x;

    // increment stack pointer
    i++;
}

// function to implement pop operation
void implement_pop(string s, vector<int>& st,
                   vector<int>& incre, int& i)
{
    // pop by making the element
    // at the top 0
    st[i - 1] = 0;

    // maintaining the incre container
    // by doing suffix sum
    if (i - 2 >= 0)
        incre[i - 2] += incre[i - 1];
    incre[i - 1] = 0;

    // decrementing stack pointer
    i--;
}

// function to implement increment operation
void implement_increment(string s, vector<int>& st,
                         vector<int>& incre, int& i)
{
    // extracting k and y from the string
    int e = 4;
    string p = "";
    while (s[e] != ' ')
        p += s[e++];
    e++;
    string r = "";
    int z = s.size();
    while (e < z)
        r += s[e++];
    int k = stoi(p);
    int y = stoi(r);

    // incrementing k-1th index
    // in the incre container
    // by y

    incre[k - 1] += y;
}
// Function to implement stack
// on the given commands
void implementStack(vector<string>& commands)
{
    // calculating number of commands
    int n = commands.size();

    // maintaining two containers
    // one for the stack and the other
    // for the increment operation
    vector<int> st(n, 0), incre(n, 0);

    // initialising the stack pointer
    int i = 0;

    // traversing through the commands
    for (auto s : commands) {

        // push command
        if (s.substr(0, 4) == "push")
            implement_push(s, st, incre, i);

        // pop command
        else if (s.substr(0, 3) == "pop")
            implement_pop(s, st, incre, i);

        // increment command
        else
            implement_increment(s, st, incre, i);

        // Printing the top element
        if (i == 0)
            cout << "NULL ";
        else
            cout << st[i - 1] + incre[i - 1] << " ";
    }
}
// Driver Program
int main()
{
    // commands
    vector<string> commands
        = { "push 5", "push 7", "inc 1 3", "pop", "pop" };

    // calling function to implement stack
    implementStack(commands);
}

Output:

5 7 7 8 NULL 

Time Complexity: O(n)
Auxiliary Space: O(n)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.