You've seen stacks before. Stacks of books and papers cover your desk and stacks of plates sit in the cupboard (or maybe they're just stacked in the sink; we aren't judging). Grocery stores like to stack boxes of soda into pixel art. You can do a lot with a stack, whether you're trying to keep your dishes clean or want to keep your art school dreams alive while manning the checkout at Kroger.

In computer science, stacks are an abstract data type (ADT) somewhere between arrays and linked lists. Like all ADTs, a stack is a concept—not a concrete implementation. To implement it, you'll need either an array or a linked list "under the hood." If you turned either implementation on its head, you'd get a stack.

Sort-of. Data structures don't really have an orientation inside the computer, but it's easier to think about them that way.

 

Unlike linked lists, stacks don't need a pointer at both ends; they just need one at the very top. Any time you add a new element, you place it above the last one and make it the new top. Just like a stack in real life (minus the threat of toppling the entire thing).

You can still use a linked list to implement a stack, though. When working with stacks, just like when drawing cards from a deck (and not peeking like a cheater), you can only see one element at a time: the top of the stack. If you're using a linked list to implement it, all you need to worry about is the tail. That's where you're adding and removing things, making the head squarely on the side of unimportant until the tail and the head are the same element. If you want to implement a stack with an array, just set a pointer to the last element in the array.

This structure is just like any stack in the real world, whether it's a stack of dishes in the sink or the stack of textbooks in your room. Unless you're feeling daring with your family's fine china, the last item in a stack is the first one in, since it's at the top, making it a Last In, First Out (LIFO) data structure. You can also think of it as the first item being the last one out, making it a First In, Last Out Structure (FILO). Whenever you add to a stack, you're pushing that new element. When you take the top element, you're popping it from the stack.

 

Most computers have a max number of elements for any one stack. If you try to add to the top of the stack when there's no more space, you'll get a stack overflow error and your program will crash.

(Disclaimer: When people talk about the stack, they aren't talking about any old stack, they're talking about the stack that holds what current processes a programming language is running. Stack overflows can happen anytime the computer has too many processes on its stack to handle.)

Don't be that programmer who causes the stack overflow. You'll probably get put on dishwashing duty as some sort of ironic punishment.