Author Archives: graceliana@gmail.com

The great tree-list recursion problem

Screen Shot 2015-02-09 at 12.56.51 AM

The great tree-list recursion problem. A binary search tree and a circular doubly linked list are conceptually built from the same type of nodes – a data field and two references to other nodes.

Given a binary search tree, rearrange the references so that it becomes a circular doubly-linked list (in sorted order). Nick Parlante describes this as one of the neatest recursive pointer problems ever devised.

Hint: create a circularly linked list A from the left subtree, a circularly linked list B from the right subtree, and make the root a one-node circularly linked list. Then merge the three lists.

Screen Shot 2015-02-22 at 1.50.19 PM

ResizingArrayBag.java

/******************************************************************************
 *  Compilation:  javac ResizingArrayBag.java
 *  Execution:    java ResizingArrayBag
 *  Dependencies: StdIn.java StdOut.java
 *  
 *  Bag implementation with a resizing array.
 *
 ******************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  The {@code ResizingArrayBag} class represents a bag (or multiset) of 
 *  generic items. It supports insertion and iterating over the 
 *  items in arbitrary order.
 *  <p>
 *  This implementation uses a resizing array.
 *  See {@link LinkedBag} for a version that uses a singly linked list.
 *  The <em>add</em> operation takes constant amortized time; the
 *  <em>isEmpty</em>, and <em>size</em> operations
 *  take constant time. Iteration takes time proportional to the number of items.
 *  <p>
 *  For additional documentation, see <a href="https://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class ResizingArrayBag<Item> implements Iterable<Item> {
    // initial capacity of underlying resizing array
    private static final int INIT_CAPACITY = 8;

    private Item[] a;         // array of items
    private int n;            // number of elements on bag

    /**
     * Initializes an empty bag.
     */
    public ResizingArrayBag() {
        a = (Item[]) new Object[INIT_CAPACITY];
        n = 0;
    }

    /**
     * Is this bag empty?
     * @return true if this bag is empty; false otherwise
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * Returns the number of items in this bag.
     * @return the number of items in this bag
     */
    public int size() {
        return n;
    }

    // resize the underlying array holding the elements
    private void resize(int capacity) {
        assert capacity >= n;
        Item[] copy = (Item[]) new Object[capacity];
        for (int i = 0; i < n; i++)
            copy[i] = a[i];
        a = copy;
    }

    /**
     * Adds the item to this bag.
     * @param item the item to add to this bag
     */
    public void add(Item item) {
        if (n == a.length) resize(2*a.length);    // double size of array if necessary
        a[n++] = item;                            // add item
    }


    /**
     * Returns an iterator that iterates over the items in the bag in arbitrary order.
     * @return an iterator that iterates over the items in the bag in arbitrary order
     */
    public Iterator<Item> iterator() {
        return new ArrayIterator();
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ArrayIterator implements Iterator<Item> {
        private int i = 0;
        public boolean hasNext()  { return i < n;                               }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            return a[i++];
        }
    }

    /**
     * Unit tests the {@code ResizingArrayBag} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        ResizingArrayBag<String> bag = new ResizingArrayBag<String>();
        bag.add("Hello");
        bag.add("World");
        bag.add("how");
        bag.add("are");
        bag.add("you");

        for (String s : bag)
            StdOut.println(s);
    }

}

Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne.
Last updated: Sun Sep 6 14:02:50 EDT 2020.

Hellooo!!

Hi,
I am wondering how you are doing. Do you have any questions on any of the assignments? Are the videos helping? I truly appreciate all the work some of you have done!!
Animated GIF
For those who have no turned in much… What in the name of God are you working on?! 🤔🤷‍♀️
You do know I have been on zoom every week on F days 9:30 to 10:30 but I can change it to 2:30We only have 2 F days left, 5th and 9th.
Animated GIF
Then all periods are meeting on the 10th and the last day of school, the 16th!
For many of you, I will not see you next school year.
Animated GIF  and ……. for some
Animated GIF
Stay healthy. Stay safe.
mrs.e loves you!
Animated GIF

Queue ADT

/*************************************************************************
 *  Compilation:  javac Queue.java
 *  Execution:    java Queue < input.txt
 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt  
 *
 *  A generic queue, implemented using a linked list.
 *
 *  % java Queue < tobe.txt 
 *  to be or not to be (2 left on queue)
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  The Queue class represents a first-in-first-out (FIFO)
 *  queue of generic items.
 *  It supports the usual enqueue and dequeue
 *  operations, along with methods for peeking at the first item,
 *  testing if the queue is empty, and iterating through
 *  the items in FIFO order.
 *  
 *  This implementation uses a singly-linked list with a static nested class for
 *  linked-list nodes. See LinkedQueue for the version from the
 *  textbook that uses a non-static nested class.
 *  The enqueue, dequeue, peek, size, and is-empty
 *  operations all take constant time in the worst case.
 *  
 *  For additional documentation, see      
 *  http://algs4.cs.princeton.edu/13stacks 
 *  Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 */
