Stack introduction

Stack applications in data structure 

Following are some of the important applications of a Stack data structure:

1. Stacks can be used for expression evaluation.
2. Stacks can be used to check parenthesis matching in an expression.
3. Stacks can be used for Conversion from one form of expression to another.
4. Stacks can be used for Memory Management.
5. Stack data structures are used in backtracking problems.

 

Expression Evaluation

Stack data structure is used for evaluating the given expression. For example, consider the following expression

5 * ( 6 + 2 ) - 12 / 4

Since parenthesis has the highest precedence among the arithmetic operators, ( 6 +2 ) = 8 will be evaluated first. Now, the expression becomes 

5 * 8 - 12 / 4

* and / 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

Converting one form of expressions to another is one of the important applications of stacks.

• Infix to prefix
• Infix to postfix
• Prefix to Infix
• Prefix to Postfix
• Postfix to Infix
• Postfix to Infix

 

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 function call stack. The size of the memory to be allocated is 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 is released. All this happens with the help of some predefined routines in the compiler. The user does not have to worry about memory allocation and release of stack variables.

Consider the following snippet:

int main() 
{ 
   // All these variables get memory 
   // allocated on stack 
   int f; 
   int a[10]; 
   int c = 20; 
   int e[n]; 
} 

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.

Backtracking Problems

Consider the N-Queens problem for an example. The solution of this problem is that N queens should be positioned on a chessboard so that none of the queens can attack another queen. In the generalized N-Queens problem, N represents the number of rows and columns of the board and the number of queens which must be placed in safe positions on the board.

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

This means we return to the queen's previous move, undo this step, and continue to search for a safe place to place this queen.

We will use the stack 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.

Hence, stacks can be used for the allocation of memory for most of the backtracking problems.