import java.util.Iterator;
public class ResizingArrayStack<Item> implements Iterable<Item>
{
private Item[] a = (Item[]) new Object[1];
private int N = 0;
public boolean isEmpty() { return N == 0;}
public int size() { return N; }
private void resize(int max) {
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++)
temp[i] = a[i];
a = temp;
}
public void push(Item item)
{
if (N == a.length) resize(2*a.length);
a[N++] = item;
}
public Item pop() {
Item item = a[--N];
a[N] = null;
if (N > 0 && N == a.length/4) resize(a.length/2);
return item;
}
public Iterator<Item> iterator()
{ return new ReverseArrayIterator(); }
private class ReverseArrayIterator implements Iterator<Item>
{
private int i = N;
public boolean hasNext() { return i > 0; }
public Item next() { return a[i--]; }
public void remove() { }
}
}
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>
{
private Node first;
private int N;
private class Node
{
Item item;
Node next;
}
public boolean isEmpty() { return first == null; }
public int size() { return N; }
public void push(Item item)
{ //add to top
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop()
{ //remove from top
Item item = first.item;
first = first.next;
N--;
return item;
}
public Iterator<Item> iterator()
{ return new ListIterator(); }
private class ListIterator implements Iterator<Item>
{
private Node current = first;
public boolean hasNext()
{ return current != null; }
public void remove() {}
public Item next()
{
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-"))
stack.push(item);
else if (!stack.isEmpty())
StdOut.print(stack.pop() + " ");
}
StdOut.println("(" + stack.size() + " left on stack)");
}
}
import java.util.Iterator;
public class Queue<Item> implements Iterable<Item> {
private Node first;
private Node last;
private int N;
private class Node {
private Item item;
private Node next;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public void enqueue(Item item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
N++;
}
public Item dequeue() {
Item item = first.item;
first = first.next;
N--;
if (isEmpty()) last = null;
return item;
}
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { }
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
Queue<String> queue = new Queue<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-"))
queue.enqueue(item);
else if (!queue.isEmpty())
StdOut.print(queue.dequeue() + " ");
}
StdOut.println("(" + queue.size() + " left on queue)");
}
}
import java.util.Iterator;
public class Bag<Item> implements Iterable<Item> {
private Node first;
private static class Node<Item> {
private Item item;
private Node next;
}
public void add(Item item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}
public Iterator<Item> iterator()
{ return new ListIterator<Item>(first); }
private class ListIterator implements Iterator<Item>
{
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { }
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
public class UF
{
private int[] id;
private int count;
public UF(int N)
{
count =N;
id = new int[N];
for (int i=0; i <N; i++)
id[i] =i;
}
public int count()
{ return count;}
public boolean connected(int p, int q)
{ return find(p)==find(q);}
public int find(int p)
public void union(int p, int q)
/// qick
public static void main (String[] args )
{
int N = StdIn.readInt();
UF uf = new UF(N);
while (!StdIn.isEmpty())
{
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.connected(p, q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
public class WQUUF {
private int[] id;
private int[] sz;
private int count;
public WQUUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < n; i++) id[i] = i;
sz = new int[N];
for (int i = 0; i < n; i++) sz[i] = 1;
}
public int count() { return count; }
public boolean connected(int p, int q)
{ return find(p) == find(q); }
public int find(int p)
{
while (p != id[p])
p = id[p];
return p;
}
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
else { id[j] = i; sz[i] += sz[j]; }
count--;
}
}
public class Selection
{
public static void sort(Comparable[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
{
int min = i;
for (int j = i+1; j < N; j++)
if (less(a[j], a[min])) min = j;
exch(a, i, min);
}
}
// less(), exch(), isSOrted(), main()
}
public class Insertion
{
public static void sort(Comparable[] a)
{
int N = a.length;
for (int i = 1; i < N; i++)
{
for (int j = i; j > 0 && less(a[j], a[j-1]; j--)
exch(a, j, j-1);
}
}
// less(), exch(), isSorted(), main()
}
public class Shell
{
public static void sort(Comparable[] a)
{
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1;
while (h >= 1)
{
for (int i = h; i < N; i++)
{
for (int j = i; j >= h && less(a[j], a[j-h]; j -= h)
exch(a, j, j-h);
}
h = h/3;
}
}
}
public class Merge
{
private static Comparable[] aux;
public static void sort(Comparable[] a)
{
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid);
sort(a, mid+1, hi);
merge(a, lo, mid, hi);
}
public static void merge(Comparable[] a, int lo, int mid, int hi)
{
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++)
aux[k] = a[k];
for (int k = lo; k <= hi; k++)
if (i > mid) a[k] = aux[j++];
else if (j > hi ) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
public class Quick
{
public static void sort(Comparable[] a)
{
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}
private static int partition(Comparable[] a, int lo, int hi)
{
int i = lo, j = hi+1;
Comparable v = a[lo];
while (true)
{
while (less(a[++i], v)) if (i == hi) break;
while (less(v, a[--j])) if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
}
public class MaxPQ<Key extends Comparable<Key>>
{
private Key[] pq;
private int N = 0;
public MaxPQ(int maxN)
{ pq = (Key[]) new Comparable[maxN+1]; }
public boolean isEmpty()
{ return N == 0; }
public int size()
{ return N; }
public void insert(Key v)
{
pq[++N] = v;
swim(N);
}
public Key delMax()
{
Key max = pq[1];
exch(1, N--);
pq[N+1] = null;
sink(1);
return max;
}
private boolean less(int i, int j)
{ return pq[i].compareTo(pq[j]) < 0; }
private void exch(int i, int j)
{ Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }
private void swim(int k)
{
while (k > 1 && less(k/2, k))
{
exch(k/2, k);
k = k/2;
}
}
private void sink(int k)
{
while (2*k <= N)
{
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
}
public static void sort(Comparable[] a)
{
int N = a.length;
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1)
{
exch(a, 1, N--);
sink(a, 1, N);
}
}
public class SequentialSearchST<Key, Value>
{
private Node first;
private class Node
{
Key key;
Value val;
Node next;
public Node(Key key, Value val, Node next)
{
this.key = key;
this.val = val;
this.next = next;
}
}
public Value get(Key key)
{
for (Node x = first; x != null; x = x.next)
if (key.equals(x.key))
return x.val;
return null;
}
public void put(Key key, Value val)
{
for (Node x = first; x != null; x = x.next)
if (key.equals(x.key))
{ x.val = val; return; }
first = new Node(key, val, first);
}
}
public class BinarySearchST<Key extends Comparable<Key>, Value>
{
private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int capacity)
{ // See Algorithm 1.1
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}
public int size()
{ return N; }
public Value get(Key key)
{
if (isEmpty()) return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) return vals[i];
else return null;
}
public int rank(Key key)
// See page 381.
public void put(Key key, Value val)
{
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0)
{ vals[i] = val; return; }
for (int j = N; j > i; j--)
{ keys[j] = keys[j-1]; vals[j] = vals[j-1]; }
keys[i] = key; vals[i] = val;
N++;
}
public void delete(Key key)
// Exercise 3.1.16
}
public int rank(Key key)
{
int lo = 0, hi = N-1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0) hi = mid - 1;
else if (cmp > 0) lo = mid + 1;
else return mid;
}
return lo;
}
public Key min()
{ return keys[0]; }
public Key max()
{ return keys[N-1]; }
public Key select(int k)
{ return keys[k]; }
public Key ceiling(Key key)
{
int i = rank(key);
return keys[i];
}
public Key floor(Key key)
// See Exercise 3.1.17.
public Key delete(Key key)
// See Exercise 3.1.16.
public Iterable<Key> keys(Key lo, Key hi)
{
Queue<Key> q = new Queue<Key>();
for (int i = rank(lo); i < rank(hi); i++)
q.enqueue(keys[i]);
if (contains(hi))
q.enqueue(keys[rank(hi)]);
return q;
}
public class BST<Key extends Comparable<Key>, Value>
{
private Node root; // root of BST
private class Node
{
private Key key; // key
private Value val; // associated value
private Node left, right; // links to subtrees
private int N; // # nodes in subtree rooted here
public Node(Key key, Value val, int N)
{ this.key = key; this.val = val; this.N = N; }
}
public int size()
{ return size(root); }
private int size(Node x)
{
if (x == null) return 0;
else return x.N;
}
public Value get(Key key)
// See page 399.
public void put(Key key, Value val)
// See page 399.
// See page 407 for min(), max(), floor(), and ceiling().
// See page 409 for select() and rank().
// See page 411 for delete(), deleteMin(), and deleteMax().
// See page 413 for keys().
}
public Value get(Key key)
{ return get(root, key); }
private Value get(Node x, Key key)
{ // Return value associated with key in the subtree rooted at x;
// return null if key not present in subtree rooted at x.
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x.val;
}
public void put(Key key, Value val)
{ // Search for key. Update value if found; grow table if new.
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val)
{
// Change key’s value to val if key in subtree rooted at x.
// Otherwise, add new node to subtree associating key with val.
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);
else if (cmp > 0) x.right = put(x.right, key, val);
else x.val = val;
x.N = size(x.left) + size(x.right) + 1;
return x;
}
public Key min()
{
return min(root).key;
}
private Node min(Node x)
{
if (x.left == null) return x;
return min(x.left);
}
public Key floor(Key key)
{
Node x = floor(root, key);
if (x == null) return null;
return x.key;
}
private Node floor(Node x, Key key)
{
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x;
if (cmp < 0) return floor(x.left, key);
Node t = floor(x.right, key);
if (t != null) return t;
else return x;
}
public Key select(int k)
{
return select(root, k).key;
}
private Node select(Node x, int k)
{ // Return Node containing key of rank k.
if (x == null) return null;
int t = size(x.left);
if (t > k) return select(x.left, k);
else if (t < k) return select(x.right, k-t-1);
else return x;
}
public int rank(Key key)
{ return rank(key, root); }
private int rank(Key key, Node x)
{ // Return number of keys less than key in the subtree rooted at x.
if (x == null) return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0) return rank(key, x.left);
else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
else return size(x.left);
}
public void deleteMin()
{
root = deleteMin(root);
}
private Node deleteMin(Node x)
{
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
public void delete(Key key)
{ root = delete(root, key); }
private Node delete(Node x, Key key)
{
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);
else if (cmp > 0) x.right = delete(x.right, key);
else
{
if (x.right == null) return x.left;
if (x.left == null) return x.right;
Node t = x;
x = min(t.right); // See page 407.
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}
public Iterable<Key> keys()
{ return keys(min(), max()); }
public Iterable<Key> keys(Key lo, Key hi)
{
Queue<Key> queue = new Queue<Key>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, Queue<Key> queue, Key lo, Key hi)
{
if (x == null) return;
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) keys(x.left, queue, lo, hi);
if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
if (cmphi > 0) keys(x.right, queue, lo, hi);
}
public class RedBlackBST<Key extends Comparable<Key>, Value>
{
private Node root;
private class Node // BST node with color bit (see page 433)
private boolean isRed(Node h) // See page 433.
private Node rotateLeft(Node h) // See page 434.
private Node rotateRight(Node h) // See page 434.
private void flipColors(Node h) // See page 436.
private int size() // See page 398.
public void put(Key key, Value val)
{ // Search for key. Update value if found; grow table if new.
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val)
{
if (h == null) // Do standard insert, with red link to parent.
return new Node(key, val, 1, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
}
public class SeparateChainingHashST<Key, Value>
{
private int M; // hash table size
private SequentialSearchST<Key, Value>[] st; // array of ST objects
public SeparateChainingHashST()
{ this(997); }
public SeparateChainingHashST(int M)
{ // Create M linked lists.
this.M = M;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
for (int i = 0; i < M; i++)
st[i] = new SequentialSearchST();
}
private int hash(Key key)
{ return (key.hashCode() & 0x7fffffff) % M; }
public Value get(Key key)
{ return (Value) st[hash(key)].get(key); }
public void put(Key key, Value val)
{ st[hash(key)].put(key, val); }
public Iterable<Key> keys()
// See Exercise 3.4.19.
}
public class LinearProbingHashST<Key, Value>
{
private int N; // number of key-value pairs in the table
private int M = 16; // size of linear-probing table
private Key[] keys; // the keys
private Value[] vals; // the values
public LinearProbingHashST()
{
keys = (Key[]) new Object[M];
vals = (Value[]) new Object[M];
}
private int hash(Key key)
{ return (key.hashCode() & 0x7fffffff) % M; }
private void resize() // See page 474.
public void put(Key key, Value val)
{
if (N >= M/2) resize(2*M); // double M (see text)
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % M)
if (keys[i].equals(key)) { vals[i] = val; return; }
keys[i] = key;
vals[i] = val;
N++;
}
public Value get(Key key)
{
for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
if (keys[i].equals(key))
return vals[i];
return null;
}
}
public class LookupIndex
{
public static void main(String[] args)
{
In in = new In(args[0]); // index database
String sp = args[1]; // separator
ST<String, Queue<String>> st = new ST<String, Queue<String>>();
ST<String, Queue<String>> ts = new ST<String, Queue<String>>();
while (in.hasNextLine())
{
String[] a = in.readLine().split(sp);
String key = a[0];
for (int i = 1; i < a.length; i++)
{
String val = a[i];
if (!st.contains(key)) st.put(key, new Queue<String>());
if (!ts.contains(val)) ts.put(val, new Queue<String>());
st.get(key).enqueue(val);
ts.get(val).enqueue(key);
}
}
while (!StdIn.isEmpty())
{
String query = StdIn.readLine();
if (st.contains(query))
for (String s : st.get(query))
StdOut.println(" " + s);
if (ts.contains(query))
for (String s : ts.get(query))
StdOut.println(" " + s);
}
}
}
import java.io.File;
public class FileIndex
{
public static void main(String[] args)
{
ST<String, SET<File>> st = new ST<String, SET<File>>();
for (String filename : args)
{
File file = new File(filename);
In in = new In(file);
while (!in.isEmpty())
{
String word = in.readString();
if (!st.contains(word)) st.put(word, new SET<File>());
SET<File> set = st.get(word);
set.add(file);
}
}
while (!StdIn.isEmpty())
{
String query = StdIn.readString();
if (st.contains(query))
for (File file : st.get(query))
StdOut.println(" " + file.getName());
}
}
}
public class SparseVector
{
private HashST<Integer, Double> st;
public SparseVector()
{ st = new HashST<Integer, Double>(); }
public int size()
{ return st.size(); }
public void put(int i, double x)
{ st.put(i, x); }
public double get(int i)
{
if (!st.contains(i)) return 0.0;
else return st.get(i);
}
public double dot(double[] that)
{
double sum = 0.0;
for (int i : st.keys())
sum += that[i]*this.get(i);
return sum;
}
}
Depth-first search to find connected components in a graph
[szerkesztés]Kosaraju—Sharir algorithm for computing strong components
[szerkesztés] 
