Write a Stack class: push(),pop() methods without using built-in pop() method. Following questions was to write a MinStack class which contains a method that finds the minimal value of a stack using only push() and pop().

Question

Use two stacks: one to store actual stack elements and other as an auxiliary stack to store min · Accepted Answer

Push(int x) // inserts an element x to Special Stack 
1) push x to the first stack (the stack with actual elements)
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.
…..a) If x is smaller than y then push x to the auxiliary stack.
…..b) If x is greater than y then push y to the auxiliary stack.

int Pop() // removes an element from Special Stack and return the removed element 
1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.

The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

int getMin() // returns the minimum element from Special Stack 
1) Return the top element of auxiliary stack.

We can see that all above operations are O(1).

class SpecialStack: public Stack
{
    Stack min;
public:
    int pop();
    void push(int x);
    int getMin();
};
 
/* SpecialStack's member method to insert an element to it. This method
   makes sure that the min stack is also updated with appropriate minimum
   values */
void SpecialStack::push(int x)
{
    if(isEmpty()==true)
    {
        Stack::push(x);
        min.push(x);
    }
    else
    {
        Stack::push(x);
        int y = min.pop();
        min.push(y);
        if( x < y )
          min.push(x);
        else
          min.push(y);
    }
}
 
/* SpecialStack's member method to remove an element from it. This method
   removes top element from min stack also. */
int SpecialStack::pop()
{
    int x = Stack::pop();
    min.pop();
    return x;
}
 
/* SpecialStack's member method to get minimum element from it. */
int SpecialStack::getMin()
{
    int x = min.pop();
    min.push(x);
    return x;
}

LP · Answer

//Write a Stack class: push(),pop() methods without using  built-in pop() method. 
class Stack
{
private:
    int currSize;
    vector localStack;
    
public:
    Stack()
    {
        currSize = 0;
    }
    
    void push(int x)
    {
        localStack.push_back(x);
        currSize++;
    }
    
    void pop()
    {
        localStack.resize(currSize-1);
        currSize--;
    }
    
    int top()
    {
       return localStack[currSize-1];
    }
    
    bool empty()
    {
        return (currSize == 0);
    }
};

//MinStack class which contains a method that finds the minimal value of a stack using only push() and pop().
class MinStack: public Stack
{
public:
    int findMinimum()
    {
        Stack tmpStack;
        int min = INT_MAX;
        
        while(!this->empty())
        {
            tmpStack.push(this->top());
            if(this->top() top();
            }
            this->pop();
        }
        
        while(!tmpStack.empty())
        {
            this->push(tmpStack.top());
            tmpStack.pop();
        }
        
        return min;
    }
};

Bloomberg

Pregunta de entrevista de Bloomberg

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo