03
  • Stack ADT

    A stack S stores items of some type (stackElementType) in Last-In, First-Out (LIFO) order.

    Stack ADT operations

    stackElementType S.pop()
    Precondition:  	!S.isEmpty()
    Postcondition:	S = S with top removed
    Returns:        The item x such that S.push(x) was the most recent invocation of push.	
    
    void S.push(stackElementType)
    Precondition: 	Stack S exists
    Postcondition:	Item x is added to the stack, such that a subsequent S.pop() returns x.
    
    stackElementType S.top()
    Precondition:	! S.isEmpty()
    Postcondition:	None
    Returns:        The item x such that S.push(x) was the most recent invocation of push.
    
    bool S.isEmpty()
    Precondition:	Stack S exists
    Postcondition:	None
    Returns:	true if and only if S is empty, i.e., contains no data items.
    
    int S.size()
    Precondition:	Stack S exists 
    Postcondition:	None
    Returns:        number of data items in stack
    
  • Stacks and Lists

    Stacks share many of the characteristics of lists, except they have a restriction on where data must be accessed or stored (only at the top).

    Data in stacks is homogeneous, i.e., all data items are of the same type (note that because of polymorphism, the items can be of the stack element type or any sub-type of that type)

    We can use list-type implementations for stacks
    Arrays (static/fixed datastructure)
    Linked lists (dynamic datastructure)

    Array-based stack (version 1)

    Array Based Stack Image

    Problems
    The top is fixed, therefore all access for storage (push) or retrieval (pop) must go through it.
    To keep it LIFO, the most recent item must be on top
    As new items are added older items must shuffle down.
    This is slow and unnecessary

    A better implementation
    Instead of fixing the top and moving the data, fix the data and move the top
    As long as we know where top is we can still do all push and pop functions associated with LIFO

    Array-based stack (version 1) – floating top

    Array Based Stack Image
  • Stack creator (constructor)

    // set up the stack top
    begin createStack( )
       set stackTop to lowest array index  -1;
    end createStack;
    

    push( ) algorithm – array

    // function to push an item onto the stack
    begin push( stackElement se )
       if ( stackFull ) begin
          print "Stack is full\n";
          set ok to false;
       end
       else begin
          inc stackTop;
          set stack[ stackTop ] = se;
          set ok to true;
       end if
       return ok;
    end push;
    

    pop( ) algorithm – array( )

    // function to pop the top item from the stack 
    begin pop( stackElement se)
       if ( stackEmpty ) begin
          print "Stack is empty\n";
          set ok to false;
       end
       else begin
          se = stack [ stackTop ];
          dec stackTop;
          set ok to true;
       end if
       return ok;
    end pop;
    

    stackEmpty( ) and stackFull( )

    // function checks to see if the stack is empty
    begin stackEmpty( )
       return stackTop == minStackSize;
    end stackEmpty;
    
    // function checks to see if the stack is full
    begin stackFull( )
       return stackTop == maxStackSize;
    end stackFull;
    
  • ADTStack in Java

    This is a Java interface to define a Stack ADT. Note that for simplicity this defines a stack that stores string data. This could be changed to use generics and store any kind of data elements as shown in the linked list example you saw previously.

    public interface ADTStack {
    
        void createStack();
        
        int size();
    
        boolean isEmpty();
    
        boolean isFull();
    
        void push(String s);
    
        String pop();
    
    }
    
  • String Stack

    This shows part of a possible implementation of our Stack ADT, showing the fields of the class and the createStack operation.

    public class SimpleStack  {
        private String[] stack ;   
        private static final int MAXELEMENTS = 100;
        private int top;
        
        public void createStack() {
            stack = new String[MAXELEMENTS];    
            top = 0;          
        }
    

    The push operation can then be implemented as follows:

    public boolean push(String s) {
        if ( isFull() == false)         // checks if space in stack
        {
            stack[top] = s;     // add item
            top++;              // increment top
            return true;        // to indicate success
        }
        else {
            return false;       // to indicate failure
        }
    }
    

    The full implementation of the SimpleStack class is left as a lab exercise.

    Linked list implementation

    Array-based stacks have the disadvantage that they are static structures. They may waste space, or they may not have enough space.

    Dynamic stacks, on the other hand:
    Do not have unused space
    Do have extra memory requirements (for references/pointers)
    Do not run out of space, unless there is no more room on the heap (the memory set aside for dynamic allocation)

    How could you build a dynamic stack class to implement our Stack ADT? This could be based on the linked list implementation you have seen. The head of the list would be the top of the stack – remember that linked lists are very efficient for insert/remove at the start, so would be efficient for push/pop.

  • Application: An Expression Calculator

    Standard notation for arithmetic expression is called ‘infix’. The operator is ‘in between’ pairs of operands.

    Example:

    5 + 7

    A problem that arises with infix notation is possible ambiguity - which operator is carried out first when there is more than one operator in an expression?

    5 + 7 / 2

    Precedence rules

    Infix ambiguity is solved by precedence rules
    1. Evaluate expressions in parentheses first
    2. * and / before + and -
    3. Equal precedence goes left to right

    These rules are sometimes known as BODMAS
    Brackets (parts of a calculation inside brackets always come first)
    Orders (numbers involving powers or square roots).
    Division
    Multiplication
    Addition
    Subtraction

    Other forms of expressions

    Infix is only one method of representing expressions. Others are ‘postfix’ and ‘prefix’
    In postfix expressions the operators come after operand pairs (5 7 +)
    In prefix expressions the operators come before operand pairs. (+ 5 7)

    Reverse Polish Notation

    RPN is a postfix expression form. It requires no parentheses. It does require a stack to evaluate expressions.

    Rules of evaluation:

    1. Evaluate from left to right
    2. When you encounter an operator you immediately apply it to the operands that preceded it. Then put the result on the stack.

    Tokenization

    Input characters are either operators or operands. Each is evaluated as a ‘token’ and the appropriate action taken for that token.

    This process is called ‘tokenization’ or ‘lexical analysis’

    Flow Chart Image

    Sample expression

    Let's see how the following infix expression would be written in RPN and evaluated using a stack:

    (3-4)-(5*3) = -1 - 15 = -16

    In RPN this would be written as:

    3 4 – 5 3 * -

    When a number is read in it is pushed to the stack. When an operator is read in, we check to see if there are number(s) available on the stack as operands for that operator. If so, those numbers are popped from the stack, the operation is evaluated and the result is pushed back to the stack.

    Expression and Stack Image
  • Application: Function / Method Calls and Recursion

    Most computer programs involve the use of methods (in OO languages) or functions (in functional languages) that are called as the program runs. In this section we talk about methods, but everything applies also to functions.

    Methods can be called from other methods. When one method calls another, execution switches from the code in the calling method to the code in the called method. When the called method completes, execution returns to the calling method.

    It is important for the runtime environment to keep track of method calls so that the right code is executed at the right time. This is done by storing method calls and returning them in LIFO order – i.e. using a stack.

    When a method is initiated, it gets its own copies of the parameters that are passed to it by the calling code.

    Upon a method call, the data for the calling method, along with the address of where the call occurred, must be stored somewhere. These get stored on a stack data structure, the call stack, as ‘stack frames’ or ‘activation records’.

    Recursion

    A recursive call is a special case of a method or function call, where the code inside a method calls that same function again, which in turn calls the same function, and so on. While there is only one function involved, it may be called many times, and each call needs to be tracked by the call stack.

    Method Stack in the JVM

    The Java Virtual Machine (JVM) keeps track of the chain of active methods with a call stack

    When a method is called, the JVM pushes onto the stack a frame containing
    Local variables and return value
    Program counter, keeping track of the statement being executed

    When a method ends, its frame is popped from the stack and control is passed to the method on top of the stack. This allows for method calls including recursive calls.

    main() {
    	int i = 5;
    	foo(i);
    }
    foo(int j) {
    	int k;
    	k = j+1;
    	bar(k);
    }
    bar(int m) {
    	…
    }
    

    This diagram shows how the contents of the call stack change over time as methods are called. Time goes from left to right, and each stack of frames shows the contents of the call stack at a point in time.

    Java Stack Method Diagram

    Stack frames

    A stack frame contains all that is necessary to restart a method:
    The location of the next instructions
    The values of all local variables
    The values of all parameters

    A call to method g from method f:
    Loads a stack frame
    Pushes the frame on to the ‘call stack’
    Binds the formal parameters for g to the actual parameters for f
    Transfers control to the first instruction in g.

    To return to method f from g:
    Pop the top stack frame from the call stack
    Use the values in the stack frame to reinitialize the values for f
    Bind the return value for the call to g
    Transfer control to the return address in function f
  • A Recursive Power Function

    Computes an integer power of a floating point number

    double power(double base, int exponent) {
        if (exponent < 1) {
            return 1.0;
        } else {
            return power(base, exponent-1) * base;
        }
    }
    

    The function is called as follows:

    System.out.println( power(1.7, 3) );
    

    Initial bindings
    base = 1.7
    exponent = 3

    This diagram shows how the contents of the call stack change as recursive calls are made. Each time power executes, it makes another call to power, and pushes a new stack frame to the call stack. The value of the exponent parameter is different each time – look at the code to see why. At the fourth call, exponent is now < 1, so the other branch of the if statement executes and power is not called again. This is the stopping condition – without it the recursion would go on forever!

    Call stack with recursive calls

    Call Stack with recursive calls

    In the fourth call, power returns 1.0 and that frame is popped from the stack. Execution returns to the third call, which returns the result of calculating:

    power(base, exponent-1) * base

    which is:

    value returned by fourth call * base
    = 1.0 * 1.7
    = 1.7

    Now the third frame is popped from the stack and execution returns to the second call, which in turn returns the result of calculating:

    value returned by third call * base
    = 1.7 * 1.7
    = 2.89

    Now the second frame is popped from the stack and execution returns to the first call, which in turn returns the result of calculating:

    value returned by second call * base
    = 2.89 * 1.7
    = 4.913

    Each return does the following:
    Pops a frame off of the stack
    Restores its data state
    Replaces the call to power with the return value
    Continues execution at the return address

    Call stack as recursive calls return

    Call Stack with recursive calls

    Recursion and RAM

    Recursive functions may require more space in memory than non-recursive calls. With some deeply recursive algorithms this can be a problem. It is possible to run out of memory space on the stack – stack overflow.

    It can also be a problem with poorly written recursive functions with bad stopping condition definitions (result is like an infinite loop only on the stack)

    Advantages of recursion

    Recursion’s big advantage is the elegance with which it embodies the solution to many problems

    It closely follows the mathematical definition of many functions

    This makes it easier to prove correctness

    Some problems are much easier to solve recursively than iteratively, e.g. Towers of Hanoi

    Disadvantages of recursion
    Use of system resources slows the process down compared to iterative solutions, although this may not be a big factor on modern machines
    Possibility of stack overflow
    Difficult to ‘think recursively’
  • Application: Parentheses Matching

    You have seen that a stack can be used to evaluate postfix expressions. However, when you write expressions in most programming languages, you don't write postfix. One of the jobs that a compiler typically does is to translate expressions to postfix notation so that they can be evaluated.

    The compiler's job of translating code that you write into something that can be executed is helped by the presence of brackets, in expressions and elsewhere in the code, as well as other symbols – all those tedious { and }, ( and ) and so on. The compiler uses a stack when checking these. This example is a simple illustration of how this works.

    Parentheses Matching using a stack

    Each “(”, “{”, or “[” must be paired with a matching “)”, “}”, or “[”

    For example:

        correct: ( )(( )){([( )])}
        correct: ((( )(( )){([( )])}))
        incorrect: )(( )){([( )])}
        incorrect: ({[ ])}
        incorrect: )(
    

    Parenthesis Matching (Java Code)

    The method isMatched takes a string and returns true if all the brackets match correctly, false otherwise. The expression could be a string containing the contents of a Java source file.

    public boolean isMatched(String expression) {
        SimpleStack buffer = new SimpleStack();
        buffer.createStack();
        final String opening = "({["; // opening delimiters
        final String closing = ")}]"; // closing delimiters
    
        for (char c : expression.toCharArray()) {
            if (opening.indexOf(c) != -1) // this is a left delimiter
                buffer.push(Character.toString(c));
            else if (closing.indexOf(c) != -1) { // this is a right delimiter
                if (buffer.isEmpty()) // nothing to match with
                    return false;
                if (closing.indexOf(c) != opening.indexOf(buffer.pop())) 
                    return false; // mismatched delimiter
            }
        }
    
        return buffer.isEmpty(); // were all opening delimiters matched?
    }
    

    Note that this method makes use of the SimpleStack class we looked at earlier on. Alternatively we could have used a Java Collections Framework class such as the Stack. See the following link for documentation on that class:

    🔗 https://docs.oracle.com/javase/9/docs/api/java/util/Stack.html

  • Summary

    The Stack ADT is a LIFO data structure characterised by the operations push and pop.
    The Stack ADT can be implemented using either an array, which has a fixed maximum size, or a linked list which can grow dynamically.
    Reverse Polish Notation (RPN) expressions can be conveniently evaluated with a Stack ADT.
    The Stack ADT can be used to organize the stack frames used at runtime to keep track of function calls, both recursive and non-recursive.
    Compilers can use a Stack ADT to help translate source code into executable code
School of Computing, Engineering and Built Environment