ADT Stacks

Stacks Principle: Last In First Out Definition: An ordered collection of data items which can be accessed at only one location, called the top of the stack

Basic Operations



Push inserts the data item at the top of the stack, returns the modified stack.



Pop


retrieves and removes the element at the top of the stack, returns the top element of the stack and the modified stack

  

Make Null Empty Full

Representation:

char STACK[10];

{

void Push (char ch) if (Top >= (MaxStack - 1)) Success = False; //no room on stack else { Top++; //increment stack top pointer STACK[Top] = ch; //copy X to stack Success = True; }}

}

char Pop ( ) { if (Top < 0) Success = False; //empty stack else { ch = STACK[Top]; //pop top of stack into X Top--; //decrement top of stack pointer Success = True; return ch; }

void Make Null ( ) { Top = -1; } int Empty Stack ( ) { return (Top < 0); } int Full Stack ( ) { return(Top >= MaxStack); }

Array Implementation for a Stack of ints public class ArrayStack { int store[]; int top; static final int MAX = 100; public ArrayStack() { store = new int[MAX]; top = 0; } // ... }

top 4

top = index of the first FREE slot

12 24

37 17

...

ArrayStack class, continued public class ArrayStack { // ... public boolean empty() { return (top == 0); } public void push(int entry) { if (top < MAX) store[top++] = entry; } // ... } // in the code that uses // the stack … stack.push( 95 );

Remember: top = index of the first FREE slot top 5 4 37 17 95 ...

12 24

ArrayStack class, continued public class ArrayStack { // ... public int pop() throws Exception { if ( empty() ) throw new Exception(); else return store[--top]; } } // in the code that uses // the stack … int x = stack.pop();

// x gets 95, // slot 4 is now free

Remember: top = index of the first FREE slot top 4 5 37 17 95 Store[4] still contains 95, but it’s now considered “free”. ...

12 24

Using the Stack try { ArrayStack st = new ArrayStack(); st.push( 1 ); st.push( 3 ); st.push( 2 ); System.out.println( st.pop() ); st.push( 5 ); System.out.println( st.pop() ); System.out.println( st.pop() ); } catch ( Exception e ) { System.out.println( “pop() on empty stack” ); }

Application of Stacks




Checking for unpaired or paired (),{} in a programming language Evaluation of expressions.

Evaluation of Expression
To understand how stacks can be used in evaluating expressions, we first need to know some underlying principles of binary expressions, that is notation of expressions. Notations of Expressions Let X=A+B be an expression. Then the notations of expressions are defined as: 1. Prefix notation: the operator is written before the two operands. Ex. +AB 2. Infix notation: the operator is written in between the two operands. Ex. A+B 3. Postfix notation: the operator is written after the two operands. Ex. AB+

  

Illustration: X=A+B/C-D Find the 3 notations of the above expression. Prefix: -+A/BCD Infix: A+B/C-D Postfix: ABC/+D-

  

Knowing the underlying principles on the 3 notations of expressions, we now are ready to use stacks to evaluate expressions. There are 2 possible ways to evaluate expressions 1. 2. Prefix method Postfix method

Prefix Method
Let there be 2 stacks X and S. Assume that X contains the prefix notation of the expression and S be initially empty. S will be used to do the evaluation. Get the top of X. If x [i] is an operand, push the element into S.  If x[i] is an operator, pop the 2 topmost element of S. Apply the operation defined by x[i] then push the result into S  4. Repeat steps 2-3 until X is empty or S is left with only one element. That element must be the result of the evaluation process.

Conversion of infix to postfix notation using stacks •push only operations onto the stack •push the operator if the incoming operator has a higher precedence than the top operator in the stack. •If the incoming operator has a priority