One of the most useful properties of stacks is that they follow a last in, first out (LIFO) order. What every item was most recently pushed onto the stack is the first item that will be popped off.
This pattern is useful in many algorithms. One example we are already familiar with is the use of a stack to keep track of function calls in a program. When a function is called, information about the current state of the program is pushed onto a call stack. When the function returns, that information is popped off the stack to restore the previous state. This allows functions to be nested and called recursively while keeping track of where to return to. (See Section 5.5.)
Another common use of stacks is in undo functionality in applications. Each time a user makes a change, the previous state is pushed onto a stack. When the user wants to undo an action, the most recent state is popped off the stack and restored.
Stacks are also important in many parsing algorithms. For example, consider the task of deciding if the parentheses in a mathematical expression are balanced. We need to look at expressions like ((2 + 3) * (4 - 1)) and determine if every opening parenthesis has a corresponding closing parenthesis. We must not just have an equal number of open and close parentheses, but also want to make sure that the parentheses are properly nested, so that ( ( ) ) is valid but ( ) ) ( is not.
As an added challenge, maybe some of the pairs use different types of brackets, like { } or [ ], and you need to make sure they are all balanced and properly nested.
A stack is a perfect data structure to help with this problem. As we read through the expression from left to right, each time we see an opening parenthesis (or bracket), we push it onto the stack. Each time we see a closing parenthesis (or bracket), we check the top of the stack. If the top of the stack is the matching opening parenthesis, we pop it off the stack and continue. If it does not match, or if the stack is empty when we encounter a closing parenthesis, then the expression is not balanced. At the end of processing the expression, if the stack is empty, then all parentheses were balanced; otherwise, there are unmatched opening parentheses remaining.
We are parsing the parens in this expression: ([(5 - 1) + 3] * {4 - [6 + 2]}). What will the stack look like when we reach the 3? Put the block for the top of the stack first and the bottom of the stack last.
We are parsing the parens in this expression: ([(5 - 1) + 3] * {4 - [6 + 2]}). What will the stack look like when we reach the 6? Put the block for the top of the stack first and the bottom of the stack last.
