Applications of Stacks

APPLICATIONS:

Direct applications:

• Balancing of symbols
• Infix-to-postfix conversion
• Evaluation of postfix expression
• Implementing function calls (including recursion)
• Finding of spans (finding spans in stock markets, refer to Problems section)
• Page-visited history in a Web browser [Back Buttons]
• Undo sequence in a text editor
• Matching tags in HTML and XML 

Indirect applications:

• Auxiliary data structure for other algorithms (Example: Tree traversal algorithms)
• Component of other data structures.

GENERAL PROGRAMMING APPLICATIONS:

• Useful for expression evaluation.
• Useful to check parenthesis matching in an expression.
• Useful for Conversion from one form of expression to another.
• Useful for Memory Management.
• Useful in backtracking problems

 

Expression Evaluation:

The Stack can be used for the evaluation of an arithmetic expression if used with a properly optimized algorithm with the implementation of a stack.

For example, consider the following expression :

5 * ( 6 + 2 ) - 12 / 4 

Since parenthesis has the highest precedence(priority) among the arithmetic operators,

( 6 +2 ) = 8 will be evaluated first.

Now, the expression becomes:

5 * 8 - 12 / 4

*(multiply) and /(divide) have equal precedence and their associativity is from left-to-right. So, start evaluating the expression from left-to-right.

5 * 8 = 40 and 12 / 4 = 3

Now, the expression becomes : 40 - 3 

And the value returned after the subtraction operation is 37.

Parenthesis Matching

Given an expression, you have to find if the parenthesis is either correctly matched or not. For example, consider the expression ( a + b ) * ( c + d ).

In the above expression, the opening and closing of the parenthesis are given properly and hence it is said to be a correctly matched parenthesis expression. Whereas, the expression, (a + b * [c + d ) is not a valid expression as the parenthesis are incorrectly given. 

Expression Conversion

stacks can be used to evaluate different expressions such as infix to postfix or prefix.

Memory management

The assignment of memory takes place in contiguous memory blocks. We call this stack memory allocation because the assignment takes place in the call stack of function. The size of the memory to be allocated is made to be known to the compiler. When a function is called, its variables get memory allocated on the stack. When the function call is completed, the memory for the variables the allocated place is released. All this happens with the help of some predefined protocols and routines in the compiler. The user does not have to worry about memory allocation and release of stack variables.

The memory to be allocated to these variables is known to the compiler and when the function is called, the allocation is done and when the function terminates, the memory is released.

Consider the following code snippet:

int main( )

{

// All these variables get memory

// Allocated on stack

int f;

int a[10];

int c = 20;

int e[n];

}

Backtracking Problems

Analyze N-Queen's problem as an example. The solution to this problem is that some number of queens must be positioned on a chessboard in such a manner that none of the queens can attack another queen in a consequent step. In the generalized N-Queens problem, N represents the number of rows and columns of the board and the number of queens that must be placed in safe positions on the board.

The basic strategy we will use here is to solve this problem is to use backtracking. In this case, backtracking signifies that we will perform a safe move for a queen at the time we make the move. Later, however, if we may find that we are stuck and there is no safe movement for the next Queen, whom we are trying to put on the chess-board, so we have to go back.

We will use the stack data structure to remember where we placed queens on the board, and if we need to make a backup, the queen at the top of the stack will be popped, and we will use the position of that queen to resume the search for next safe location.