Search code examples
data-structuresstackheapheap-memorystack-memory

Are stack and heap memory actually implemented as stack and heap data structures?

I would like to know whether the stack and heap referred to in stack and heap memory are actually implemented as stack and heap data structures?

I think the stack is actually a stack that has pointers to the LIFO (Last In First Out) variables declared in functions however I wanted to confirm and also ask whether the heap shares more than just its name to the dynamic tree data structure that satisfies the heap property? I have read a lot recently on the stack and heap and believe I understand the concept however it then made me curious about the actual implementation. I imagine it could be different on different architectures too and there may not be a specific general answer for all computers and OS's.

In case anyone comes upon this question who is still unsure of what and where are the stack and heap please see this question and other links I found useful in learning the stack and heap concept.

What and where are the stack and heap? http://gribblelab.org/CBootcamp/7_Memory_Stack_vs_Heap.html http://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/ https://www.youtube.com/watch?v=_8-ht2AKyH4

Solution

  • The memory heap is decidedly not a heap data structure. That is, it's not a priority queue. I suppose you could use a priority queue heap to build a memory heap, but there are much better ways to do it.

    The stack is ... well ... Typically, the stack is a fixed block of memory allocated to the process. The processor itself treats that block of memory like a pure stack. That is, the processor's stack pointer points to the top of stack, and the push and pop instructions work as expected, adding things to and removing things from the stack. In that way, it's LIFO.

    However, the processor can do all manner of things with the stack: push and pop different sized things, address directly into it (i.e. view the third item without popping the first two), etc. So although the processor stack does have push and pop instructions, it also has much more extended functionality. I wouldn't call it a pure LIFO data structure.