Hi, I am currently trying to teach myself how to use stacks, queues, linked lists and binary trees (how to implement them myself from scratch first, that is, before I use what has already been provided for me in java.util.*).
I'm currently at the point where I can write stacks and queues and linked lists (and combinations of these), but I'm sort of going "so what?". I know that both stacks and queues are important, but I don't REALLY get it. Queues are used in transaction processing, that I can kind of see intuitively, but am less certain about stacks. I read something about their use in the handling/storage of data in registers during the running of recursive method calls, or during interrupt handling, but the whole thing sort of whooshed past over my head at a bit of a distance... What are the main usage areas of stacks in particular? Can someone dumb it down to my level? Now there's a challenge you probably hear every day...
A typical use of a stack would be an undo queue (yes, I know it sounds weird, the name "undo queue" while commonly used isn't really correct technically). Typically you'd want to undo the last action placed on the queue first. Another stack is the callstack of an application. The last function placed on it will be executed first. Or what about a car ferry that has only a single on/off ramp. If it's not properly loaded everyone has to drive off in reverse, the last car on will be the first car off (normally of course everyone is made to drive so they'll face forward on unloading, but some dockworkers aren't that smart).
A stack implements a LIFO mechanism, a queue a FIFO mechanism.
I haven't had to use stacks very often, but sometimes you have to do recursive things that need them. I have a little file processor that lets FileA say "Include FileB" and I insert FileB at that point. FileB might say "include FileC". I always need to know what file I'm processing right now, so I have a current file variable. When I start a new nested file, I push the current file onto a stack and set the variable to the new file. When I finish one file, I pop the previous file off the stack and make it current again.
If I had made my method call itself in conventional recursion, the compiler would take care of all that - push the current state of all local variables onto the stack and give me a fresh set, then pop them all off again when I return.
Does that help or confuse more?
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi