Stack, heap, and queue are ways that elements are stored in memory. Lets look at a queue first because that is similar to a line we would stand in at a bank to get a teller, or at a grocery store to check out. With a queue, the first one in is the first one out. The mnemonic FIFO is used to describe a queue (First-In-First-Out).
The program statement queue.add(element) might be used to store an element at the end of a queue. The program statement queue.remove() might be used to remove an item at the front of a queue. Note that the name of the item is not needed when you remove an item from a queue because only the item at the front of the queue can be removed.
a stack, elements are added to the "top" of the stack, and removed from the "top" of the stack. With a stack, the last one in is the first one out. The mnemonic LIFO is used to describe a stack (Last-In-First-Out). I used quotations around the term "top" above because stacks are built in reverse in memory, that is, the bottom of the stack has the highest address and a stack pointer decrements to add elements to the top of the stack.
The program statement queue.push(element) might be used to store an element in a stack. The program statement queue.pop() might be used to remove an element from a stack. Note that the name of the item is not needed when you remove an item from a stack because only the item at the top of the stack can be removed.
The most common use of a stack is when a function is called, its local variables are pushed on the top of the stack. If that function calls another function, its local variables are push on the top of that. As each sub-function is called, the stack grows. When each sub-function goes out of scope its local variables are popped off the stack. When the first function goes out of scope its local variables popped off the stack.
A heap is an area of memory where elements can be stored and removed in any order. Both a queue and a stack are usually used to store elements of the same size. This way a simple pointer or register can be incremented or decremented by the size of an element to store or retrieve an element. But a heap is usually used to store elements of different sizes. Storing elements of different sizes in any order requires much more complex algorithm.
| Object_ID | Address | Size | Date/Time | Priority |
Heap allocation algorithm might maintain a table to track the allocation of memory blocks. It would need to track the address of each element in the heap, the size of the element, the date/time that the element was stored, and the elements priority.
The date/time information would be used to determine if the element has any active processes pointing using it. Processes that have allocated memory on the heap are responsible for deallocating that memory once it's no longer needed. If it fails to do this, the process is said to have a memory leak. Memory blocks that don't have related active processes are considered to be garbage, and the process of deallocating the abandoned memory is referred to as garbage collection.
When blocks of memory in the heap are released, they are marked as free. Active processes may now allocate that memory. When a process needs memory in the heap, it searches through the allocation table for a block of memory marked free and large enough to meet its requirements. It may not find free block of memory large enough to meet its requirements.
A heap allocation algorithm might perform the maintenance task of moving memory around to combine many small blocks of free memory into one or more large blocks so that Active processes can find enough memory to meet their requirements. This called defragmenting.
If there is still insufficient free memory for a process to allocate the memory it needs, the heap allocation algorithm may compare the priority of the memory the process requests with the priority of block of memory in the allocation table. If it finds lower priority blocks of memory, it will deallocate those blocks, informing the owning processes that their memory has been deallocated, and reallocating those blocks to the higher priority process.
The program statement malloc might be used to store an element in a heap. The program statement free might be used to remove an element from a heap.
• Note: A data structure known as a "binary heap" has the form of a binary tree. Many sources state that a heap IS a binary tree. Not true.
Note: in general memory allocation the memory needed to meet a processes requirement is not required to be in one contiguous block. Any free memory blocks can be used, and each block will have a pointer to the previous block and a pointer to the next block. In this way the non-contiguous blocks can be daisy chained together. This is not very efficient and requires frequent defragmentation.
Learn more at amazon.com
More Computer Architecture Articles:
• The AMD Athlon 64 X2 Processor
• Introduction to Boolean Algebra
• Difference between Stack, Heap, and Queue
• Basic Computer Architecture
• Intel's Dual-Core Core i3 Processor
• Operating System Memory Allocation Methods
• Digital Logic Semiconductor Families
• Arduino Microcontroller Development Platform
• Round-Robin CPU Scheduling Algorithm
• Computer Buses