Why we have only two data structure "stack" and "heap"?
Why we have only two data structure "stack" and "heap"? like int value will be stored in stack and similarly reference type value will be stored in heap.
Why we cannot use some other data structure? Is there any specific reason to use only two these stack and heap.
Thanks a lot.
"The stack", and "the heap" in the context of memory allocation are not data structures. They're memory layout schemes, which can or cannot be implemented with stacks/heaps (respectively).
The existence of these 2 memory layout schemes stems from the need for two different kinds of memory:
Let's consider the 2 cases:
Static Memory Allocation
First, imagine if we were dealing with functions that only take parameters and input, and return some value as output, and use no local variables. There needs to be memory allocated that in some way stores the parameters before the function starts, and stores the return value after the function exists. The natural choice of data structure for this is a stack. Every time a new function is called, a new stack frame is allocated on a stack (called the runtime stack), to which the parameters are pushed. Whenever a function exists, its stack frame is popped off the stack, and its return is pushed, so that it can be read by its caller.
This scheme can be extended to support local variables. By definition, any variables that are "local" only exist for the duration of a function's lifetime. Because of this, they fit in very nicely, we can just allocate space for them in a function's stack frame.
This stack can be implemented in any number of ways, as a contiguous array, or a linked list, but ultimately it still acts as a stack, with the ability to only push/pop at the top. That constraint is acceptable because of the qualities of how functions and function calls works: - A function can't exit before all functions it calls have completed. As a consequence, there's no need to ever remove stack frames in positions aren't at the top of the stack. - Only the currently running function can make new function calls. As a consequence, there's no need to ever add stack frames in positions other than the top of the stack.
Dynamic Memory Allocation
Secondly, we have memory that that needs to be able to exist for some indefinite duration that's not bound to the lifetime of the function that defined it. This can be done in a plethora of ways. There could be a contiguous array that's split up and allocated in some way (which is ultimately how RAM works any way), it can be a linked list, or a tree structure. A heap happens to be a type of tree, but this is a coincidence. The term heap, as it pertains to dynamic memory allocation, is meant in the sense of a "bunch" or a "pile", a disorganized collection of things.
The Third Case
Doesn't exist, because there's no third option for memory lifetimes. They're either bound to a function's lifetime, or their not. A third memory allocation scheme would only exist if we had some third requirement that isn't covered by the first two cases.
Stack is a data structure. A heap is not a data structure. A stack can be created in the heap.
In fact, the way you appear to be describing them, they are MEMORY ALLOCATION schemes. Programming languages user a third mechanism: static allocation.
If you go behind the programming languages, a heap is just memory. A stack is just memory. The only thing that makes a stack a stack is that the memory is allocated last in last out. Any memory can be a stack.
It sounds like some elaboration is in order.
Executable and shared library files are actually programs that instruct the loader what to do. When you run a program, the executable file directs the loader to allocate pages of memory. This memory will usually be read only (static data), read/write (initialized program data), read/write demand zero (static data initialized to zero, and read/execute pages. One of blocks the executable directs to be creates is designated as the stack. The EXE instructs the loader to place the Stack Pointer register at (near) the top of this block.
Note that there is no heap when the program starts.
Once the program starts, memory managers are likely to execute. Usually there is only one in a program but it is possible to have multiple memory managers. These memory managers allocate read/write pages of memory that become heaps.
It is entirely possible for the application to use a memory manager to allocate a block of memory and then make that the program stack (rare, but it is common to allocate application stacks for various algorithms).
A stack is a generic data structure. The program stack is a stack that is managed by the stack pointer register. The stack itself is just a block of read/write memory.
A heap is just a block or read/write memory that is controlled by a memory manager. The memory manager will certainly impose a data structure on the heap but that structure is not visible to the application. All the application sees is that pages have been added to its address space.
There are then two levels of dynamic memory allocation.
Memory managers have to call #1 to service calls for #2. Generally one refers to memory allocated from memory managers as being "dynamic."
However, the pages loaded in an application can also be dynamic. While the program loader sets up the initial state of the application, the application can modify its page layout by allocating and freeing pages. In most systems, the application can even free pages created by the application loader (but that is likely to cause a crash).
Summing up: 1. The application can have read only, read/write (initialized or demand zero), and read/execute pages of memory. 2. Any page can be made the program stack (but it better be read/write). 3. One or more memory managers can allocate read/write pages and use them for heaps.
链接地址: http://www.djcxy.com/p/82840.html上一篇: 在JDK 8中删除PermGen