Stacks & Stack Terminologies:

Stacks & Stack Terminologies:

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

Special terminology used for two basic operations associated with stack:

1. Push:  is the term used to insert an element into a stack.
2. Pop:  is the term used to delete an element from a stack.
   

Array representation of Stacks:

Stack may be represented in the computer memory in various ways. Usually by means of one way list or a linear array. Stack will be maintained by linear array STACK. A pointer variable TOP, which contain the location of the top element of stack. And a variable MAXSTK which gives the maximum number of elements that can be held by the stack. The condition TOP= 0 or TOP=NULL will indicate the stack is empty.

Figure shows the array representation of stack. Since top = 3, the stack has three elements, XXX, YYY and ZZZ; and since MAXSTK=8, there is a room for five more elements in stack.

The operation of adding an element on to a stack and the operation of removing an element from the stack may be implemented, respectively, by the following procedure called push and pop.

In executing the procedure push, one must first check whether there is a room in the stack for the new item; if not, then we have the condition known as overflow.  Analogously, in executing the procedure pop, one must first test whether there is an element in the stack to be deleted; if not then we have the condition known as underflow.

Algorithm: PUSH (STACK, TOP, MAXSTK, ITEM)

This procedure Push an item onto a stack.

1.    [Stack already filled?]

If TOP= MAXSTK, then: print: OVERFLOW, and Return. 

2.    Set TOP:=TOP+1 [Increase TOP by 1]

3.    Set Stack [TOP]:=ITEM [Insert ITEM in new TOP position.]

4.    Return

Algorithm: POP (STACK, TOP, ITEM)

     This procedure Delete an item from a stack.

1.    [Stack has an item to be removed?]

If TOP= 0, then: print: UNDERFLOW, and Return. 

2.    Set ITEM :=STACK [TOP]  [Assign TOP element to ITEM.]

3.    Set Top: TOP-1. [Decrease TOP by 1.]

4.. Return

Polish notation:

In most common arithmetic operations, the operator symbol is placed between its two operand. 

For example, 

 A+B, C-D,    E*F,    G/H

This is called as infix notation.

Polish notation refers to the notation in which the operator symbol is placed before it's two operands also called as prefix notations.

For example, 

                                    +AB,   -CD,    *EF,    /GH

Translate following in this expression into polish (prefix) notation:

1. (A+B)*C=[+AB]*C=*+ABC
2. A+(B*C)=A+[*BC]= +A*BC
3. (A+B)/(C-D)=[+AB]/[-CD]=/+AB-CD

Reverse polish notation (postfix notation) refers to the analogous notation in which the operator symbol is place after two operand.

For example, 

                                    AB+,   CD+,   EF+,    GH+

Evaluation of Postfix Expression:

 

Suppose P is an arithmetic expression written in postfix notation.  The following algorithm, which uses a stack to hold the operands, evaluates P. 

Algorithm:  This algorithm finds the value of an arithmetic expression P written in postfix notation.

1. Add a right parentheses “)” at end of P. [This acts as a sentinel]
2. Scan P from left to right and repeat step 3 and 4 for each element of P until the sentinel is encountered.
3. If an operand is encountered, put it on STACK.
4. If an operator is encounter, then:

a)    Remove the top two element of stack, where A is the top element and B is the next top element.

b)    Evaluate  B X A

c)    Place the result of (b) back on STACK

        [End of if structure]

    5. Set VALUE equals to the top element on STACK

              6. Exit

Consider the following arithmetic expression P written in postfix notation:

                     P:        5,         6,         2,         +,         *,          12,       4,         /,          -

 Equivalent infix expression of Q follows:

                     Q: 5*(6+2)-12/4

 We evaluate P by simulating the above algorithm.  First we add a sentinel right parenthesis at the end of P to obtain

              P:        5,         6,         2,         +,         *,          12,       4,         /,          -

(1)       (2)       (3)       (4)       (5)           (6)       (7)       (8)       (9)

The elements of P have been labelled from left to right for easy reference.  Following figure shows the content of stack as each element of P is scanned, the final number in the stack is ,37,  which is assigned to the value when the sentinel “)” is scanned, is the value of P.