Data Structure & Algorithm

• Taking the statement of a problem and develop a computer program to solve the problem
• A solution is a computer program written in programming language consists of module (e.g dunciton, method, class, etc)
• A good computer program (solution) consists of modules that:
  • Organize data collection to facilitate operations
  • Store, move and alter data
  • Use algorithms to communicate with one another

• A step-by-step procedure to perform a task in a finite amount of time
• It operate on a collection of data
• It’s a problem solving using logic
• A well-defined instructions in algorithm include:
  • Input
  • Processing
  • Output
• Basic Control Structures;
  • Sequential
  • Selection
  • Repetition
• Techniques to design algorithm:
  • Pseudocode
  • Flowchart
  • State Machine

• It’s a high-level conceptual model for organizing and working with data in cs, it defines sets of operations that can be preformed on the data.

• A way of storing and organizing data in a computer so that it can be used efficiently
• Choosing the right data structure will affect the efficiency of an algorithm implementation
• Operations to data structure
  • traversing
  • searching
  • insertion
  • deletion
  • sorting
  • merging
• What are 2 data structure types (how data is organized and stored)?
  • Primitive Data Structures: These are basic data types provided by programming languages, like integers, floating-point numbers, characters, booleans, and pointers.
  • Non-Primitive Data Structures: These are more complex structures created by combining primitive data types or other non-primitive structures, like arrays, structures, linked lists, stacks, queues, trees, and graphs. They help organize and manage data in various ways.

• To predict the performance (time + space(memory))
• To compare algorithms
• To provide guarantees
• To avoid bugs

• Effectiveness
  • Easy to understand
  • Easy to trace
  • The step of logical execution are well organized
• Termination
  • Step of execution contains ending
  • Termination happen as planned, not because of problems like looping, out of memory, or infinite value
• Efficiency
  • Running time
  • Memory usage
  • Accuracy (output is expected or required)

• The analysis of how the resources required by an algorithm (time and memory) grow as a function as the size of the input data
• it provides measure of how efficient an algorithm is in terms of time and memory usage
• What are 2 primary aspects of algorithm complexity?
  • Time
    • Most algorithms transform input objects into output objects
    • The running time of an algorithm typically grows with the input size
    • 3 case to consider
      • Worst case
        • A determination of the max amount of time that an algorithm requires to solve the problems of size n
        • eg: sorting increasing of number for input:
          • 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 (the algorithm will need to compare the first number to all the number after it to find the lowest, thus take a looooong time)
      • Average case
        • A determination of the average amount of time that an algorithm requires to solve the problems of size n
        • eg: sorting increasing of number for input:
          • 8,6,4,5,3,2,0,1,9 (the algorithm does not need to compare the numbers all the. way to the back, hence better than the worse case)
      • Best case
        • A determination of the min amount of time that an algorithm requires to solve problems of size n
        • eg: sorting increasing of number for input:
          • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (the numbers are already sorted)
    • Represented using Big O notation
      • provides idea on how an algorithm will grow in complexity as the number of input increases
      • 7 Big O

A data structure composed of nodes, each node holding some information and a reference to another node in the list

• Nodes can be located anywhere in the memory
• Passing one node to another using references
• Can be implemented many ways, but the most flexible is by using a separate object for each node

Closest thing is array, but array has limitation:

• Changing of array size needs to create new array and copy all data
• Data in array are next to each other sequentially, inserting new data require shifting other data

What are the types of linked list?

• Singly linked list
  • head: beginning of linked list
  • tail: end of linked list
  • Each node has:
    • Info field: store the info
    • Address field: linking nodes (address field that contains reference to the next node — thats why at the tail, the address field is NULL, since there is no next node)
• Doubly linked list
  • head: the beginning of the linked list
  • tail: the end of linked list
  • Each nodes have:
    • Info field: the actual data
    • Next field: the address of next node
    • Prev field: the address of previous node
• Circular linked list
  • Can be:
    • Singly: The next pointer of tail points to head
    • Doubly: The previous pointer of head points to tail
• Self-organizing list example of self-organizing list
  • A list that reorders its elements based on some self-organizing heuristic to improve average access time
  • Methods for organizing list:
    • Move-to-front
      • After the desired element is located, put it at the beginning of the list
    • Transpose
      • After the desired element is located, swap it with its predecessor unless it is at the head of the list
    • Count
      • Order the list by the number of times elements are being accessed (the more it is accessed, the closer it is to the beginning)
    • Ordering
      • Order the list using certain criteria natural for the information under scrutiny — This means that the order of elements in the list is not fixed; it changes dynamically based on how often and how recently elements are accessed or searched for.

Access to the list

• isEmpty()
• addToHead(Tel)
• addToTail()
• deleteFromHead()
• deleteFromTail()
• Delete(Tel)
• printAll()
• isInList(Tel)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

    public class IntSLList {
        protected IntSLLNode head, tail;
        public IntSLList() { //constructor, initiating a value
            head = tail = null;
        }

        public boolean isEmpty() {
            return head == null; //check if head is empty, then the list is empty
        }

        public void addToHead(int el) {
            head = new intSLLNode(el, head);
            if (tail==null)
                tail = head; //if tail is null, then the list is empty (only contain the newly added head)
        }

        public void addToTail(int el) {
            if  (!isEmpty()) {
                tail.next = new IntSLLNode(el);
                tail = tail.next
            }
            else head = tail = new IntSLLNode(el); //if the list is empty, head = tail
        }

        public int deleteFromHead() {
            int el = head.info;
            if (head==tail)
                head = tail = null; //if only one node in the list
            else head = head.next;
            return el; //the value deleted is returned
            }

        public int deleteFromTail() {
            int el = tail.info;
            if (head==tail)
                head = tail = null;
            else {
                IntSLLNode tmp;
                for (tmp = head; tmp.next != null; tmp = tmp.next);//finding the predecessor of tail
                tail = tmp; //the predecessor of tail becomes tail
                tail.next = null;
                }
            return el;
            }

        public void printAll() {
            for(IntSLLNode tmp = head; tmp != null; tmp = tmp.next)
                System.out.print(tmp.info + " ")
        }

        public boolean isInList(int el) {
            InsSLLNode tmp;
            for(tmp = head; tmp!=null && tmp.info!=el; tmp=tmp,next);
            return tmp!=null;
        }

        public void delete(int el) {
        if(!isEmpty())
            if(head==tail && el==head.info)
                if(head==tail && el==head.info)
                    head = tail = null; //if only one node in the list
                else if(el==head.info)
                    head = head.next; //if the node is the head
                else {
                    IntSLLNode pred, tmp;//of node is not the head
                    for(pred=head, tmp=head.next;
                        tmp!=null && tmp.info !=el;
                        pred=pred.next, tmp=tmp.next);
                    if(tmp!=null {
                        pred.next = tmp.next;//it skips the deleted node, jump straight to next node
                        if(tmp==tail) //if el is in tail
                            tail=pred;
                    })
                }
        }
        }

