Data Structure - [STACK Applications]

♠ Posted by Unknown in Data Structure at 03:51

Applications of STACK

There are three applications in which stacks are used. The first application deals with recursion. Recursion is an important facility in many programming languages such as ALGOL 60 and PASCAL. There are many problems whose algorithmic description is best described in a recursive manner.

The second application of a stack is classical; it deals with the compilation of infix expressions into object code.

The third application of a stack is stack machine. Certain computers perform stack operations at the hardware or machine level, and these operations enable insertions to and deletions from a stack to be made very rapidly.

      Recursion:

The natural numbers have been defined recursively through the process of induction. Recursion is the name given to the technique of defining a set or a process in terms or itself.

The factorial function, whose domain is the natural numbers, can be recursively defined as,

Here the FACTORIAL(N) is defined in terms of FACTORIAL(N-1), which in turn is defined in terms of FACTORIAL(N-2), etc. until finally FACTORIAL(0) is reached, whose value is given as “one”. The basic idea is to define a function for all its argument values in a constructive manner by using induction. The value of a function for a particular argument value can be computed in a finite number of steps using the recursive definition, where at each step of recursion we get nearer to the solution.

Classical (Polish Expression and Their Compilation) :

In this section we shall primarily concerned with the mechanical evaluation or compilation of infix expressions. We shall find it to be more efficient to evaluate an infix arithmetical expression by first converting it to a suffix expression and then evaluating the latter. This approach will eliminate the repeated scanning of an infix expression in order to obtain its value.

Stack Machines:

One of the main problems with using machines which have a  very limited number of registers is how to handle the storage of intermediate results. In particulars, we must be very cognizant of the generation of wasted store/load instruction sequences. In this sections we illustrate how the presence of the simple stack operations of POP and PUSH can enhance the process of generating code from a reverse-polish string. The instructions available for this machine are given in mnemonic form as follows:

1.      PUSH<name> - Load from memory onto stack. This instructions loads an operand from the memory location named <name> and places the contents of <name> on the stack.

2.      POP <name> - Store top of stack in memory. The contents of the top of the stack are removed and stored in the memory location referenced by <name>.

3.      ADD, SUM, MUL, DIV – Arithmetic operation.