Stack and application of stack

31 December 2019

let’s start with Stack and application of stack. First start with introduction to stack then go to the application of stack.

Introduction to stack

A stack is a linear structure in which items may be added or removed only at one end. Everyday examples of such a structure are a stock of dishes, a stack of pennies, a stack of disks and a stack of folded cloths. We can observe that an item may be added or removed only from the top of the stack. It means that the last item to be added to a stack is the first item to be removed. Stacks are also called last in first out (LIFO) lists.

In stack, an element may be inserted or deleted only at one end called the top of the stack. It means that the elements are removed from a stack in the reverse order of that in which they were inserted into the stack.

Special terminology is used for two basic operations(push, pop) associated with stacks.

  1. PUSH: The process of inserting an element into a stack is known as a push.
  2. POP:  The process of deleting an element from a stack is known as pop.
working of a Stack

Two conditions can exist for a stack that is overflow and underflow:

Overflow: Overflow occurs when a stack is full in spite of that we try to push an item into a stack.

Underflow: It occurs when a stack is empty, we try to pop an element from a stack.

Algorithm to push an element into a STACK:

PUSH( STACK, TOP, MAXSTK, ITEM )

(This algorithm inserts an element ITEM in the STACK. TOP is an element or pointer that indicates the top position of the stack and MAXSTK is the no of elements that can be placed in the stack.)

  1. [Check for overflow] If TOP > = MAXSTK-1 then Printf (“ overflow “) and EXIT
  2. [Increase the TOP] Set: TOP = TOP + 1
  3. [Push the element] STACK [TOP] = ITEM
  4. [Finish]End.

Algorithm to pop an element from a STACK:

POP ( STACK, TOP, ITEM )

(This algorithm deletes the top element of the STACK and assigns it to the variable ITEM. TOP is the pointer that indicates the top position of the stack.)

  1. [Check for underflow] If TOP < 0 then Print (“Underflow “) and EXIT.
  2. [Pop the element] ITEM = STACK [TOP]
  3. [Decrease the TOP] Set: TOP = TOP – 1
  4. [Finish] End.

Application of stack

There are a number of applications of stacks; three of them are discussed briefly in the preceding sections. A stack is internally used by the compiler when we implement (or execute) any recursive function. If we want to implement a recursive function non-recursively, a stack is programmed explicitly. A stack is also used to evaluate a mathematical expression and to check the parentheses in an expression.

1. RECURSION

Recursion occurs when a function is called by itself repeatedly; the function is called a recursive function. The general algorithm model for any recursive function contains the following steps:

  1. Prologue: Save the parameters, local variables, and return address.
  2. Body: If the base criterion has been reached, then perform the final computation and go to step 3; otherwise, perform the partial computation and go to step 1 (initiate a recursive call).
  3. Epilogue: Restore the most recently saved parameters, local variables, and return address.

It is difficult to understand a recursive function from its flowchart, and the best way is to have an intuitive understanding of the function. The key box in the flowchart contained in the body of the function is the one, which invokes a call to itself. Each time a function call to itself is executed, the prologue of the function saves necessary information required for its proper functioning.

2. EXPRESSION

Another application of stack is the calculation of postfix expression. There are basically three types of notation for an expression (mathematical expression; An expression is defined as the number of operands or data items combined with several operators.)

  1. Infix notation
  2. Prefix notation
  3. Postfix notation

The infix notation is what we come across in our general mathematics, where the operator is written in-between the operands.

For example, the expression to add two numbers A and B is written in infix notation as A + B

Note that the operator ‘+’ is written in between the operands A and B.

The prefix notation is a notation in which the operator(s) is written before the operands, it is also called polish notation in the honor of the Polish mathematician Jan Lukasiewicz who developed this notation.

The same expression, when written in prefix notation, looks like + A B

As the operator ‘+’ is written before the operands A and B, this notation is called prefix (pre means before).

In the postfix notation, the operator(s) are written after the operands, so it is called the postfix notation (post means after), it is also known as suffix notation or reverse polish notation.

The above expression if written in postfix expression looks like: A B +

The prefix and postfix notations are not really as awkward to use as they might look.

For example, a C function to return the sum of two variables A and B (passed an argument) is called or invoked by the instruction: add (A, B)

3. To record the sequence of all the pages browsed in one session.

4. To implement the undo function in a text editor.