public class Queue implements Iterable{
   private Node first; // beginning of queue
   private Node last; // end of queue
   private int n; // number of elements on queue

    // helper linked list class
    private static class Node<item> {
        private Item item;
        private Node<item> next;
    }

    /**
     * Initializes an empty queue.
     */
    public Queue() {
        first = null;
        last  = null;
        N = 0;
    }

    /**
     * Is this queue empty?
     * @return true if this queue is empty; false otherwise
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * Returns the number of items in this queue.
     * @return the number of items in this queue
     */
    public int size() {
        return N;     
    }

    /**
     * Returns the item least recently added to this queue.
     * @return the item least recently added to this queue
     * @throws java.util.NoSuchElementException if this queue is empty
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return first.item;
    }

    /**
     * Adds the item to this queue.
     * @param item the item to add
     */
    public void enqueue(Item item) {
        Node<item> oldlast = last;
        last = new Node<item>();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else           oldlast.next = last;
        N++;
    }

    /**
     * Removes and returns the item on this queue that was least recently added.
     * @return the item on this queue that was least recently added
     * @throws java.util.NoSuchElementException if this queue is empty
     */
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = first.item;
        first = first.next;
        N--;
        if (isEmpty()) last = null;   // to avoid loitering
        return item;
    }

    /**
     * Returns a string representation of this queue.
     * @return the sequence of items in FIFO order, separated by spaces
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    } 

    /**
     * Returns an iterator that iterates over the items in this queue in FIFO order.
     * @return an iterator that iterates over the items in this queue in FIFO order
     */
    public Iterator<item> iterator()  {
        return new ListIterator<item>(first);  
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ListIterator<item> implements Iterator<item> {
        private Node<item> current;

        public ListIterator(Node<item> first) {
            current = first;
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }


    /**
     * Unit tests the Queue data type.
     */
    public static void main(String[] args) {
        Queue<string> q = new Queue<string>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) q.enqueue(item);
            else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
        }
        StdOut.println("(" + q.size() + " left on queue)");
    }
}


Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. 
Last updated: Tue Sep 24 09:59:27 EDT 2013.

Queue ADT

Iteration. As mentioned earlier in this section, one of the fundamental operations on collections is to process each item by iterating through the collection using Java’s foreach statement. This paradigm leads to clear and compact code that is free from dependence on the details of a collection’s implementation. To consider the task of implementing iteration, we start with a snippet of client code that prints all of the items in a collection of strings, one per line:

     Stack<String> collection = new Stack<String>();
      …
     for (String s : collection)
          StdOut.println(s);
      …

 

Now, this foreach statement is shorthand for a while construct (just like the for statement itself). It is essentially equivalent to the following while statement:

Iterator<String> i = collection.iterator(); while (i.hasNext())
{
     String s = i.next();
     StdOut.println(s);
}

This code exposes the ingredients that we need to implement in any iterable collection:

  • The collection must implement an iterator() method that returns an Iterator object.
  • The Iterator class must include two methods: hasNext() (which returns a boolean value) and next() (which returns a generic item from the collection). In Java, we use the interface mechanism to express the idea that a class implements a specific method (see page 100). For iterable collections, the necessary interfaces are already defined for us in Java. To make a class iterable, the first step is to add the phrase implements Iterable<Item> to its declaration, matching the interface

        public interface Iterable<Item>
       {
            Iterator<Item> iterator();
       }

(which is in java.lang.Iterable), and to add a method iterator() to the class that returns an Iterator<Item>. Iterators are generic, so we can use our parameterized type Item to allow clients to iterate through objects of whatever type is provided by our client.

Stack ADT



Below is the syntax highlighted version of Stack.java from § Algorithms.   Here is the Javadoc.


