- Push - Stack overflow
- Top – one end
- Pop – underflow
Complexity :
Each operation 0(1)
Applications :
Parsing (Balancing symbols)
An important application of stacks is in parsing. For example, a compiler must parse arithmetic expressions written using infix notation. For example the following infix expression evaluates to 212.
| ( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) ) |
| |
Evaluating a postfix expression. A postfix expression is....
| 2 3 4 + 5 6 * * + |
First, we describe how to parse and evaluate a postfix expression. We read the tokens in one at a time. If it is an integer, push it on the stack; if it is a binary operator, pop the top two elements from the stack, apply the operator to the two elements, and push the result back on the stack.
Converting from infix to postfix. Now, we describe how to convert from infix to postfix. We read in the tokens one at a time. If it is an operator, we push it on the stack; if it is an integer, we print it out; if it is a right parentheses, we pop the topmost element from the stack and print it out; if it is a left parentheses, we ignore it.
Function calls.(Recursion) Perhaps the most important application of stacks is to implement function calls. Most compilers implement function calls by using a stack. This also provides a technique for eliminating recursion from a program: instead of calling a function recursively, the programmer uses a stack to simulate the function calls in the same way that the compiler would have done so. Conversely, we can often use recursion instead of using an explicit stack. Some programming languages provide a mechanism for recursion, but not for calling functions.
Programming languages have built in support for stacks (recursion), but no analogous mechanism for dealing with queues.
