Implementation of a simple stack with min method The problem statement:


  Implement a stack which has push and pop method and also min method whereas min method has \$O(1)\$ complexity.


From an interview standpoint, what mistakes would you point out in terms of algorithmic design and other things?

#include &lt;iostream&gt;
#include &lt;string&gt;


template&lt;typename T&gt;
class stack
{
  private:
    struct stackNode
    {
       stackNode(T val) : val(val), next(nullptr) {}
       stackNode() {next=nullptr;} 
       T val;
       stackNode *next;
    };

  public:
    stack() { first = min = nullptr; sz = 0;}
    ~stack()
    {
      while(first) {
        stackNode *tmp = first-&gt;next;
        delete first;
        first = tmp;
      }
    }

    void print()
    {
      stackNode *tmp = first;
      std::cout &lt;&lt; "Stack =&gt; "; 
      while(tmp) {
        std::cout &lt;&lt; tmp-&gt;val &lt;&lt; ", "; 
        tmp = tmp-&gt;next;
      }
      std::cout &lt;&lt; std::endl; 
    }

    stackNode* push(T val, stackNode *head)
    {
      stackNode *tmp = new stackNode(val);
      tmp-&gt;next = head;
      return head;
    }

    void push(T val)
    {
      first = push(val, first);

      T tVal = val;
      if(min &amp;&amp; (min-&gt;val &lt; val)) {
        tVal = min-&gt;val;
      }
      min = push(tVal, min);
      sz++;
    } 

    size_t size()
    {
      return sz;
    }

    void pop()
    {
      if(first) {
        stackNode *tmp = first-&gt;next;
        delete first;
        first = tmp;

        //pop min temporary
        tmp = min-&gt;next;
        delete min;
        min = tmp; 
        sz--;
      }
    }

    T minimum()
    {
      if(min) {
        return min-&gt;val;
      }
      return T();
    } 

  private:
    stackNode *first, *min;
    size_t sz;
};

using myStack = stack&lt;int&gt;;

int main()
{
  myStack s;

  s.push(10);
  s.push(100);
  s.push(33);
  s.push(55);
  s.push(17);
  s.push(9);
  s.push(201);

  s.print();
  std::cout &lt;&lt; "Size of stack = " &lt;&lt; s.size() &lt;&lt; std::endl; 
  std::cout &lt;&lt; "Minimum = " &lt;&lt; s.minimum() &lt;&lt; std::endl; 

  s.pop(); s.pop();
  s.print();
  std::cout &lt;&lt; "Minimum = " &lt;&lt; s.minimum() &lt;&lt; std::endl; 

  s.pop(); s.pop();
  s.print();
  std::cout &lt;&lt; "Minimum = " &lt;&lt; s.minimum() &lt;&lt; std::endl; 

  return 0;
}
It all depends how much time you had to do this, overall it looks ok. In a couple of places you are initializing in the body of the constructor rather than using the initializer list, that is if nothing somewhat inconsistent but you should be using the initializer list in all of these cases. Also the way you use it, the stackNode constructor might as well take the next pointer, this way you don't forget to set it. I might try and get you to figure that out via questions about the constructor. 

There is no way to get to value of the top of the stack, pop doesn't return it, neither is there a top() function that would return the top value. 

I'd probably also would like to see an error condition rather than the default constructed value being returned for minimum() and pop(). It's worse for minimum because you are returning a valid value e.g. int() for an empty stack, i.e. calling minimum() on an empty stack&lt;int&gt; will return 0. That is just plain wrong therefore a bug. 

I'd probably ask you why you consider min a temporary, this is from the comment in pop() just to clarify language. 

stackNode* push(T val, stackNode *head) should be private

Algorithm wise it looks like a reasonable solution, depending on how the inteview goes i might ask you follow up questions, e.g. could you come up with a solution that doesn't need two separate stacks, these days I'd also ask you how to make this datastructure thread safe. I might ask what requirements there are to type T and what might happen if they aren't fulfilled. Maybe again depending how the interview goes, how to extend the stack to allow classes that don't fulfill the requirements to still used for the stack.