/*************************************************************************
 *  Compilation:  javac Stack.java
 *  Execution:    java Stack < input.txt
 *
 *  A generic stack, implemented using a singly-linked list.
 *  Each stack element is of type Item.
 *
 *  This version uses a static nested class Node (to save 8 bytes per
 *  Node), whereas the version in the textbook uses a non-static nested
 *  class (for simplicity).
 *  
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java Stack < tobe.txt
 *  to be not that or be (2 left on stack)
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;


/**
 *  The Stack class represents a last-in-first-out (LIFO) stack of generic items.
 *  It supports the usual push and pop operations, along with methods
 *  for peeking at the top item, testing if the stack is empty, and iterating through
 *  the items in LIFO order.
 *  

* This implementation uses a singly-linked list with a static nested class for * linked-list nodes. See {@link LinkedStack} for the version from the * textbook that uses a non-static nested class. * The push, pop, peek, size, and is-empty * operations all take constant time in the worst case. *

* For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Stack implements Iterable { private int N; // size of the stack private Node first; // top of stack // helper linked list class private static class Node { private Item item; private Node next; } /** * Initializes an empty stack. */ public Stack() { first = null; N = 0; } /** * Is this stack empty? * @return true if this stack is empty; false otherwise */ public boolean isEmpty() { return first == null; } /** * Returns the number of items in the stack. * @return the number of items in the stack */ public int size() { return N; } /** * Adds the item to this stack. * @param item the item to add */ public void push(Item item) { Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; N++; } /** * Removes and returns the item most recently added to this stack. * @return the item most recently added * @throws java.util.NoSuchElementException if this stack is empty */ public Item pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); Item item = first.item; // save item to return first = first.next; // delete first node N--; return item; // return the saved item } /** * Returns (but does not remove) the item most recently added to this stack. * @return the item most recently added to this stack * @throws java.util.NoSuchElementException if this stack is empty */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return first.item; } /** * Returns a string representation of this stack. * @return the sequence of items in the stack in LIFO order, separated by spaces */ public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) s.append(item + " "); return s.toString(); } /** * Returns an iterator to this stack that iterates through the items in LIFO order. * @return an iterator to this stack that iterates through the items in LIFO order. */ public Iterator iterator() { return new ListIterator(first); } // an iterator, doesn't implement remove() since it's optional private class ListIterator implements Iterator { private Node current; public ListIterator(Node first) { current = first; } public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; } } /** * Unit tests the Stack data type. */ public static void main(String[] args) { Stack s = new Stack(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) s.push(item); else if (!s.isEmpty()) StdOut.print(s.pop() + " "); } StdOut.println("(" + s.size() + " left on stack)"); } } Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. Last updated: Tue Sep 24 10:43:42 EDT 2013.

ResizingArrayStack ADT

/*************************************************************************
 *  Compilation:  javac ResizingArrayStack.java
 *  Execution:    java ResizingArrayStack < input.txt
 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt
 *  
 *  Stack implementation with a resizing array.
 *
 *  % more tobe.txt 
 *  to be or not to - be - - that - - - is
 *
 *  % java ResizingArrayStack < tobe.txt
 *  to be not that or be (2 left on stack)
 *
 *************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  The ResizingArrayStack class represents a last-in-first-out (LIFO) stack
 *  of generic items.
 *  It supports the usual push and pop operations, along with methods
 *  for peeking at the top item, testing if the stack is empty, and iterating through
 *  the items in LIFO order.
 *  

* This implementation uses a resizing array, which double the underlying array * when it is full and halves the underlying array when it is one-quarter full. * The push and pop operations take constant amortized time. * The size, peek, and is-empty operations takes * constant time in the worst case. * * For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class ResizingArrayStack implements Iterable { private Item[] a; // array of items private int N; // number of elements on stack /** * Initializes an empty stack. */ public ResizingArrayStack() { a = (Item[]) new Object[2]; } /** * Is this stack empty? * @return true if this stack is empty; false otherwise */ public boolean isEmpty() { return N == 0; } /** * Returns the number of items in the stack. * @return the number of items in the stack */ public int size() { return N; } // resize the underlying array holding the elements private void resize(int capacity) { assert capacity >= N; Item[] temp = (Item[]) new Object[capacity]; for (int i = 0; i < N; i++) { temp[i] = a[i]; } a = temp; } /** * Adds the item to this stack. * @param item the item to add */ public void push(Item item) { if (N == a.length) resize(2*a.length); // double size of array if necessary a[N++] = item; // add item } /** * Removes and returns the item most recently added to this stack. * @return the item most recently added * @throws java.util.NoSuchElementException if this stack is empty */ public Item pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); Item item = a[N-1]; a[N-1] = null; // to avoid loitering N--; // shrink size of array if necessary if (N > 0 && N == a.length/4) resize(a.length/2); return item; } /** * Returns (but does not remove) the item most recently added to this stack. * @return the item most recently added to this stack * @throws java.util.NoSuchElementException if this stack is empty */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return a[N-1]; } /** * Returns an iterator to this stack that iterates through the items in LIFO order. * @return an iterator to this stack that iterates through the items in LIFO order. */ public Iterator iterator() { return new ReverseArrayIterator(); } // an iterator, doesn't implement remove() since it's optional private class ReverseArrayIterator implements Iterator { private int i; public ReverseArrayIterator() { i = N; } public boolean hasNext() { return i > 0; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return a[--i]; } } /** * Unit tests the Stack data type. */ public static void main(String[] args) { ResizingArrayStack s = new ResizingArrayStack(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) s.push(item); else if (!s.isEmpty()) StdOut.print(s.pop() + " "); } StdOut.println("(" + s.size() + " left on stack)"); } } Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne. Last updated: Mon Oct 7 11:58:25 EDT 2013.