Difference between Stack, Heap, and Queue
By Stephen Bucaro
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.
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.