Re: Stack vs. heap?

["mdj" <mdj.mdj@gmail.com>]

Don Bruder wrote:

> *KIND OF*...
>
> A stack always consists of same-sized units (usually, but not always,
> native machine-words) which get operated on atomically (at least from
> the high-level language programmer's perspective - The push and pull/pop
> operations on it may or may not actually be atomic at the machine
> language level, depending on the particular CPU and the routines that a
> given language uses to implement its stack) while a heap gets
> allocated/deallocated (by new/mark and release/dispose) in
> arbitrarily-sized, programmer specified chunks, and may or may not
> appear to be atomic to the programmer. A heap is much more like the
> linked list that you talk about later, in that it *CAN* be (not that
> doing so is a good idea under most circumstances, but the possibility
> exists when such a practice makes sense) randomly accessed, while a
> stack is *ALWAYS* LIFO.
>
> The Apple Pascal heap is "Stack-like", in that the "best practice" is to
> always balance your "new/dispose" or "mark/release" calls. However,
> doing so is *NOT* mandatory. With a stack, LIFO is the way it is -
> period. (barring excursions to machine language routines or similar that
> permit the programmer to manipulate the stack pointer "behind the
> compiler's back", so to speak. But then, we're no longer talking about
> "pure" Pascal.)

A much more concise explanation. Note however that the Apple Pascal
heap is composed of units of the same size - UCSD words. The new
operation merely decrements the heap pointer according to the number of
words needed for the particular data type being 'allocated'

The essential difference with the Apple Pascal heap from a stack is
that there is no 'pop' operation, only the means to move the stack
pointer backwards, so it's still a LIFO structure like a stack.

A common idiom is to mark the top of heap at the beginning of a
procedure, use up some storage then reset the top of heap pointer to
where it was at the beginning.

It should be noted that hardware stacks used by CPU's leave the stack
pointer public, such that the above operation can be performed for bulk
removal in addition to 'pop's which remove only one item. A given
machine may be able to operate on data items of various sizes, all of
which can be pushed onto the stack, so it's possible to have stacks
with various sizes.

Although strictly speaking a stack should be an opaque structure with
only two operations: push an item, pop the most recent item.

This point is often cited as an example of when you shouldn't use
inheritance for extension in an OO design - extending a collection type
and adding push and pop might be a simple way to get a stack, but it's
technically wrong, as the other operations on the data type are still
available via inheritance. In this case, delegation is the more
appropriate design decision.

> > Now if that's not confusing enough, this heap is not to be confused the
> > data structure called a heap, which is (generally) speaking a
> > specialised form of tree structure, such that a parent node is always
> > greater than, or equal to it's children. This is commonly used to
> > implement priority queues, or sometimes for sorting.
>
> That's a binary tree, not a heap. A binary tree is almost certainly
> implemented within the confines of the heap, but it is not, in and of
> itself, actually a heap. At best, it could be considered a "sub-heap" of
> the main program heap.

It's important to note that here I'm referring to a specific type of
data structure, called a heap, which is distinct from the 'heap' or
'heapspace'. Indeed such heaps are often (but not always) implemented
as a binary tree (a balanced binary tree qualifies as being a heap).
Micheal mentioned the primary usage of such a structure, being the
heapsort algorithm. These days, you'd probably use mergesort instead,
as it's easier to write parallelisable versions (merge takes advantage
of the fact that two already sorted lists can be very quickly merged).

There's a few good articles on Wikipedia that cover various heap data
structures, if you're interested.

Matt