PP13

Stacks

Introduction to Stacks

• Stacks are a data structure used to store an ordered sequence of values.

• They support a minimal set of operations:

  • Add Value: Place values onto the stack (push)

  • Remove Value: Take values out of the stack (pop)

  • Check Emptiness: Test whether there are any values left (is empty)

Characteristics of Stacks

• A stack is characterized by having restricted insertion and removal, only allowing operations on the top or end of the list.

• Also known as First-In, Last-Out (FILO):

  • Insertion always adds an item to the top.

  • Deletion always removes the item from the top.

Important Stack Methods

1. push

   • Inserts an item onto the top of the stack.

2. pop

   • Removes and returns the item on the top of the stack. Consecutive calls to pop will return items in the reverse order they were pushed.

3. peek

   • Returns the top item of the stack without removing it.

Visual Representation

• It is useful to visualize stacks as upright structures (e.g., a stack of books).

Performance of Stacks

• The time complexity for push, pop, and peek operations must all be $O(1)$.

• The stack can be implemented using an array.

• Top Index Management:

  • Keep track of a variable called top to manage the position of the last inserted element.

  • Increment top when pushing an element and decrement it when popping one.

Resizing Considerations

• If an attempt is made to push an element when the underlying array is full, the array might need to be resized, which can take $O(N)$ time. However, since such operations are rare, the average case performance for push is still $O(1)$.

Java Implementation of Stack

• Class Definition:

class Stack {
    private int arr[];
    private int top;
    private int capacity;

    // Constructor to initialize stack
    Stack (int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    // Function to push element onto stack
    public void push(int x) {
        if (isFull()) {
            System.out.println("OverFlow\nProgram Terminated\n");
            System.exit(1);
        }
        arr[++top] = x;
    }

    // Function to pop top element from stack
    public int pop() {
        if (isEmpty()) {
            System.out.println("UnderFlow\nProgram Terminated");
            System.exit(1);
        }
        return arr[top--];
    }

    // Function to return top element
    public int peek() {
        if (!isEmpty())
            return arr[top];
        else
            System.exit(1);
    }

    // Function to return size of the stack
    public int size() {
        return top + 1;
    }

    // Function to check if stack is empty
    public boolean isEmpty() {
        return top == -1;
    }

    // Function to check if stack is full
    public boolean isFull() {
        return top == capacity - 1;
    }
}

Postfix Notation and Evaluation Using Stacks

• Infix notation places an operator between operands (e.g., a + b). The order of operations can be ambiguous without parentheses.

• Postfix Notation (or Reverse Polish Notation): An alternative that avoids ambiguity by placing operators after their operands (e.g., ab+).

Steps to Evaluate Postfix Expression Using a Stack

1. When an Operand is Seen: Push it onto the stack.

2. When an Operator is Seen: Pop the two topmost operands from the stack, perform the operation, and push the result back onto the stack.

3. At the Completion of the Expression: The remaining item on the stack is the result.

Example of Postfix Evaluation

• For the expression 1 2 3 * + 4 -, the steps would be:

  • Push 1, push 2, push 3, upon seeing *, pop 3 and 2, compute 2 * 3 = 6, push 6.

  • Next, push 4, upon seeing +, pop 4 and 6, compute 6 + 1 = 7, push 7.

  • Upon seeing -, pop 7 and 4 to compute 4 - 7 = -3.

Java Program to Evaluate Postfix Expression

import java.util.Stack;

class Test {
    // Method to evaluate value of a postfix expression
    static int evaluatePostfix(String exp) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < exp.length(); i++) {
            char c = exp.charAt(i);
            if (Character.isDigit(c)) {
                stack.push(c - '0'); // Push operand
            } else {
                int val1 = stack.pop(); // Pop top element
                int val2 = stack.pop(); // Pop next element
                switch (c) {
                    case '+': stack.push(val2 + val1); break;
                    case '-': stack.push(val2 - val1); break;
                    case '/': stack.push(val2 / val1); break;
                    case '*': stack.push(val2 * val1); break;
                }
            }
        }
        return stack.pop(); // Final result
    }
}

Conclusion

• Stacks are fundamental data structures used extensively in programming for operations that require ordering, such as undo operations, parsing expressions, and call stacks in programming languages. Their implementation can directly affect performance and algorithm efficiency. Understanding stacks is crucial for effective programming and algorithm design.