Thread: Stacks?

This any good? http://en.wikipedia.org/wiki/Stack_%28data_structure%29

--
Mats

The "back" button on your Internet browser uses a stack. It's "last-in-first-out" (LIFO)... It starts at the most-recently visited page, and works backwards to the beginning. The stack starts-out empty. Every time you visit a new page, the web address of the page you are leaving is popped onto the stack, and the stack-pointer points to it.

Stacks are used internally by computers to store temporary data. It's kind-of hard to explain why... When a computer program calls a function, it needs to save a return pointer and the function may need some stack-space to save it's variables. If that function calls another function, more stack space is needed, and that data is added to the top of the stack.

When a function returns, its stack-space is no longer needed. The last-called function is the first to return... Everything goes in reverse order as the functions "unwind". The stack will grow and shrink as needed.

When it comes to applications, I'd say a queue (first-in-first-out = FIFO) is more common than a stack... When you write programs, you are more likely to need FIFO storage than LIFO storage. For example, when you send jobs to a printer, they are stored in a queue. When you are working with audio/video, the data is often stored in a FIFO buffer (a queue).

I was reading the tutorial page on stacks and well, to be frank, it was "bare".

Most tutorials are very brief. You may need to visit several websites to get the kind of detail and and explanation that you get in a 300 - 700 page beginning C++ book.

Most stack-explanations describe a stack of dinner plates. The important thing to remember is that you want the data written on the plate. You can only add or remove pates to the top of the stack. You normally write data as you "push" an additional plate onto the top of the stack, and you read the data as you "pop" the top-plate off of the stack. ...The analogy doesn't really hold-up that well, because you can manipulate the stack-pointer and access data in the middle of the stack.

@DougDbug: You shouldn't manipulate things in the middle of the stack in a proper stack-based implementation [I'm not talking about the call-stack in the processor here, where that sort of thing is very much the right way to behave].

@all:
Stacks are often used for implementing math expression evaluation, e.g. evaluate using standard mathematical precedence: 1 + 3 * 2 + 4 / 2. There are other ways to solve the same problem, but a stack does this nicely.

--
Mats