Stack. A very simple and easy to understand data type, and a great example for the beginning programmer. It is a type that is useful for introducing the concept of Abstract Data Types to a beginner, however to the more experienced programmer, Stacks can be even more useful.
Consider the problem of a calculator. We should all know how to program at least a simple one that can carry out basic operations along with those in any standard math library, however when parentheses are introduced the problem becomes more challenging.
This is just one of many uses for a stack. It can be used to implement Djikstra's Railway Algorithm for a more complex solution (Operator Precedence), or it can be used in a simpler case to parse the contents of the parentheses.
Consider (1 + 5) * 2.
If we use a stack, we can push the tokens in the expression onto it until we meet a close parentheses ')', At this point we can now pop all of the items in the stack until we reach the open parentheses '('. Now we can simply evaluate the expression, push the result back onto the stack and continue on, allowing us to simplify our problem.
Wether you're an experienced programmer, or a beginner, a stack can be a useful thing indeed.
No comments:
Post a Comment