Implementation of linked list

• Implement other complex data structure:
  • Trees
  • Graphs
  • Heaps
• To store and process polynomials
• To create. dynamic stacks and queues which can grow and shrink at run time
• To add two large numbers (stack)
• To check if it is palindrome — katak ↔ katak

Stacks

• Linear data structure that can be accessed only at one of its ends for storing and retrieving data

• LIFO structure: Last In First Out — useful when data have to be stored and then retrieved in reverse order

• Functions on stack a series of operations executed on a stack

  • clear() - clear the stack
  • isEmpty() - check if stack is empty
  • push(el) - put element el on top of the stack
  • pop() - take the topmost element form the stack (only the top can be removed)
  • topEl() - return the topmost element without removing

• What are the applications of stack?

  • Matching delimiters/ balanced parenthesis

    • delimiters:
      • parentheses ( )
      • square brackets [ ]
      • curly brackets { }
      • comment delimiters /* */
    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

    read character ch from file; while not end of file if ch is '(', '[', or '{' push(ch);#if open brakcet found, push into stack else if ch is double quote skip all chars to a double quote; else if ch is ')', ']', or '}' if ch and popped off delimiter not match failure;#if close bracket found, pop from stack #if popped doesnt mactch the close brakcet #means the bracket isn't balanced else pop stack; else if ch is '/' read the next character; if character is '*' skip all character until '*/' is found report if until end of file, no '*/' found else ch = the character read in; continue; //go to the beginning of the loop if stack is empty success; ese failure;

    

    • if open bracket found, push into stack
    • if close bracket found, pop the stack, if not match, than the parentheses is not balanced
      • Since stack is LIFO, if it is balanced, the bracket should always match

  • addingLargeNumbers()

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

    read numerals of the first number, store the numbers corresponding to them on the stack; read numerals of the second number, store the numbers corresponding to them on the stack; carry=0; while at least one stack is not empty pop a number from each nonempty stack, add to carry; push the unit part on the result stack; store carry in carry; push carry on the result stack if it is not zero; pop numbers from the result stack and display them'

    

  • convertDecimaltoBinary()

    copy

    1 2 3 4 5 6 7 8 9 10 11

    Create stack object Read (number) While num != 0 d = num % 2 #d= remainder push d into stack num = num / 2 #num is updated while stack is not empty pop numbers from the stack, display them; #stack is popped according #to LIFO

  • reverseWord()

    copy

    1 2 3 4 5 6 7

    read(data) while (not end of file && stack not full) push data read data while (stack is not empty) pop data print data

  • Postfix Evaluation

    • Prefix: +ab
    • Infix: a+b
    • Postfix: ab+
    • In high level languages, infix can’t be used to evaluate expressions, because it make ambiguity in the order of expressions, therefore computer convert infix to postfix first then evaluate it
    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14

    eg: 23+* if digit push into stack; //1, 2, 3 is pushed into stack else pop last digit; //3 is popped pop last difit; //2 is popped calculate; //2+3=5 push result into stack; //stack: 1, 5

  • Infix to Postfix conversion

    • Rules
      • Operand directly to output
      • Operators are pushed into the stack (including parenthesis)
        • Priority: */ → +- → ()
        • Check if top operator, if:
          • top < current, push current onto stack
          • top > current, pop top, push current
        • If there is ‘(’, pop into stack, wait until ‘)’ is found, then pop the operators after ‘(’, (parenthesis is not output-ed)
    • eg:

• How to implement stack?

      - Custom implementation
  
        - Using array
  
          ```java
          public class ArrayStack {
              private int maxSize;
              private int[] stackArray;
              private int top;
  
              public ArrayStack(int size) {
                  maxSize = size;
                  stackArray = new int[maxSize];
                  top = -1;
              }
  
              public void push(int value) {
                  if (top < maxSize - 1) {
                      stackArray[++top] = value;
                  } else {
                      System.out.println("Stack is full. Cannot push " + value);
                  }
              }
  
              public int pop() {
                  if (top >= 0) {
                      return stackArray[top--];
                  } else {
                      System.out.println("Stack is empty. Cannot pop.");
                      return -1; // Or throw an exception
                  }
              }
  
              public int peek() {
                  return top >= 0 ? stackArray[top] : -1;
              }
  
              public boolean isEmpty() {
                  return top == -1;
              }
          }
          ```
  
        - Using LinkedList
  
          ```java
          import java.util.LinkedList;
  
          public class LinkedListStack {
              private LinkedList<Integer> stack = new LinkedList<>();
  
              public void push(int value) {
                  stack.addFirst(value);
              }
  
              public int pop() {
                  if (!stack.isEmpty()) {
                      return stack.removeFirst();
                  } else {
                      System.out.println("Stack is empty. Cannot pop.");
                      return -1; // Or throw an exception
                  }
              }
  
              public int peek() {
                  return stack.isEmpty() ? -1 : stack.getFirst();
              }
  
              public boolean isEmpty() {
                  return stack.isEmpty();
              }
          }
          ```
  
      - Using Java’s standard library
  
        - Using java.util.Stack
  
          ```java
          import java.util.Stack;
  
          public class JavaUtilStackExample {
              public static void main(String[] args) {
                  Stack<Integer> stack = new Stack<>();
                  stack.push(1);
                  stack.push(2);
                  stack.push(3);
  
                  System.out.println("Top element: " + stack.peek());
  
                  while (!stack.isEmpty()) {
                      System.out.println("Popped: " + stack.pop());
                  }
              }
          }
          ```
  
          - Method summary
            | Modifier and Type | Method and Description |
            | ------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ |
            | `boolean` | [**`empty**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html#empty--)()`Tests if this stack is empty.                                                                                                                                   |
  
  | [**`E`**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html) | [**`peek**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html#peek--)()`Looks at the object at the top of this stack without removing it from the stack. |
        | [**`E`**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html) | [**`pop**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html#pop--)()`Removes the object at the top of this stack and returns that object as the value of this function. |
  | [**`E`**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html) | [**`push**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html#push-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html) item)`Pushes an item onto the top of this stack. |
  | `int` | [**`search**](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html#search-java.lang.Object-)([\*\*Object\*\*](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)`Returns the 1-based position where an object is on this stack. |
  
        - Using java.util.ArrayDeque
  
          - Deque is double-ended queue, it extends queue interface, allow for double-ended queue; can be used to implement stack and queue
  
          ```java
          import java.util.ArrayDeque;
          import java.util.Deque;
  
          public class DequeAsStackExample {
              public static void main(String[] args) {
                  Deque<Integer> stack = new ArrayDeque<>();
  
                  // Push elements onto the stack
                  stack.push(1);
                  stack.push(2);
                  stack.push(3);
  
                  System.out.println("Top element: " + stack.peek());
  
                  // Pop elements from the stack
                  while (!stack.isEmpty()) {
                      System.out.println("Popped: " + stack.pop());
                  }
              }
          }
          ```
  
          - Method summary
            | Modifier and Type | Method and Description |
            | ------------------------------------------------------------------------------------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
            | `boolean` | [**`add**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#add-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)`Inserts the specified element into the queue represented by this deque (in other words, at the tail of this deque) if it is possible to do so immediately without violating capacity restrictions, returning `true` upon success and throwing an `IllegalStateException` if no space is currently available. |
  
  | `void` | [**`addFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#addFirst-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)`Inserts the specified element at the front of this deque if it is possible to do so immediately without violating capacity restrictions, throwing an `IllegalStateException` if no space is currently available.                                                                                   |
  copy

  | void | [addLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#addLast-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Inserts the specified element at the end of this deque if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available. | | boolean | [contains**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#contains-java.lang.Object-)([**Object**](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)Returns true if this deque contains the specified element. | | [Iterator**](https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html)<[**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html)> | [descendingIterator**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#descendingIterator--)()Returns an iterator over the elements in this deque in reverse sequential order. | | E | [element**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#element--)()Retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque). | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [getFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#getFirst--)()Retrieves, but does not remove, the first element of this deque. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [getLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#getLast--)()Retrieves, but does not remove, the last element of this deque. | | [Iterator**](https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html)<[**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html)> | [iterator**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#iterator--)()Returns an iterator over the elements in this deque in proper sequence. | | boolean | [offer**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#offer-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Inserts the specified element into the queue represented by this deque (in other words, at the tail of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and false if no space is currently available. | | boolean | [offerFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#offerFirst-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Inserts the specified element at the front of this deque unless it would violate capacity restrictions. | | boolean | [offerLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#offerLast-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Inserts the specified element at the end of this deque unless it would violate capacity restrictions. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [peek**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#peek--)()Retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [peekFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#peekFirst--)()Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [peekLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#peekLast--)()Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [poll**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#poll--)()Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [pollFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#pollFirst--)()Retrieves and removes the first element of this deque, or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [pollLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#pollLast--)()Retrieves and removes the last element of this deque, or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [pop**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#pop--)()Pops an element from the stack represented by this deque. | | void | [push**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#push-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Pushes an element onto the stack represented by this deque (in other words, at the head of this deque) if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [remove**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#remove--)()Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque). | | boolean | [remove**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#remove-java.lang.Object-)([**Object**](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)Removes the first occurrence of the specified element from this deque. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [removeFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#removeFirst--)()Retrieves and removes the first element of this deque. | | boolean | [removeFirstOccurrence**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#removeFirstOccurrence-java.lang.Object-)([**Object**](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)Removes the first occurrence of the specified element from this deque. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [removeLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#removeLast--)()Retrieves and removes the last element of this deque. | | boolean | [removeLastOccurrence**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#removeLastOccurrence-java.lang.Object-)([**Object\*\*](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)Removes the last occurrence of the specified element from this deque. | | int | [**size\*\*](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#size--)()Returns the number of elements in this deque. |

      - Stacks function in java.util
        - `boolean empty()`- return true if empty
        - `Object peek()` - return top element, throw EmptyStackException for empty stack
        - `Object pop()` - remove top element, throw EmptyStackException if empty
        - `Object push(Object el)` - insert el at the top of the stack, return it
        - `int search(Object el)` - return position of el
        - `Stack()` - create empty stack
  copy

Queue

• A waiting line that grows by adding elements to its end, shrinks elements from its front (both end are used, compared to stack, only the front end is used to add, remove)

• FIFO structure: First In, First Out

• Functions on queue

  • clear() - clear the queue
  • isEmpty() - check if the queue is empty
  • enqueue(el) - put the element el at the end of the queue
  • dequeue() - take the first element from the queue
  • firstEl() - return the first element in the queue without removing it

• What are the applications?

  • Tracing people at ticket windows
  • CPU scheduling
  • Printing task
  • Checking palindrome

• How to implement queue?

      - Custom implementation
  
        - Using Array
  
          ```java
          public class ArrayStack {
              private int maxSize;
              private int[] stackArray;
              private int top;
  
              public ArrayStack(int size) {
                  maxSize = size;
                  stackArray = new int[maxSize];
                  top = -1;
              }
  
              public void push(int value) {
                  if (top < maxSize - 1) {
                      stackArray[++top] = value;
                  } else {
                      System.out.println("Stack is full. Cannot push " + value);
                  }
              }
  
              public int pop() {
                  if (top >= 0) {
                      return stackArray[top--];
                  } else {
                      System.out.println("Stack is empty. Cannot pop.");
                      return -1; // Or throw an exception
                  }
              }
  
              public int peek() {
                  return top >= 0 ? stackArray[top] : -1;
              }
  
              public boolean isEmpty() {
                  return top == -1;
              }
          }
          ```
  
        - Using LinkedList
  
          ```java
          import java.util.LinkedList;
  
          public class LinkedListQueue {
              private LinkedList<Integer> queue = new LinkedList<>();
  
              public void enqueue(int value) {
                  queue.addLast(value);
              }
  
              public int dequeue() {
                  if (!queue.isEmpty()) {
                      return queue.removeFirst();
                  } else {
                      System.out.println("Queue is empty. Cannot dequeue.");
                      return -1; // Or throw an exception
                  }
              }
  
              public int peek() {
                  return queue.isEmpty() ? -1 : queue.getFirst();
              }
  
              public boolean isEmpty() {
                  return queue.isEmpty();
              }
          }
          ```
  
      - Using [Java’s standard library](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html)
  
        - Using java.util.LinkedList
  
          ```java
          import java.util.LinkedList;
          import java.util.Queue;
  
          public class JavaUtilQueueExample {
              public static void main(String[] args) {
                  Queue<Integer> queue = new LinkedList<>();
                  queue.offer(1);
                  queue.offer(2);
                  queue.offer(3);
  
                  System.out.println("Front element: " + queue.peek());
  
                  while (!queue.isEmpty()) {
                      System.out.println("Dequeued: " + queue.poll());
                  }
              }
          }
          ```
  
          - Method summary
            | Modifier and Type | Method and Description |
            | ------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
            | `boolean` | [**`add**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#add-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html) e)`Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning `true` upon success and throwing an `IllegalStateException` if no space is currently available. |
  
  | [**`E`**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html) | [**`element**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#element--)()`Retrieves, but does not remove, the head of this queue. |
        | `boolean` | [**`offer**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#offer-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html) e)`Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. |
  | [**`E`**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html) | [**`peek**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#peek--)()`Retrieves, but does not remove, the head of this queue, or returns `null` if this queue is empty. |
  | [**`E`**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html) | [**`poll**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#poll--)()`Retrieves and removes the head of this queue, or returns `null` if this queue is empty. |
        | [**`E`**](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html) | [**`remove\*\*](https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html#remove--)()`Retrieves and removes the head of this queue. |
  
        - Using java.util.ArrayDeque
  
          - Deque is double-ended queue, it extends queue interface, allow for double-ended queue; can be used to implement stack and queue
  
          ```java
          import java.util.ArrayDeque;
          import java.util.Deque;
  
          public class ArrayDequeQueueExample {
              public static void main(String[] args) {
                  Deque<Integer> queue = new ArrayDeque<>();
                  queue.offer(1);
                  queue.offer(2);
                  queue.offer(3);
  
                  System.out.println("Front element: " + queue.peek());
  
                  while (!queue.isEmpty()) {
                      System.out.println("Dequeued: " + queue.poll());
                  }
              }
          }
          ```
  
          - Method summary
            | Modifier and Type | Method and Description |
            | ------------------------------------------------------------------------------------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
            | `boolean` | [**`add**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#add-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)`Inserts the specified element into the queue represented by this deque (in other words, at the tail of this deque) if it is possible to do so immediately without violating capacity restrictions, returning `true` upon success and throwing an `IllegalStateException` if no space is currently available. |
  
  | `void` | [**`addFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#addFirst-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)`Inserts the specified element at the front of this deque if it is possible to do so immediately without violating capacity restrictions, throwing an `IllegalStateException` if no space is currently available.                                                                                   |
  copy

  | void | [addLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#addLast-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Inserts the specified element at the end of this deque if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available. | | boolean | [contains**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#contains-java.lang.Object-)([**Object**](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)Returns true if this deque contains the specified element. | | [Iterator**](https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html)<[**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html)> | [descendingIterator**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#descendingIterator--)()Returns an iterator over the elements in this deque in reverse sequential order. | | E | [element**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#element--)()Retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque). | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [getFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#getFirst--)()Retrieves, but does not remove, the first element of this deque. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [getLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#getLast--)()Retrieves, but does not remove, the last element of this deque. | | [Iterator**](https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html)<[**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html)> | [iterator**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#iterator--)()Returns an iterator over the elements in this deque in proper sequence. | | boolean | [offer**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#offer-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Inserts the specified element into the queue represented by this deque (in other words, at the tail of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and false if no space is currently available. | | boolean | [offerFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#offerFirst-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Inserts the specified element at the front of this deque unless it would violate capacity restrictions. | | boolean | [offerLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#offerLast-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Inserts the specified element at the end of this deque unless it would violate capacity restrictions. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [peek**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#peek--)()Retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [peekFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#peekFirst--)()Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [peekLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#peekLast--)()Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [poll**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#poll--)()Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [pollFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#pollFirst--)()Retrieves and removes the first element of this deque, or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [pollLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#pollLast--)()Retrieves and removes the last element of this deque, or returns null if this deque is empty. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [pop**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#pop--)()Pops an element from the stack represented by this deque. | | void | [push**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#push-E-)([**E**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) e)Pushes an element onto the stack represented by this deque (in other words, at the head of this deque) if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [remove**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#remove--)()Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque). | | boolean | [remove**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#remove-java.lang.Object-)([**Object**](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)Removes the first occurrence of the specified element from this deque. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [removeFirst**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#removeFirst--)()Retrieves and removes the first element of this deque. | | boolean | [removeFirstOccurrence**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#removeFirstOccurrence-java.lang.Object-)([**Object**](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)Removes the first occurrence of the specified element from this deque. | | [E](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html) | [removeLast**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#removeLast--)()Retrieves and removes the last element of this deque. | | boolean | [removeLastOccurrence**](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#removeLastOccurrence-java.lang.Object-)([**Object\*\*](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html) o)Removes the last occurrence of the specified element from this deque. | | int | [**size\*\*](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html#size--)()Returns the number of elements in this deque. |

Priority queues

• Can be assigned to enable a particular process, or event, to be executed out of a sequence without affecting overall system operation

• Elements are dequeued according to their priority and their current queue position

• How to implement priority queue?

  • Custom implementation

    • Using LinkedList

      copy

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

      import java.util.LinkedList; import java.util.ListIterator; public class LinkedListPriorityQueue<T extends Comparable<T>> { private LinkedList<PriorityNode<T>> list = new LinkedList<>(); public void enqueue(T element, int priority) { PriorityNode<T> newNode = new PriorityNode<>(element, priority); if (list.isEmpty() || priority > list.getLast().getPriority()) { list.addLast(newNode); } else { ListIterator<PriorityNode<T>> iterator = list.listIterator(); while (iterator.hasNext()) { if (priority < iterator.next().getPriority()) { iterator.previous(); iterator.add(newNode); break; } } } } public T dequeue() { if (isEmpty()) { return null; } return list.removeFirst().getElement(); } public T peek() { return isEmpty() ? null : list.getFirst().getElement(); } public boolean isEmpty() { return list.isEmpty(); } public static void main(String[] args) { LinkedListPriorityQueue<String> priorityQueue = new LinkedListPriorityQueue<>(); priorityQueue.enqueue("Task 1", 3); priorityQueue.enqueue("Task 2", 1); priorityQueue.enqueue("Task 3", 2); System.out.println("Peek: " + priorityQueue.peek()); while (!priorityQueue.isEmpty()) { System.out.println("Dequeued: " + priorityQueue.dequeue()); } } private static class PriorityNode<T> { private T element; private int priority; public PriorityNode(T element, int priority) { this.element = element; this.priority = priority; } public T getElement() { return element; } public int getPriority() { return priority; } } }

  • Using Java’s standard library

    • Using java.util.PriorityQueue

      copy

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

      import java.util.PriorityQueue; public class PriorityQueueExample { public static void main(String[] args) { PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); priorityQueue.offer(3); priorityQueue.offer(1); priorityQueue.offer(2); System.out.println("Peek: " + priorityQueue.peek()); while (!priorityQueue.isEmpty()) { System.out.println("Poll: " + priorityQueue.poll()); } } }

• How to represent priority queue by linked list?

  • All elements are entry ordered (unordered list, since its based on which element are added first)
    • Big O for:
      • adding element: O(1)
      • searching element: O(n)
  • Order is maintained by putting new element at its proper position according to its priority (sorted list)
    • Big O for:
      • adding element: O(n) — need to traverse to proper position to add the new element
      • searching element: O(1)

• What are the application?

  • Assignment priority based on dateline
  • Airline check in — business class is prioritized

Technique of making a function call itself, it provides a way to break complicated problems into simple problems which are easier to solve

The name “recursive” comes from the idea of recursion, where a problem is broken down into smaller, more manageable subproblems, and the solution is obtained by solving these subproblems and combining their results. The repetition of the function calls, each addressing a smaller part of the problem, gives rise to the term “recursive.”

General form of a recursive call

1
2
3
4
5
6
7
8
9

if (base case condition) { //calculate base without recursion
}
else {
}
// general case with recursive calls
// break the problem into a smaller problem of the same form
// solve the smaller problems by calling the recursive function.
// smaller solutions can be used to solve the larger problem
}

• It have 2 cases:

  • Base case - identify case that easily solvable (no need for recursion)
  • Recursive case - breaks problem into smaller problem of the same form

• eg: n - factorial

  • Pseudocode

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    //Recursive int fact(int n) { if(n==0) return 1.0; else return n*fact(n-1); } //Iterative int fact(int n) { int product=1; for(int j = 1; j <= n; j++) product *=j; return product; }

  • Anatomy of a recursive call

    • n=0 is base case
    • n>0 is recursive case

  • Tracing

• eg: summation

  copy

  1 2 3 4 5 6 7 8 9 10 11 12 13

  public class Main { public static void main(String[] args) { int result = sum(10); System.out.println(result); } public static int sum(int k) { if (k > 0) { return k + sum(k - 1); } else { return 0; } } }

  • When sum() function is called, it adds parameter k to the sum of all numbers < k until k = 0.
  • Tracing: 10 + sum(9) 10 + ( 9 + sum(8) ) 10 + ( 9 + ( 8 + sum(7) ) ) … 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0) 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

What are types of recursion?

• 1. Direct Recursion

  • Function calls itself within the same function repeatedly:

    • Tail recursion
      • The function call itself, the call is the last statement executed by the function before returning.
      • eg: Printing num down to 1
        copy

        1 2 3 4 5 6 7 8 9 10 11 12

        void fun1(int num) { // if block check the condition if (num == 0) return; else printf ("\n Number is: %d", num); // print the number return fun1(num - 1); // recursive call at the end in the fun() function } int main () { fun1(7); // pass 7 as integer argument return 0; }

    • Non-tail/ head recursion
      • Non-tail simply means every recursion that is not tail, one of which is head recursion (if the recursion doesn’t fit tail recursion, it’s non-tail)
      • The recursive call is the first statement in the function
      • eg: Print num down to 1
        copy

        1 2 3 4 5 6 7 8 9 10 11 12 13

        void head_fun (int num) { if ( num > 0 ) { // Here the head_fun() is the first statement to be called head_fun (num - 1); printf (" %d", num); } } int main () { int a = 5; printf (" Use of Non-Tail/Head Recursive function \n"); head_fun (a); // function calling return 0; }

  • Structure of direct recursion:

    copy

    1 2 3 4 5

    fun() { //some code fun(); //some code }

    • the outer fun() recursively calls the inner fun()

  • Eg: Finding fibonacci series

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

    int fibo_num (int i) { // if the num i is equal to 0, return 0; //base case if ( i == 0) { return 0; } //base case if ( i == 1) { return 1; } //recursive case return fibo_num (i - 1) + fibonacci (i -2); } int main () { int i; // use for loop to get the first 10 fibonacci series for ( i = 0; i < 10; i++) { printf (" %d \t ", fibo_num (i)); } return 0; }

• 2. Indirect Recursion

  • Function is mutually called by another function in a circular manner

  • Structure of indirect recursion:

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    fun1() { // write some code fun2() } fun2() { // write some code fun3() // write some code } fun3() { // write some code fun1() }

    • There are 3 functions, When the fun1() function is executed, it calls the fun2() for its execution. And then, the fun2() function starts its execution calls the fun3() function
    • Each function leads to another function to make their execution cicularly

  • Eg: Checking even or odd of 1 - 10;

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

    int num = 1; // global variable public void odd () { // if statement check and execute the block till n is less than equal to 10 if (num <= 10) { printf (" %d ", num + 1); // print a number by adding 1 num++; // increment by 1 even(); // invoke the even function } return; } public void even () { // if block check the condition that n is less than equal to 10 if ( num <= 10) { printf (" %d ", num - 1); // print a number by subtracting 1 num++; odd(); // call the odd() function } return; } public static void main (String[] args) { odd(); // main call the odd() function at once return 0; }

• 3. Nested Recursion
  • Recursive function calls itself with a recursive call as on of its arguments (the input parameter is the result of a recursive call)
  • eg: Ackerman function
    copy

    1 2 3 4 5 6 7 8 9

    public void int ackerman(int m, int n) { if(m == 0) { retunr n + 1; } else if(m > 0 && n == 0) { return ackerman(m - 1, 1) } else { return ackerman(m - 1, ackerman(m, n - 1)) } }

What is excessive recursion?

• A situation where recursion continues for an extended period, potentially leading to issue like stack overflow.
• eg
  copy

  1 2 3 4 5 6

  int fib(int n) { if (n<2) return n; else return fib(n-2) + fib(n-1); }

  

What are the applications of recursion?

• Fibonacci Series
• Linear Search
• Binary Search
• Quick Sort
• Merge Sort
• Tower of Hanoi
• Tree traversals
• Graph traversals

What are the advantage and disadvantage of recursive over iterative?

• Advantages
  • Code is simpler, shorter
  • Performs better in solving problems based on tree structures
• Disadvantages
  • Can throw a StackOverflow Exception since it consumes a lot of memory

Iteration to recursion

• Print reverse using of a linked list

  • Reverse linked list by iteration
  copy

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  package Q3.Q3_a; import java.util.LinkedList; public class reverseLinkedList { //reverse by iteration public static void printReverseByIteration (LinkedList<Integer> list) { int listLength = list.size(); for (int i = 0; i < listLength; i ++) { System.out.println(list.pollLast()); } } //funtion testing public static void main(String [] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); System.out.println("Reverse linked list by iteration: "); printReverseByIteration(list); } }

  • Reverse linked list by recursion

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

    package Q3.Q3_a; import java.util.LinkedList; public class reverseLinkedList { //reverse by recursion public static void printReverseByRecursion (LinkedList<Integer> list) { if (list.isEmpty()) { return; System.out.println(list.pollLast()); printReverseByIteration(list); } //funtion testing public static void main(String [] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); System.out.println("Reverse linked list by recursion: "); printReverseByRecursion(list); } }

    

• Sum of array elements

  • Sum of array by iteration

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

    package Q3.Q3_b; public class sumOfArray { //sum calculation using for loop public static int sumByIteration (int[] numArr) { int sum = 0; for (int i = 0; i < numArr.length; i++) { sum += numArr[i]; } return sum; } public static void main (String [] args) { int numArr[] = {1,2,3,4,5}; System.out.print(sumByIteration(numArr)); } }

  • Sum of array by recursion

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    sumOfArray{ //sum calculation using recursion public static int sumByRecursion (int[] numArr, int index) { if (index == numArr.length) { return 0; } //recursive case return numArr[index] + sumByRecursion(numArr, index + 1); } public static void main (String [] args) { int numArr[] = {1,2,3,4,5}; System.out.print(sumByRecursion(numArr, 0)); } }

• Reverse a stack

  • Reverse stack via iteration:

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

    class reverseByIteration { static void insertAtBottom(Stack<Integer> st, int x) { Stack<Integer> tmpStack2 = new Stack<>(); // Pop all elements from the original stack // and push them onto tmpStack2 while (!st.isEmpty()) { tmpStack2.push(st.pop()); } // Push the new element x onto the original stack st.push(x); // Pop all elements from tmpStack2 and push them // back onto the original stack while (!tmpStack2.isEmpty()) { st.push(tmpStack2.pop()); } } static void reverse(Stack<Integer> st) { Stack<Integer> tmpStack = new Stack<>(); // Pop all elements from the original stack and // push them onto tmpStack while (!st.isEmpty()) { tmpStack.push(st.pop()); } // Insert each element from tmpStack at the bottom of the original stack while (!tmpStack.isEmpty()) { int x = tmpStack.pop(); insertAtBottom(st, x); } } } public class reverseStack { public static void main (String [] args) { Stack<Integer> st = new Stack<>(); st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); // System.out.print("Original string: " + st); // reverseByRecursion.reverse(st); // System.out.print("\nReversed string " + st); System.out.print("Original string: " + st); reverseByIteration.reverse(st); System.out.print("\nReversed string using iteration:" + st); } }

  • Reverse stack via recursion:

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

    package Q3.Q3_c; import java.util.Stack; class reverseByRecursion{ static void insertAtBottom(Stack<Integer> st, int x) { //if stack is empty, insert directly to stack if (st.isEmpty()) { st.push(x); //if stack not empty, pop element, //store as tmp, //repeat until stack is empty. //push x, //push tmp } else { int tmp = st.peek(); st.pop(); insertAtBottom(st, x); st.push(tmp); } } static void reverse(Stack<Integer> st) { //if stack size not 0, //pop element, store as x; //when size = 0, //call insertAtBottom(x) //until the last element if (st.size() > 0) { int x = st.peek(); st.pop(); reverse(st); insertAtBottom(st, x); } } } public class reverseStack { public static void main (String [] args) { Stack<Integer> st = new Stack<>(); st.push(1); st.push(2); st.push(3); st.push(4); st.push(5); System.out.print("Original string: " + st); reverseByRecursion.reverse(st); System.out.print("\nReversed string using recursion" + st); } }

    

What is tree?

• A data type that consists of nodes and arcs
• These trees are depicted upside-down, the root at the top, the leaves(terminal nodes) at the bottom
• Basic terminologies
  • Parent node: Predecessor of a node (eg: 4 = 2; 8 = 4)
  • Child node: Immediate successor of a node (eg: 4 = 8, 9)
  • Root node: Topmost node (eg: 1)
  • Leaf/ terminal node: Nodes without children(eg: 8, 9, 10, 11, 13, 14)
  • Ancestor of a node: All predecessor of a node (eg: 8 = 4, 2, 1)
  • Descendants: child, grandchild, grand-grandchild(eg: 2 = 4, 8, 9, 5, 10, 11)
  • Sibling: Children of the same parent node(eg: 8 = 9)
  • Depth of a node: number of edges in path from root to node (eg: 4 = 2)
  • Level: 1 + Depth (eg: 4 = 3)
  • Height of a tree: Depth of the root; Number of edges on the longest downward path between root and a leaf (3)
  • Height of a node: No. of edges on the longest downward path between that node and a leaf (eg: 8 = 3)

What is binary tree?

• A tree whose nodes have at most two children, each node of a binary tree consists of:

  • data item
  • address of left child
  • address of right child

• max no of nodes at level i (root starts with level 1) = (2^i)-1

• What are the categories of binary tree?

  • Strict/ proper binary tree
    • Each node can only have either 2 or no children
  • Complete binary tree
    • Identical with full binary tree, with two differences:
      1. Every level must be completely filled except for the last level
      2. The last level has all values as left as possible
  • Perfect binary tree
    • All levels are completely filled
    • max no of nodes(elements) with height h = (2^(h+1))-1

• What are the types of binary trees?

  • Binary search tree

    • Its called search tree because it can be used to search for the number in O(log(n)) time

    • left child < parent

    • right child ≥ parent

    • Converting array into BST

      • If child ≥ parent, insert right
      • if child < parent, insert left
      • eg: converting sequence of number into BST

    • Deletion in BST

    • Searching in BST

      • On each node, if el < node, go down left, if el > node, go right

    • Implementation in JAVA

      copy

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116

      // Binary Search Tree operations in Java class BinarySearchTree { class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } Node root; BinarySearchTree() { root = null; } void insert(int key) { root = insertKey(root, key); } // Insert key in the tree Node insertKey(Node root, int key) { // Return a new node if the tree is empty if (root == null) { root = new Node(key); return root; } // Traverse to the right place and insert the node if (key < root.key) root.left = insertKey(root.left, key); else if (key > root.key) root.right = insertKey(root.right, key); return root; } void inorder() { inorderRec(root); } // Inorder Traversal void inorderRec(Node root) { if (root != null) { inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); } } void deleteKey(int key) { root = deleteRec(root, key); } Node deleteRec(Node root, int key) { // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key < root.key) root.left = deleteRec(root.left, key); else if (key > root.key) root.right = deleteRec(root.right, key); else { // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); } return root; } // Find the inorder successor int minValue(Node root) { int minv = root.key; while (root.left != null) { minv = root.left.key; root = root.left; } return minv; } // Driver Program to test above functions public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("\n\nAfter deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); } }

    • Complexity of BST

      Operation	Best Case Complexity
      Search	O(log n)
      Insertion	O(log n)
      Deletion	O(log n)

  • Heap

    • Properties
      • Complete binary tree — each level is completely filled, except for last level, it is filled from left to right
      • children ≤ parent
    • Converting array to heap
      • Always insert the new element at the end, and gradually move it upward if needed
      • Top-down method — John Williams Algorithm
        1. Insert the elements on the last, leftmost
        2. Heapify, repeat until the last element
        • Example
      • Bottom-up method - Floyd Algorithm
        1. Arrange the arrays into a binary tree
        2. Heapify, starting from the lowest parent, check for the largest child, swap with parent, work our way up
        • Pseudocode
          copy

          1 2 3 4 5

          FloydAlgorithm(data []) for i = index of the last nonlead, down to 0 p = data [i]; while p not a lead and p < any of its children swap p with the larger child

        • Example
    • Insertion
      1. Insert element at the end of the tree
      2. Heapify the tree
    • Deletion
      1. Delete the elements
      2. Replace with the lowest elements
      3. Heapify the tree
    • Heap representation using array

      Parent	Left child	RIght child
      i	(2 * i) + 1	(2 * i) + 1

• How to traverse a tree? https://www.youtube.com/watch?v=IpyCqRmaKW4&ab_channel=GeeksforGeeks

  • Process of visiting each node in the tree exactly one time in some order

  • Breadth-First Traversal (BFT)

    • Nodes on each level is read from left to right, from top to bottom

    • Logical approach:

      • Start from the root, a queue is initialized with root, root is dequeued, its child is enqueued
      • The elements in queue is dequeued one at a time, and its child in enqueued
      • Process is repeated until queue is empty

    • Tracing

    • Implementation

      copy

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

      import java.util.ArrayDeque; import java.util.Deque; import java.util.Queue; class Node { int data; Node left, right; public Node(int data) { this.data = data; this.left = this.right = null; } } public class BFTTraversal { static void BFTraversal(Node root) { if (root == null) { return; } Queue<Node> queue = new ArrayDeque<>(); queue.add(root); while (!queue.isEmpty()) { Node tempNode = queue.poll(); System.out.print(tempNode.data + " "); //enque left child if (tempNode.left != null) { queue.add(tempNode.left); } //enque right child if (tempNode.right != null) { queue.add(tempNode.right); } } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); System.out.println("Breadth First Traversal (using ArrayDeque): "); BFTraversal(root); } }

  • Depth-First Traversal (DFT)

    • Preorder traversal

      copy

      1 2 3 4 5 6 7 8 9 10 11 12 13 14

      void printPreorder(Node node) { if (node == null) return; // First print data of node System.out.print(node.key + " "); // Then recur on left subtree printPreorder(node.left); // Now recur on right subtree printPreorder(node.right); }

      • eg
        • Preorder: ABDEFC
        • step-by-step explanation
          1. at A, print A, read A.left
          2. at B, print B, read B.left
          3. at D, print D, read D.left
          4. D.left is null, return, read D.right
          5. D.right is null, return, read B.right
          6. at E, print E, read E.left
          7. at F, print F, read F.left
          8. F.left is null, return, read E.right
          9. E.right is null, return, read A.right
          10. at C, print C, read C.left
          11. C.left is null, return, read C.right
          12. C.tight is null, return

    • Inorder traversal

      copy

      1 2 3 4 5 6 7 8 9 10 11 12 13 14

      void printInorder(Node node) { if (node == null) return; // First recur on left child printInorder(node.left); // Then print the data of node System.out.print(node.key + " "); // Recur on right child printInorder(node.right); }

      • eg
        • Inorder: DBFEAC
        • step-by-step explagnation
          1. at A, read A.left
          2. at B, read B.left
          3. at D, read D.left
          4. D.left is null, return, print D
          5. D.right is null, return
          6. at B, print B, read B.right
          7. at E, read E.left
          8. at F, read F.left
          9. F.left is null, return, print F
          10. at F, read F.right
          11. F.right is null, return
          12. at E, print E, read E.right
          13. E.right is null, return
          14. at A, print A, read A.right
          15. at C, read C.left
          16. C.left is null, return, print C, read C.right
          17. C.right is null, return

    • Postorder traversal

      copy

      1 2 3 4 5 6 7 8 9 10 11 12 13 14

      void printPostorder(Node node) { if (node == null) return; // First recur on left subtree printPostorder(node.left); // Then recur on right subtree printPostorder(node.right); // Now deal with the node System.out.print(node.key + " "); }

      • eg
        • postorder: DFEBCA
        • step-by-step explanation
          1. at A, read A.left
          2. at B, read B.left
          3. at D. read D.left
          4. D.left is null, return, read D.right
          5. D.right is null, return, print D
          6. at B, read B.right
          7. at E, read E.left
          8. at F, read F.left
          9. F.left is null, return, read F.right
          10. F.right is null, return, print F
          11. at E, read E.right
          12. E.right is null, return, print E
          13. at B, print B
          14. at A, read A.right
          15. at C, read C.left
          16. C.left is null, return, read C.right
          17. C.right is null, return, print C
          18. at A, print A

• Implementing binary trees

  • Array

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

    public class BinaryTreeArray { private int[] treeArray; private int size; public BinaryTreeArray(int capacity) { treeArray = new int[capacity]; size = 0; } // Insert a new element into the binary tree public void insert(int data) { if (size < treeArray.length) { treeArray[size] = data; size++; } else { System.out.println("Binary tree is full. Cannot insert more elements."); } } // Display the elements using in-order traversal public void inOrderTraversal(int index) { if (index < size) { inOrderTraversal(2 * index + 1); // Left child System.out.print(treeArray[index] + " "); inOrderTraversal(2 * index + 2); // Right child } } public static void main(String[] args) { BinaryTreeArray binaryTree = new BinaryTreeArray(10); binaryTree.insert(1); binaryTree.insert(2); binaryTree.insert(3); binaryTree.insert(4); binaryTree.insert(5); System.out.println("In-order traversal:"); binaryTree.inOrderTraversal(0); } }

  • Node-based

    copy

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

    // Node creation class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } class BinaryTree { Node root; BinaryTree(int key) { root = new Node(key); } BinaryTree() { root = null; } // Traverse Inorder public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); } } // Traverse Postorder public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); } } // Traverse Preorder public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); } } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); System.out.print("Pre order Traversal: "); tree.traversePreOrder(tree.root); System.out.print("\nIn order Traversal: "); tree.traverseInOrder(tree.root); System.out.print("\nPost order Traversal: "); tree.traversePostOrder(tree.root); } }