Stack in Data Structure

Table of Contents

Stack in Data Structure

It is a linear data structure in which

  • Data is inserted and deleted at same end called top of stack.
  • Data is stored and retrieved by LIFO (Last In First Out) This means, that elements are removed from a stack in the reverse order of that in which they were inserted into the stack.

Two basic operations associated with stack are:

  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.

  • In case of insertion of new element in a stack, a condition of overflow should be avoided. This means when the array is full and an attempt is made to push yet another element onto the stack. The result of such an attempt is called an overflow.
  • In case of deletion, condition of the underflow should be avoided. This means that stack contains no element and an attempt to perform pop operation is done. The result of such an attempt is called underflow.

Primitive operations on stack:

  • Insertion of new element (PUSH)
  • Deletion of element (POP)
Insertion of a new element in stack:
Algorithm: PUSH (S, TOP, MAX, ITEM)

This algorithm inserts an element ‘ITEM’ to TOP of the stack ‘S’ containing ‘MAX’ elements with a pointer ‘TOP’ denoting top element in the stack.

Step 1: [ Check the stack overflow. ]

If TOP = MAX, then

Write (‘Stack overflow’) and Return.

[ End of If structure]

Step 2: [ Increment TOP. ]

TOP := TOP + 1

Step 3: [ Insert an element ]

S[TOP] := ITEM

Step 4: [ Finished ]

Return.

 

Deletion of an element from stack:
Algorithm: POP (S, TOP, ITEM)

This algorithm deletes the top element of stack ‘S’ and assign its value to ‘ITEM’. ‘TOP’ is a pointer to the top element of the stack.

Step 1: [ Check the stack underflow. ]

If TOP = 0, then

Write (‘Stack underflow’) and Return.

[ End of If structure]

Step 2: [ Assign TOP element to ITEM. ]

ITEM := S[TOP]

Step 3: [ Decrement TOP. ]

TOP := TOP – 1

Step 4: [ Finished ]

Return.

 

Stack as an Abstract Data type:

A stack is a linear list in which insertions (also called additions) and deletions take place at the same end. This end is called top, other end is called bottom. A stack is LIFO (Last In First Out) list.

Instances: Linear list of element; one end is called the bottom; the other is top.

Operations:

create( ): Create an empty stack.

isempty( ): Return true if stack is empty.

isfull( ): Return true if stack is full.

top( ): Return top element of stack.

push(x): Add element x to the stack.

pop(x): Delete top element from stack and put it in x.

 

Stack’s applications: Infix, Prefix, Postfix

There are three types of notations for binary operations:

  • Infix notation
  • Prefix / Polish notation
  • Postfix / Reverse Polish / Suffix notation
Infix notation:

For most common arithmetic operations, the operator symbol is placed between its two operands.

For example :

A + B               C – D              E * F                G / H

This is called infix notation.

With this notation, we must distinguish between

( A + B ) * C      and      A + ( B * C )

by using either parenthesis or some operator-precedence convention.

 

Prefix notation:

This is called Polish notation. In this notation, operator symbol is placed before its two operands.

For example :

+ AB               – CD               * EF                / GH

( A + B ) * C             =   [ + AB ] * C             =   * + ABC

A + ( B * C )             =   A + [ * BC ]             =   + A * BC

( A + B ) / ( C – D )   =   [ + AB ] / [ – CD ]   =   / + AB – CD

In the prefix notation, parenthesis are not needed in writing the expressions.

 

Postfix (Suffix) notation:

This is also called Reverse Polish notation. In this notation, operator symbol is placed after its two operands.

For example :

AB +                CD –               EF *                 GH /

Here, also parenthesis are not needed to determine the order of the operations in any arithmetic expression written in Reverse Polish notation.

Note: The computer usually evaluates an arithmetic expression written in infix notation in two steps. First, it converts the expression to postfix notation, and then it evaluates the postfix expression. In each step, the stack is the main tool that is used to done the given task.

 

Evaluation of a Postfix Expression:

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

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

Step 1: Add a right parenthesis “)” at the end of P.

[ This acts as a sentinel ]

Step 2: Scan P from left to right and repeat steps 3 and 4 for each element of P until the sentinel “)” is encountered.

Step 3: If an operand is encountered, put it on STACK.

Step 4: If an operand   is encountered, then:

  • Remove the two top elements of STACK, where A is the top element and B is the next-to-top element.
  • Evaluate B ⊗  A
  • Place the result of (b) back on STACK.

[ End of If structure ]

[ End of Step 2 loop. ]

Step 5: Set VALUE equal to the top element on STACK.

Step 6: Exit.

 

Example:- Consider the following arithmetic expression P written in postfix notation:

P: 5, 6, 6, +, *, 12, 4, /, –

Sol:

Symbol                  Stack

(1)            5                          5

(2)            6                          5, 6

(3)            2                          5, 6, 2

(4)           +                           5, 8

(5)           *                           40

(6)           12                         40, 12

(7)           4                           40, 12, 4

(8)           /                            40, 3

(9)           –                           37

 

Transforming Infix Expression into Postfix notation:

Algorithm: POLISH (Q, P)

Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression P.

Step 1: Push “(“ onto STACK, and add “)” to the end of Q.

Step 2: Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the STACK is empty:

Step 3: If an operand  is encountered, add it to P.

Step 4: If a left parenthesis is encountered, push it onto STACK.

Step 5: If an operator  is encountered, then:

  • Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has same precedence as or higher precedence than
  • Add   to

[ End of If structure ]

Step 6: If a right parenthesis is encountered, then:

  • Repeatedly pop from STACK and add to P each operator ( on the top of STACK ) until a left parenthesis is encountered.
  • Remove the left [ Do not add the left parenthesis to P.] [ End of If structure ]

[ End of Step 2 loop. ]

Step 7: Exit.

 

Example:

Convert the following infix expression to postfix:

A + B / C – D * F / A

Sol:

A + B / C – D * F / A )

Symbol                Stack                      Expression

(1)           A                         (                                  A

(2)           +                         ( +                               A

(3)           B                         ( +                               A B

(4)           /                          ( + /                             A B

(5)           C                         ( + /                             A B C

(6)           –                         ( –                                A B C / +

(7)           D                        ( –                                A B C / + D

(8)           *                         ( – *                             A B C / + D

(9)           F                         ( – *                            A B C / + D F

(10)         /                         ( – * /                          A B C / + D F

(11)         A                        ( – * /                          A B C / + D F A

(12)         )                                                             A B C / + D F A / * –

So, the resultant postfix expression is A B C / + D F A / * –

 

Algorithm: convert infix to prefix notation

Algorithm: Polish (Q,P)

[Suppose Q is an algorithm expression written in infix notation. This algorithm finds equality prefix expression P]

  1. Push “)” on to stack and add “(“to the beginning of Q.
  2. Scan Q from right to left and repeat step 3 to 6 for each element of Q until the stack is empty.
  3. If an operand is encountered, add it into P.
  4. if a”)” is encountered push is onto stack.
  5. if an operator ⊗  is encountered then:
    • Repeatedly pop from stack and add to P each operator which has same precedence as a high precedence than .
    • Add ⊗  to the stack.
  6. if a “(“ is encountered then:
    • Repeatedly pop from stack and add to P each operator until a “)” is encountered.
    • Remove “)”. [do not add the “)” to P]

[End of itf structure]

[End of step 2 loop]

  1. Exit

You May Like to Browers More