Stack challenge - improving memory consumption I am working on this problem:


  Stacks
  
  Imagine, that you are employed by a software development company. You
  work now on the famous "D++ project", which is devoted to the creation
  of a new generation programming language. Your particular task is
  quite prosaic, though. You are to develop the memory manager being
  able to work with a large number of stacks.
  
  Input
  
  The first line of the input contains the total number of stack
  operations \$N\$, \$0 &lt; N ≤ 100000\$. Each of the next \$N\$ lines contains a
  description of a stack operation, either in the form PUSH A B (meaning
  to push B into stack A), or in the form POP A (meaning to pop an
  element from stack A), where A is the number of stack (\$1 ≤ A ≤ 1000\$),
  and B is an integer (\$0 ≤ B ≤ 10^9\$). You may assume, that every
  operation is correct (i.e., before each POP operation, the respective
  stack is not empty).
  
  Output
  
  For each POP operation, described in the input, output the value,
  which this POP operation gets from the top of that stack, to which it
  is applied. Numbers should appear according to the order of the POP
  operations in the input. Each number should be output in a separate
  line.


I have developed a solution here:   

#include&lt;map&gt;

class MyStack
{
    public:

      int data;
      MyStack *link;
      MyStack *top;

      MyStack()
      {
          link = NULL;
          top = NULL;
      }

      void push( int data )
      {
           MyStack * tmp = (MyStack *) malloc( sizeof( MyStack ) );
           tmp-&gt;data = data;
           tmp-&gt;link = top;
           top = tmp;
      }

      void pop()
      {
          MyStack *tmp = top;
          top = top-&gt;link;
          printf( "%d\n", tmp-&gt;data );
          free( tmp );
      }

      void clear()
      {
          while( top != NULL )
          {
              MyStack *tmp = top;
              top = top-&gt;link;
              free( tmp );
          }
      }

      bool isEmpty()
      {
           return top == NULL;
      }
};


int main()
{
    static MyStack* stackPtrs[1001];

    int noOfInstructions = 0;
    scanf( "%d", &amp;noOfInstructions );

    char instruction[3];
    short stackNumber = 0;
    int stackValue = 0;
    for( int inx = 0; inx &lt; noOfInstructions; ++inx )
    {        
        scanf("%s", &amp;instruction );    

        scanf( "%hd", &amp;stackNumber );

        if( instruction[1] == 'U' )
        {          
            scanf( "%d", &amp;stackValue );

            if( stackPtrs[stackNumber] == NULL )
            {              
                MyStack *myStack = new MyStack();
                myStack-&gt;push( stackValue );
                stackPtrs[stackNumber] = myStack;
            }
            else
            {
                stackPtrs[stackNumber]-&gt;push( stackValue );
            }
        }
        else
        {
            stackPtrs[stackNumber]-&gt;pop();
            if( stackPtrs[stackNumber]-&gt;top == NULL )
            {
                stackPtrs[stackNumber] = NULL;
            }
        }
    }

    for( int inx =0; inx &lt; 1001; ++inx )
    {
         if( stackPtrs[inx] != NULL )
         {
             stackPtrs[inx]-&gt;clear();
             stackPtrs[inx] = NULL;
         }
    }
    // Clear memory allocated here!.


    return 0;
}


The memory limit for this question is around 0.75MB = 750KB. My program, out of 20-30 runs on an average is taking around 800KB, with 770KB being the least time. 

Please suggest any improvements to this program.
My main problem is that you are dynamically allocating all objects with new and or malloc. In C++ object can be created locally without new just by declaring them in the local scope.

MyStack   stack;      // Creates and initializes a MyStack object.


MyStack   data[10];   // Create and initialize an array of MyStack objects.


See no need to call new at all most of the time.

The second problem is that you are using malloc. This is C memory management. The blocks are not necessarily in the same areas as memory allocated by new and thus not compatible to be deleted by either. Also they don't run the constructor and free will not run the destructor. So a very bad idea.

The third observation is that you are building a container (linked list). There is already a built-in linked list.

std::list&lt;int&gt;   data;


For this structure of a stack. The list is not the optimal data structure. A std::vector or std::deque is probably better. But we have a built-in std::stack which is actually a container adapter that wraps another container type (by default it uses std::deque).

std::stack&lt;int&gt;   data;  // This is probably your best option
                         // for holding data.


If you want multiple stacks. I would just create a std::vector of stacks that you can the size at runtime to get all the stacks you need.

std::vector&lt;std::stack&lt;int&gt;&gt; data;
data.resize(&lt;Number-Of-Stacks-You-Need&gt;);


That should solve your memory problems.

Looking at your code we could go into your design of MyStack (but I think that is superflous). But some common rules:


Don't use C facilities when better C++ ones exist.
scanf() => operator&gt;&gt;
Don't mix dynamic memory allocation.
Only use new and delete in C++ code.
Every call to new should be matched with a call to delete
But you should not even do that normally:
a. Use local object most of the time.
b. Use containers when you have groups of objects.
c. When you really need dynamic allocation use smart pointers.
Learn the Rule of 3