Stack is an ordered list in which all insertions & deletions are made at only one end, called Top. It operates in principle of last-in-first-out (LIFO) which means the items inserted at last is removed first. For example, if the elements A,B,C and D are inserted in to the stack in the same order then the removal of all elements will be in the reverse order (D,C,B and A).

Operations performed on Stack

• Create: to create a new empty stack
• IsEmty: to check whether the stack is empty or not
• IsFull: to check whether the stack is full or not
• Push: to insert an item in the stack at top
• Pop: to remove the topmost item
• Peak: to get the topmost item without removing it from the stack
• Itemcount: to count the number of items available in the stack

Applications of Stack – Function Calls

Stacks are applied in many areas in computer programming. Processing of function calls and their returns is a good example for applications of stack. If a function required to be executed, first it should be loaded in the memory. Assume that a function fun2() is being called by another function fun1(), when the execution of fun2() is completed, the execution point should return to the statement in the fun1() which immediately follows the function call to fun2(). Similarly, during the execution of fun2() if it calls another function fun3(), the execution point should return to the statement which immediately follows the function call to fun3()

The following figure demonstrates this,

Procedure calls

When fun2() is being called all the information pertained to fun1() (flow, flags, return address, etc.,) will be pushed into the stack. Similarly, when fun3() is being called information pertained to the function fun2() will be pushed into the stack. So, when fun3() returns the information set related to fun2() will be popped out first, then information pertained to fun1() (when fun2() returns).

Applications of Stack – Evaluation of Arithmetic Expressions

Another good example for applications of stack is evaluation of arithmetic expressions in computer programming. It’s all easy for us to evaluate the arithmetic expressions based on the priorities of operators and parentheses but not for computers. For example, consider the following expression,

T = A / B ^ C + D * E – A * C

Different operators have different priorities. Dividing A by B and raising the result’s power to C is totally different from dividing the A by the result of B’s power raised with C. Full use of parentheses, we can avoid the incorrect sequences but the occurrences of parentheses still give problem to the computer instructions to identify the reasonable instruction sequence because computers do not understand the information other than numerals and operators.

All the above circumstances lead us to provide the solution to evaluation of arithmetic expressions through converting the infix form of them to postfix. The following are the steps used to convert an expression from infix to postfix,

• Fully parenthesize the expression (for example the above expression can be parenthesized as follows),
  (((A / (B ^ C)) + (D * E) – (A – C))
• Replace all closing parentheses with their corresponding arithmetic operators
  
• Delete all parentheses.

Sometime, when the un-parenthesized sequence is encountered, the conversion cannot be done. With the help of stack and priority of each operator known, we can convert the expression to its postfix form.

There are two priority considerations for any operator, viz., incoming priority (when it’s being read from the expression) and the in-stack priority (when it’s being available in the stack). The following is the table which depicts the priority of mostly used operators.

The algorithm is very simple,

• When an operand is being read, it will be printed directly in to the output stream
• when and closing parenthesis ‘)‘, stack contents will be popped and printed in the output stream until a closing parenthesis is popped from stack
• when other operators read from the expression, in-stack priority of stack top will be compared with the incoming priority of incoming operator from input expression, if stack top operator’s priority is greater it will be popped out and printed in output stream and incoming operator will be pushed into the stack, otherwise incoming operator will be simply pushed into the stack.

The steps above will be repeated until all the tokens are read the input expression.

Will be continued…