Is the stack in memory actually a stack?

In memory there is a section called stack that starts at the top and grows down towards the heap. Is this stack the same thing as a LIFO stack? Is the heap at the bottom a FIFO?

When you do "push" and "pop", does that alter the stack in memory?

Upvotes: 5

Answers (5)

user607139

Reputation: 356

It's a big pile of memory, but there is a stack pointer that points to the top of the stack. On push it goes up, on pop it goes down. But often you can cheat by just modifying the pointer, and that way you could get a value back that was already popped.

Not all architectures have the stack going in the same direction. In the end it doesn't matter at all. Some systems make the stackpointer increase on push, and decrease on pop, other systems decrease on push, and increase on pop.

Example: The stackpointer is at 0x100, and it's an increasing system. Then you push, and the stackpointer is at 0x104. You push again, at 0x108. You pop, back to 0x104. The other system would have started at 0x100, pushed down to 0xfc, then pushed down to 0xf8, and a pop back up to 0xfc. If you pop again, you're back at 0x100. If you then subtract 8 from the stackpointer, it's back to 0xf8, so you can pop them again. (Or, what a C-compiler would do at the end of a function, just add/subtract 12 from the stackpointer, rather than popping 3 local variables in 3 instructions.

Upvotes: 2

Nicholas Carey

Reputation: 74297

The "stack" you're talking about is the call stack of the program, so in that sense it is a stack. But there's no need for it to be: The actual implementation is hardware-, OS- and language runtime-specific — I've used C compilers where the call stack is implemented as a [doubly] linked list of stack frames, allocated on the heap, similar to how IBM mainframe OS's do things.

The drawback to the Intel/Windows style fixed-size hardware stack is that it makes the environment not very recursion-friendly. OTOH, it makes growing the stack very efficient since you're not having to use OS resources to allocation memory off the heap: it justs increments a pointer.

Upvotes: 1

Justin Ethier

Reputation: 134197

Yes, a LIFO stack is used by the computer architecture to store things such as return addresses, local variables, etc. From Wikipedia:

The x86 architecture has hardware support for an execution stack mechanism. Instructions such as push, pop, call and ret are used with the properly set up stack to pass parameters, to allocate space for local data, and to save and restore call-return points. The ret size instruction is very useful for implementing space efficient (and fast) calling conventions where the callee is responsible for reclaiming stack space occupied by parameters.

For example, when a function is called, the architecture pushes the return address, current register values, etc onto the stack. When the function returns, that data is popped off the stack so execution can resume at the previous location.

Upvotes: 3

Yochai Timmer

Reputation: 49261

The stack is in fact a LIFO stack.

It's created by the program itself while the program is running. The code that controls the stack is created at compilation time.

Farther reading:

Upvotes: 4

Reputation: 210545

I'm not sure what you mean by "actually a stack" (what's a "real" stack?) but it's conceptually the same thing: push decrements the "stack pointer", and pop increments it.

Upvotes: 1

Is the stack in memory actually a stack?

Answers (5)

Related Questions