Chapter 7: Stacks Using Linked Lists


Football fans know that piling on after the whistle will penalize the team (although advertisers love it because it gives broadcasters time to run a few commercials while the officials pull players off the pile). If you are not football fan, piling on is the unofficial football term for players jumping on other players during a tackle. If you are a programmer, piling on is the unofficial computer term for a stack. You learned about stacks back in Chapter 4 when you discovered how to use an array to create your own stack. However, using arrays presents a problem: you cannot adjust the size of the stack when the program runs. The solution? Use a linked list to create a stack. You learned about linked lists in general in the last chapter. In this chapter, you ll learn how to use a linked list to create a stack.

A Stack

As you ll recall from Chapter 4, a stack is a data structure that organizes data similar to how you organize dishes in a stack on your kitchen counter. The newest dish is on top and the oldest is on the bottom of the stack.

When accessing dishes,  the last disk on the stack is the first dish removed from the stack. If you want the third dish, you must remove the first two dishes from the top of the stack first so that the third dish becomes the top of the stack and you can remove it. There is no way to remove a dish from anywhere other than the top of the stack. You d need to use a different kind of data structure (or stacking system) if you wanted to randomly access dishes.

A stack is useful whenever you need to store and retrieve data in last in, first out order. For example, your computer processes instructions using a stack in which the next instruction to execute is at the top of the stack.




Data Structures Demystified
Data Structures Demystified (Demystified)
ISBN: 0072253592
EAN: 2147483647
Year: 2006
Pages: 90

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net