Implementing stack without dynamic memory allocation

Question

struct Node {
    int value;
    Node *n;
};

void push (Node *front, int value) {
    Node new;
    new.n = front;
    new.value = value;
    Node *newPtr = &new;
    front = newPtr;
}

int pop (Node *front) {
    int n = front->value;
    front = front->n;
    return n;
}

I tried to implement stack without dynamic memory allocation this way, but I failed to make it work. Any hints on what I should be doing to make it work?

You need to provide [a Minimal, Complete, and Verifiable example (MCVE)](http://stackoverflow.com/help/mcve) along with a description of what exactly did not work, including exact error message text and locations wherere they appear. — Ivan Aksamentov - Drop, Feb 22 '16 at 04:27
@Drop As pop function wasn't working (front node would not disappear), I assumed the design itself was already incorrect from the beginning. — Haxify, Feb 22 '16 at 04:31
Without MCVE my guesses: (1) `new` it is a reserved keyword in C++, you cannot use it as identifier name, (2) after `push()`, `front` is pointing to a temporary object that is destroyed when `push()` exits — Ivan Aksamentov - Drop, Feb 22 '16 at 04:31
Again, "not working" is not a constructive problem description. We will not be able to help you this way. — Ivan Aksamentov - Drop, Feb 22 '16 at 04:32
@Drop Oh that is my bad; I just used simple arbitrary variable name for this question only. I didn't actually use the name "new" in my program. — Haxify, Feb 22 '16 at 04:32
I'm really sorry; the second point you suggested seems to be the problem. What can I do to fix that? — Haxify, Feb 22 '16 at 04:33
@Drop The code I used is exactly identical to the one I posted, except different variable names. — Haxify, Feb 22 '16 at 04:34
First, you would probably want to pick a good book on C++: [The Definitive C++ Book Guide and List](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Ivan Aksamentov - Drop, Feb 22 '16 at 04:37
Second, there are zillion of ways of implementing stack. Linked list implementation is hard to get right without heap memory, so you should think about some other possible implementations. For example, array-based contiguous implementation. Don't hesitate to Google, make some research. It's not that hard. Later you can return back to this question and post an answer yourself, so someone else might use this information in the future. — Ivan Aksamentov - Drop, Feb 22 '16 at 04:40
Possible duplicate of [Can a local variable's memory be accessed outside its scope?](http://stackoverflow.com/questions/6441218/can-a-local-variables-memory-be-accessed-outside-its-scope) — Raymond Chen, Feb 22 '16 at 04:44

Rob L · Answer 1 · 2016-02-22T04:44:01.520

0

You are taking the address of a temporary variable. In push, you make a local variable 'new', take the address of it, then when the function exits that's an invalid pointer.

You need to use dynamic memory allocation for this task if your solution is going to be robust.

edited Feb 22 '16 at 04:44

answered Feb 22 '16 at 04:41

Rob L

2,351
13
23

The topic name is: "Implementing stack *without* dynamic memory allocation" – Ivan Aksamentov - Drop Feb 22 '16 at 04:42
Yes.... but the program isn't up to that task. Sometimes the answer is pointing out that you shouldn't do that. (An option would be to use a different data structure, a fixed array or something, but he clearly has a linked list structure.) – Rob L Feb 22 '16 at 04:44
Well, stack *can* be implemented without heap. Robustly. And the answer is to not use linked list as underlying data structure or to use stack-buffer-based allocator. – Ivan Aksamentov - Drop Feb 22 '16 at 04:46

Implementing stack without dynamic memory allocation

1 Answers1