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 < 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

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->data = data;
tmp->link = top;
top = tmp;
}

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

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

bool isEmpty()
{

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   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   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> data;
data.resize();

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>>

• 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

StackExchange Code Review Q#54812, answer score: 10