Notes on Stacks, Queues, and Binary Search Trees

Stacks and Queues

Stack ADT

  • A stack is a list that allows insertions and deletions only at the top.

  • The bottom of the stack is the other end.

  • Fundamental Operations:

    • Push: Add an element to the top of the stack.

    • Pop: Removes the most recently inserted element from the top of the stack.

    • Top: Examines the most recently inserted element.

  • Stacks operate on a LIFO (Last In, First Out) basis; the last element added is the first to be removed.

Infix, Postfix, and Prefix Notations

  • These notations are commonly used in calculators.

  • Implementing Postfix and Prefix operations is more straightforward with stacks.

  • Postfix Notation Advantages:

    • No need for parentheses.

    • No precedence problems.

Postfix Calculation

  1. Scan the postfix expression left to right.

  2. If a character is a digit, push it onto the stack.

  3. If the character is an operator (+, -, *, /):

    • Pop two values from the stack.

    • Perform the operation.

    • Push the result back onto the stack.

  4. After processing the entire expression, pop the value from the stack for the final output.

Conversion from Infix to Postfix

Rules for Conversion

  • Scan the infix expression from left to right.

  • If the character is an operand (number or variable), output it directly to the Postfix expression.

  • If it's a left parenthesis, push it onto the stack.

  • If it's a right parenthesis, pop from the stack and output until a left parenthesis is at the top of the stack.

  • For operators:

    1. Check the character at the top of the stack.

    2. If the stack is empty or the top operator has lower precedence, push the current operator onto the stack.

    3. If the top operator has higher or equal precedence, pop it and output before pushing the current operator.

  • Once the infix expression is fully processed, pop all remaining elements in the stack until it is empty.

Queue ADT

  • A queue is also a list, but insertion occurs at one end and deletion at the other.

  • Operates in a FIFO (First In, First Out) order, similar to a check-out line.

Basic Operations

  • Enqueue: Insert an element at the rear of the queue.

  • Dequeue: Remove an element from the front of the queue.

Implementation of Queue

  • Queues can be implemented as arrays or linked lists.

  • Dynamic queues offer advantages over static queues.

Implementation Details

  1. Naive Method:

    • The front index is fixed; the rear index moves forward.

    • Dequeuing involves shifting all remaining elements (inefficient).

  2. Better Method:

    • Move the rear index forward on enqueue.

    • Move the front index simply without shifting elements.

Binary Search Trees (BST)

  • A BST allows each node to have at most two children based on value comparison.

    • Left child < Parent

    • Right child > Parent

  • Ensures operations like lookup, insertion, and deletion run in logarithmic time while keeping the average height of the tree at logarithmic scale as well.

Deletion Cases

  1. Leaf Node: Remove directly.

  2. Single Child Node: Update references to bypass the node.

  3. Two Children: Replace with either the largest item from left subtree or smallest from right subtree, ensuring efficient reference updates.

Traversals

  • To visit every node:

    1. In-order Traversal: Left, Node, Right

    2. Pre-order Traversal: Node, Left, Right

    3. Post-order Traversal: Left, Right, Node

Worst-case ScenarioS

  • An unbalanced tree can degrade performance to O(N), reinforcing the importance of maintaining balance in the structure.