One of those weirdo programming concepts university sophomore programming students eagerly avoid is the stack. It’s a type of storage with unique features, but it’s difficult to appreciate unless you understand its origins.
I’m sure most programming students pinch their nose, plow ahead, and hope that the stack torture is brief. That’s sad, because knowing what a stack is and how it works can help you understand and appreciate all programming languages.
The problem with the stack concept is that it’s beautiful only in machine language or its counterpart, Assembly. That’s how I learned about the stack. In fact, my knowledge is so rooted in Assembly language that I’m puzzled as to why any higher-level language would bother with the stack — beyond appreciating its features on a philosophical level.
Anyway.
A stack is storage. It’s a special form of storage that’s linear in nature, similar to an array. Items are added and removed from stack storage in a specific manner. This point is where a real world example becomes necessary.
Think of the stack as a bus. It has one door on the front. A queue of people enter the bus, one after another. The bus is small, so no one sits; they all stay in the queue. When people leave, the last person in is the first person off the bus. And if new people arrive, they push everyone else into the bus and only the last person to arrive can be the first person off the bus.
Weird, huh?
Another example, one that’s commonly used in stack descriptions, is a plate dispenser at a salad bar: New plates are pushed down onto the stack. Only the top plate is pulled or popped off the stack. And those terms, push and pop, are important. In fact, when you work with stack storage you encounter several terms:
Stack. This is the storage itself, which starts at a specific location, or base, in memory.
Stack Pointer. This variable holds the address of the last item stored on the stack.
Push. To add an item to the stack. The stack pointer variable is incremented and the item is saved at the stack pointer’s location.
Pop. The remove an item from the stack. The item is popped and the stack pointer variable is decremented. The term pull is also used, though it’s not as common.
LIFO. This acronym stands for Last In, First Out and it’s pronounced leaf-o. LIFO is how the stack works, similar to the bus or plate example. The last item pushed onto the stack is the first item popped off.
The stack does have an absolute size. So if you try to push an item onto a full stack you see a Stack Overflow error message. Likewise, you can’t pop an item from an empty stack.
These descriptions are easy enough to understand, but what’s the point? Why even bother with this type of strange storage? I’ll explain more new week, when I discuss how the stack plays a role in the computer’s processor. That’s truly where all the madness starts.