Quick Select - Coursera Algorithms

Quick select finds k^th smallest element by partitioning. It takes linear time and O(N²) in worst case.

Following is the program:

	package sorting.quickSort;
	public class QuickSelect {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static int partition(Comparable[] a, int lo, int hi) {
	int i=lo,j=hi+1;
	while(true) {
	while(less(a[++i],a[lo])) {
	if(i==hi) break;
	}
	while(less(a[lo],a[--j])) {
	if(j==lo) break;
	}
	if(i>=j) break;
	exchange(a,i,j);
	}
	exchange(a,lo,j);
	return j;
	}
	public static Comparable select(Comparable[] a, int k) {
	shuffle(a);
	int lo = 0, hi = a.length - 1;
	while (hi > lo)
	{
	int j = partition(a, lo, hi);
	if (j < k) lo = j + 1;
	else if (j > k) hi = j - 1;
	else return a[k];
	}
	return a[k];
	}
	public static void main(String[] args) {
	Comparable[] a1 = {5,2,4,6,1,3};
	int i = 3;
	System.out.println("element at index "+i+ " is "+ select(a1,i));
	}
	}

view raw QuickSelect.java hosted with ❤ by GitHub

Quick Sort - Coursera Algorithms

Quick Sort uses a partition element, such that the there are no larger entries to it's left and no smaller entries to it's right. It is in place, but not a stable sort.

Time complexity: O(NlgN)
Worst case : O(N²)

Following is the program:

	package sorting.quickSort;
	import sorting.insertionSort.InsertionSort;
	public class QuickSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static int partition(Comparable[] a, int lo, int hi) {
	int i=lo,j=hi+1;
	while(true) {
	while(less(a[++i],a[lo])) {
	if(i==hi) break;
	}
	while(less(a[lo],a[--j])) {
	if(j==lo) break;
	}
	if(i>=j) break;
	exchange(a,i,j);
	}
	exchange(a,lo,j);
	return j;
	}
	public static void sort(Comparable[] a, int lo, int hi) {
	int cutoff=7;
	if(hi<=lo+ cutoff -1) {
	InsertionSort is = new InsertionSort();
	is.sort(a);
	}
	if(hi<=lo) return;
	//int m = median(a,lo,lo+(hi-lo)/2,hi);
	//exchange(a, lo, m);
	int p = partition(a,lo,hi);
	sort(a,lo,p-1);
	sort(a,p+1,hi);
	}
	public static void sort(Comparable[] a) {
	shuffle(a);
	sort(a,0,a.length-1);
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {18,8,16,9,12,5,7,2,4,14,6,1,11,3,10,13,15,19,17,20};
	print(a);
	sort(a);
	print(a);
	Comparable[] a1 = {5,2,4,6,1,3};
	print(a1);
	sort(a1);
	print(a1);
	}
	}

view raw QuickSort.java hosted with ❤ by GitHub

Merge Sort - Coursera Algorithms

Merge sort uses divide and conquer approach to sort the elements. It takes at most NlgN compares and 6NlgN array accesses with total running time of NlgN.

Following is an optimized merge sort - it uses insertion sort for less number of elements. Please see Insertion Sort for the insertion sort algorithm. It also has a method for bottom up merge sort which is not as efficient as the recursive merge sort.

	package sorting.mergeSort;
	import sorting.insertionSort.InsertionSort;
	public class MergeSort {
	static Comparable[] aux;
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static void merge(Comparable[] a,Comparable[] aux, int lo, int mid, int hi) {
	for(int k=lo;k<=hi;k++) {
	aux[k] = a[k];
	}
	int i=lo,j=mid+1;
	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 static void sort(Comparable[] a,Comparable[] aux, int lo, int hi) {
	int cutoff=7;
	if(hi<=lo+ cutoff -1) {
	InsertionSort is = new InsertionSort();
	is.sort(a);
	}
	if(hi<=lo) return;
	int mid = lo + (hi-lo)/2;
	sort(a,aux,lo,mid);
	sort(a,aux,mid+1,hi);
	if(!less(a[mid+1],a[mid]))return;
	merge(a,aux,lo,mid,hi);
	}
	public static void sort(Comparable[] a) {
	aux = new Comparable[a.length];
	sort(a,aux,0,a.length-1);
	}
	public static void bottomUpMS(Comparable[] a) {
	int n = a.length;
	Comparable[] aux = new Comparable[n];
	for(int sz=1; sz<n;sz=2*sz) {
	for(int lo=0;lo<n-sz;lo+=2*sz) {
	merge(a,aux,lo,lo+sz-1,Math.min(lo+2*sz-1,n-1));
	}
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {18,8,16,9,12,5,7,2,4,14,6,1,11,3,10,13,15,19,17,20};
	print(a);
	sort(a);
	print(a);
	Comparable[] a1 = {5,2,4,6,1,3};
	print(a1);
	bottomUpMS(a1);
	print(a1);
	}
	}

view raw MergeSort.java hosted with ❤ by GitHub

Related Posts: 

Insertion Sort

Shell Sort - Coursera Algorithms

Shell sort moves entries by more than one position at a time. It is basically insertion sort with a stride length h - it considers h interleaved sequences and sorts them using insertion sort. When the increment(h) is big, the sub-arrays are smaller and when the increment gets shorter in subsequent iterations, the array is already partially sorted. In both cases, insertion sort works great and hence, it's the best option here.

The optimal value for h is provided by Knuth as 3X+1, but no accurate model has been found for this algorithm yet.

It takes O(N3/2) compares in worst case. It's fast unless array size is large and it has less footprint for code. These make it a perfect choice for hardware sort prototype, linux/kernel, embedded systems etc.

Following is the program:

	package sorting.shellSort;
	public class ShellSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	private static boolean isSorted(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	if(less(a[i],a[i-1]))
	return false;
	}
	return true;
	}
	public 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) {
	exchange(a,j,j-h);
	}
	}
	h = h/3;
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	//Comparable[] a = {5,7,2,4,6,8,1,3,9};
	Comparable[] a = {5,2,4,6,1,3};
	print(a);
	ShellSort insertionSort = new ShellSort();
	insertionSort.sort(a);
	print(a);
	}
	}

view raw ShellSort.java hosted with ❤ by GitHub

Related Posts: 

Insertion Sort

Insertion Sort - Coursera Algorithms

Insertion Sort swaps an element with a larger entry to it's left.

It take ~1/4 N2 compares and ~1/4 N2 exchanges.
Best case(already sorted) : N-1 compares and zero exchanges.
Worst case(reverse sorted):  ~1/2 N2 compares and ~1/2 N2 exchanges.
Partially sorted(when number of inversions <= cN): linear time as number of exchanges equal the number of inversions.

Following is the program, it also uses shuffle to make the order as random as possible. This is done by swapping each element with a random index r such that r is between 0 and iteration i. This takes linear time.

	package sorting.insertionSort;
	public class InsertionSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	private static boolean isSorted(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	if(less(a[i],a[i-1]))
	return false;
	}
	return true;
	}
	public void sort(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	for(int j=i;j>0;j--) {
	if(less(a[j],a[j-1]))
	exchange(a,j,j-1);
	else
	break;
	}
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {5,2,4,6,1,3};
	shuffle(a);
	print(a);
	InsertionSort insertionSort = new InsertionSort();
	insertionSort.sort(a);
	print(a);
	}
	}

view raw InsertionSort.java hosted with ❤ by GitHub

Selection Sort - Coursera Algorithms

Selection sort finds the minimum element and swaps it with the first element, till the complete array is sorted. It takes N²/2 compares and N exchanges.

Following is the program:

	package sorting.selectionSort;
	public class SelectionSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	private static boolean isSorted(Comparable[] a) {
	int n = a.length;
	for(int i=1;i<n;i++) {
	if(less(a[i],a[i-1]))
	return false;
	}
	return true;
	}
	public void sort(Comparable[] a) {
	int n = a.length;
	int min = 0;
	for(int j=0;j<n;j++) {
	min = j;
	for(int i=j+1;i<n;i++) {
	if(less(a[i],a[min])){
	min = i;
	}
	}
	exchange(a,min,j);
	}
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {5,2,4,6,1,3};
	print(a);
	SelectionSort selectionSort = new SelectionSort();
	selectionSort.sort(a);
	print(a);
	}
	}

view raw SelectionSort.java hosted with ❤ by GitHub

Decimal To Binary Conversion Using Stack

Stack can be used to convert a number into it's binary form.

1. Push the remainder into stack after dividing the number by 2.
2. Keep doing 1, till number>0.
3. Pop the binary remainders 1/0 to get the binary form.

 Following is the program:

	package stacks;
	import java.util.Iterator;
	public class BinaryConvStack {
	public String convert(int n) {
	GenericStackResizeArrayItr<Integer> bitStack = new GenericStackResizeArrayItr<Integer>(5);
	StringBuffer sb = new StringBuffer();
	while(n>0) {
	bitStack.push(n%2);
	n=n/2;
	}
	Iterator<Integer> itr = bitStack.iterator();
	while(itr.hasNext()) {
	Integer i = bitStack.pop();
	if(i==null)
	break;
	sb.append(i);
	}
	return sb.toString();
	}
	public static void main(String[] args) {
	BinaryConvStack stack = new BinaryConvStack();
	int i = 50;
	System.out.println(i+" in binary is "+ stack.convert(i));
	i=12345678;
	System.out.println(i+" in binary is "+ stack.convert(i));
	}
	}

view raw BinaryConvStack.java hosted with ❤ by GitHub

 

Arithmetic Expression Evaluation Using Stack

Arithmetic expressions can be evaluated using two stacks - one for operands and other for numeric values.

Algorithm:

1. If element is numeric, push to numeric stack.
2. If element is operand, push to operand stack.
3. If element is "(", ignore. 
4. If element is ")", pop operand from operand stack and pop two numerics from numeric stack - perform the operation and push the result back into numeric stack. 

 Following is the program based on the generic stack implementation using arrays.

	package stacks;
	import java.util.Arrays;
	import java.util.List;
	public class TwoStackDijkstra {
	public int arith(int a, int b, String opr) {
	if(opr.equals("+")) {
	return a+b;
	}else if(opr.equals("-")) {
	return b-a;
	}else if(opr.equals("*")) {
	return a*b;
	}else if(opr.equals("/")) {
	return b/a;
	}else if(opr.equals("%")) {
	return b%a;
	}
	return -1;
	}
	public int evaluate(String arith) {
	String[] operators = {"+","-","*","/","%"};
	List oprList = Arrays.asList(operators);
	GenericStackResizeArrayItr<Integer> valStack = new GenericStackResizeArrayItr<Integer>(5);
	GenericStackResizeArrayItr<String> oprStack = new GenericStackResizeArrayItr<String>(5);
	String[] arithExpr = arith.split("");
	for(String item : arithExpr) {
	if(oprList.contains(item)) {
	oprStack.push(item);
	}else if(item.equals(")")) {
	valStack.push(arith(valStack.pop(), valStack.pop(), oprStack.pop()));
	}else if(item.equals("(")) {
	continue;
	}else {
	valStack.push(Integer.parseInt(item));
	}
	}
	return valStack.pop();
	}
	public static void main(String[] args) {
	TwoStackDijkstra twoStack = new TwoStackDijkstra();
	String s = "((1+2)*(5-3))";
	System.out.println("value of "+ s + " is "+twoStack.evaluate(s));
	s = "(((1+2)*(5-3))/((1+2)*(5-3)))";
	System.out.println("value of "+ s + " is "+twoStack.evaluate(s));
	}
	}

view raw TwoStackDijkstra.java hosted with ❤ by GitHub

Generic Queue Using Resized Array And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a queue from client, we can use Generics and Iterator.

Following is the program:

	package queues;
	import java.util.Iterator;
	public class GenericQueueResizeArrayItr<Item> implements Iterable<Item>{
	public class ArrayIterator implements Iterator<Item>{
	private int i = fwdIndex;
	@Override
	public boolean hasNext() {
	return (i<bckIndex);
	}
	@Override
	public Item next() {
	return queue[i++];
	}
	}
	@Override
	public Iterator<Item> iterator() {
	return new ArrayIterator();
	}
	int fwdIndex=0, bckIndex=0;
	Item[] queue;
	public GenericQueueResizeArrayItr(int cap) {
	queue = (Item[]) new Object[cap];
	}
	public void enqueue(Item s) {
	int l = queue.length;
	if(bckIndex==l) {
	resize(2*l);
	}
	queue[bckIndex++] = s;
	if(isEmpty()) {
	fwdIndex = bckIndex;
	}
	}
	public Item dequeue() {
	if(isEmpty()) {
	System.out.println("empty Q");
	return null;
	}
	int l = queue.length;
	if(bckIndex==l/2) {
	resize(l/4);
	}
	Item s = queue[fwdIndex];
	queue[fwdIndex++] = null;
	return s;
	}
	public int size() {
	return (bckIndex-fwdIndex);
	}
	public boolean isEmpty() {
	return (size()==0);
	}
	public void print() {
	System.out.println("==========================");
	for(int i=fwdIndex;i<bckIndex;i++) {
	System.out.println(queue[i]);
	}
	}
	public void resize(int cap) {
	Item[] copy = (Item[])new Object[cap];
	for(int i=fwdIndex;i<bckIndex;i++) {
	copy[i]=queue[i];
	}
	queue = copy;
	}
	public int length() {
	return queue.length;
	}
	public static void main(String[] args) {
	GenericQueueResizeArrayItr<String> queue = new GenericQueueResizeArrayItr<String>(5);
	queue.enqueue("to");
	queue.enqueue("be");
	queue.enqueue("or");
	queue.enqueue("not");
	queue.enqueue("to");
	queue.print();
	System.out.println("stack util is "+queue.size()+" out of "+queue.length());
	queue.enqueue("be");
	System.out.println("stack util is "+queue.size()+" out of "+queue.length());
	//queue.print();
	System.out.println("-------------Iterator-----------");
	for(String s: queue) {
	System.out.println(s);
	}
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	queue.print();
	//===========Integer===============
	GenericQueueResizeArrayItr<Integer> queueInt = new GenericQueueResizeArrayItr<>(5);
	queueInt.enqueue(1);
	queueInt.enqueue(2);
	queueInt.enqueue(3);
	queueInt.enqueue(4);
	queueInt.enqueue(5);
	queueInt.enqueue(6);
	//queueInt.print();
	System.out.println("-------------Iterator-----------");
	for(Integer i: queueInt) {
	System.out.println(i);
	}
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	queueInt.print();
	}
	}

view raw GenericQueueResizeArrayItr.java hosted with ❤ by GitHub

Generic Queue Using Linked List And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a queue from client, we can use Generics and Iterator.

Following is the program:

	package queues;
	import java.util.Iterator;
	public class GenericQueueLLItr<Item> implements Iterable<Item> {
	Node first;
	Node last;
	static int size;
	public class Node{
	Item value;
	Node next;
	public Node(Item s) {
	this.value = s;
	}
	}
	public class ListIterator implements Iterator<Item>{
	private Node current = first;
	@Override
	public boolean hasNext() {
	return (current!=null);
	}
	@Override
	public Item next() {
	Item val = current.value;
	current = current.next;
	return val;
	}
	}
	@Override
	public Iterator<Item> iterator() {
	return new ListIterator();
	}
	public void enqueue(Item s) {
	Node prevLast = last;
	last = new Node(s);
	if(!isEmpty())
	prevLast.next = last;
	else {
	first = last;
	}
	size++;
	}
	public Item dequeue() {
	if(isEmpty()) {
	System.out.println("queue empty");
	return null;
	}
	Item s = first.value;
	first = first.next;
	size--;
	return s;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public int size() {
	return size;
	}
	public void print() {
	System.out.println("==========================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	//===========String===============
	GenericQueueLLItr<String> queue = new GenericQueueLLItr<String>();
	queue.enqueue("to");
	queue.enqueue("be");
	queue.enqueue("or");
	queue.enqueue("not");
	queue.enqueue("to");
	queue.enqueue("be");
	//queue.print();
	System.out.println("-------------Iterator-----------");
	for(String s: queue) {
	System.out.println(s);
	}
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	queue.print();
	//===========Integer===============
	GenericQueueLLItr<Integer> queueInt = new GenericQueueLLItr<>();
	queueInt.enqueue(1);
	queueInt.enqueue(2);
	queueInt.enqueue(3);
	queueInt.enqueue(4);
	queueInt.enqueue(5);
	queueInt.enqueue(6);
	//queueInt.print();
	System.out.println("-------------Iterator-----------");
	for(Integer i: queueInt) {
	System.out.println(i);
	}
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	System.out.println("DQd "+queueInt.dequeue());
	queueInt.print();
	}
	}

view raw GenericQueueLLItr.java hosted with ❤ by GitHub

Generic Stack Using Resized Array And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a stack from client, we can use Generics and Iterator.

Following is the program:

	package stacks;
	import java.util.Iterator;
	public class GenericStackResizeArrayItr<Item> implements Iterable<Item>{
	Item[] stack;
	int index=0;
	public GenericStackResizeArrayItr(int cap) {
	stack = (Item[])new Object[cap];
	}
	public class ArrayIterator implements Iterator<Item>{
	private int i=index;
	@Override
	public boolean hasNext() {
	return (i>0);
	}
	@Override
	public Item next() {
	return stack[--i];
	}
	}
	@Override
	public Iterator<Item> iterator() {
	// TODO Auto-generated method stub
	return new ArrayIterator();
	}
	public void push(Item s) {
	int l = stack.length;
	if(index==l) {//full array-double size
	resize(2*l);
	}
	stack[index++] = s;
	}
	public int size() {
	return index;
	}
	public int length() {
	return stack.length;
	}
	public boolean isEmpty() {
	return (index==0);
	}
	public Item pop() {
	if(isEmpty()) {
	System.out.println("stack empty");
	return null;
	}
	int l = stack.length;
	if(index<=l/4) {//25% of array is filled-half the array
	resize(l/2);
	}
	Item s = stack[--index];
	stack[index] = null;
	return s;
	}
	public void print() {
	System.out.println("============================");
	for(int i=0;i<index;i++) {
	System.out.println(stack[i]);
	}
	}
	public void resize(int cap) {
	Item copy[] = (Item[])new Object[cap];
	for(int i=0;i<index;i++) {
	copy[i]=stack[i];
	}
	stack = copy;
	}
	public static void main(String[] args) {
	GenericStackResizeArrayItr<String> stack = new GenericStackResizeArrayItr<String>(5);
	stack.push("to");
	stack.push("be");
	stack.push("or");
	stack.push("not");
	stack.push("to");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.push("be");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	//stack.print();
	System.out.println("-------------Iterator-----------");
	for(String s: stack) {
	System.out.println(s);
	}
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	//Integer
	GenericStackResizeArrayItr<Integer> stack1 = new GenericStackResizeArrayItr<Integer>(5);
	stack1.push(1);
	stack1.push(2);
	stack1.push(3);
	stack1.push(4);
	stack1.push(5);
	System.out.println("stack util is "+stack1.size()+" out of "+stack1.length());
	stack1.push(6);
	System.out.println("stack util is "+stack1.size()+" out of "+stack1.length());
	//stack1.print();
	System.out.println("-------------Iterator-----------");
	for(Integer s: stack1) {
	System.out.println(s);
	}
	stack1.pop();
	stack1.pop();
	stack1.print();
	System.out.println("stack util is "+stack1.size()+" out of "+stack1.length());
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.print();
	System.out.println("stack util is "+stack1.size()+" out of "+stack1.length());
	}
	}

view raw GenericStackResizeArrayItr.java hosted with ❤ by GitHub

Generic Stack Using Linked List And Iterator - Coursera Algorithms

To make the stack generic and to hide the internal representation of a stack from client, we can use Generics and Iterator.

Following is the program:

	package stacks;
	import java.util.Iterator;
	public class GenericStackLLIterator<Item> implements Iterable<Item> {
	private Node first = null;
	static int size = 0;
	public class Node{
	Item value;
	Node next;
	}
	@Override
	public Iterator<Item> iterator() {
	// TODO Auto-generated method stub
	return new ListIterator();
	}
	public class ListIterator implements Iterator<Item>{
	private Node current = first;
	@Override
	public boolean hasNext() {
	return (current!=null);
	}
	@Override
	public Item next() {
	Item val= current.value;
	current = current.next;
	return val;
	}
	}
	public void push(Item val) {//insert at the beginning of the LL
	Node n1 = new Node();
	n1.value = val;
	n1.next = first;
	first = n1;
	size++;
	}
	public Item pop() {//pop the first ele - LIFO
	if(isEmpty()) {
	System.out.println("stack empty");
	return null;
	}
	Item val = first.value;
	first = first.next;
	size--;
	return val;
	}
	public int size() {
	return size;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public void print() {
	System.out.println("============================================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	GenericStackLLIterator<Integer> stack = new GenericStackLLIterator<Integer>();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	stack.push(5);
	//stack.print();
	System.out.println("-------------Iterator-----------");
	for(Integer i: stack) {
	System.out.println(i);
	}
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("size is "+stack.size());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	//String
	GenericStackLLIterator<String> stack1 = new GenericStackLLIterator<String>();
	stack1.push("to");
	stack1.push("be");
	stack1.push("or");
	stack1.push("not");
	stack1.push("to");
	stack1.push("be");
	//stack1.print();
	System.out.println("-------------Iterator-----------");
	for(String s: stack1) {
	System.out.println(s);
	}
	stack1.pop();
	stack1.pop();
	stack1.print();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.pop();
	stack1.print();
	}
	}

view raw GenericStackLLIterator.java hosted with ❤ by GitHub

Queue Using Array Resizing - Coursera Algorithms

Queues follow FIFO standard. To implement, we need to maintain two indices to first and last elements of the array, for enqueue and dequeue operations.

Following is the program:

	package queues;
	public class QueueResizeArray {
	int fwdIndex=0, bckIndex=0;
	String[] queue;
	public QueueResizeArray(int cap) {
	queue = new String[cap];
	}
	public void enqueue(String s) {
	int l = queue.length;
	if(bckIndex==l) {
	resize(2*l);
	}
	queue[bckIndex++] = s;
	if(isEmpty()) {
	fwdIndex = bckIndex;
	}
	}
	public String dequeue() {
	if(isEmpty()) {
	System.out.println("empty Q");
	return "";
	}
	int l = queue.length;
	if(bckIndex==l/2) {
	resize(l/4);
	}
	String s = queue[fwdIndex];
	queue[fwdIndex++] = null;
	return s;
	}
	public int size() {
	return (bckIndex-fwdIndex);
	}
	public boolean isEmpty() {
	return (size()==0);
	}
	public void print() {
	System.out.println("==========================");
	for(int i=fwdIndex;i<bckIndex;i++) {
	System.out.println(queue[i]);
	}
	}
	public void resize(int cap) {
	String[] copy = new String[cap];
	for(int i=fwdIndex;i<bckIndex;i++) {
	copy[i]=queue[i];
	}
	queue = copy;
	}
	public int length() {
	return queue.length;
	}
	public static void main(String[] args) {
	QueueResizeArray queue = new QueueResizeArray(5);
	queue.enqueue("to");
	queue.enqueue("be");
	queue.enqueue("or");
	queue.enqueue("not");
	queue.enqueue("to");
	queue.print();
	System.out.println("stack util is "+queue.size()+" out of "+queue.length());
	queue.enqueue("be");
	System.out.println("stack util is "+queue.size()+" out of "+queue.length());
	queue.print();
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	queue.print();
	}
	}

view raw QueueResizeArray.java hosted with ❤ by GitHub

Related Posts: 

Queue Using Linked List - Coursera Algorithms

Queue Using Linked List - Coursera Algorithms

Queues follow FIFO standard. To implement, we need to maintain two pointers to first and last nodes of linked list, as we insert at the end of the list and removed the first element of the list for enqueue and dequeue operations.

Following is the program:

	package queues;
	public class QueueLL {
	Node first;
	Node last;
	static int size;
	public class Node{
	String value;
	Node next;
	public Node(String s) {
	this.value = s;
	}
	}
	public void enqueue(String s) {
	Node prevLast = last;
	last = new Node(s);
	if(!isEmpty())
	prevLast.next = last;
	else {
	first = last;
	}
	size++;
	}
	public String dequeue() {
	if(isEmpty()) {
	System.out.println("queue empty");
	return "";
	}
	String s = first.value;
	first = first.next;
	size--;
	return s;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public int size() {
	return size;
	}
	public void print() {
	System.out.println("==========================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	QueueLL queue = new QueueLL();
	queue.enqueue("to");
	queue.enqueue("be");
	queue.enqueue("or");
	queue.enqueue("not");
	queue.enqueue("to");
	queue.enqueue("be");
	queue.print();
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	System.out.println("DQd "+queue.dequeue());
	queue.print();
	}
	}

view raw QueueLL.java hosted with ❤ by GitHub

Stack Using Array Resizing - Coursera Algorithms

When implementing stacks using arrays, we may run into overflow and underflow problems. We can resize the array on need basis by doubling the array in push op when the array has reached it's limit and by halving the array in pop op when the array is just 25% utilized. 

This will result in constant amortized time operations, but ~N in worst case.

Linked list on the other hand has constant time even in worst case. But still, linked list may take more time and memory because of the links. 

If occasional slow ops are bearable, then arrays would be a better option than linked lists. 

Following is the complete program:

	package stacks;
	public class StackResizeArray {
	String[] stack;
	int index=0;
	public StackResizeArray(int cap) {
	stack = new String[cap];
	}
	public void push(String s) {
	int l = stack.length;
	if(index==l) {//full array-double size
	resize(2*l);
	}
	stack[index++] = s;
	}
	public int size() {
	return index;
	}
	public int length() {
	return stack.length;
	}
	public boolean isEmpty() {
	return (index==0);
	}
	public String pop() {
	if(isEmpty()) {
	System.out.println("stack empty");
	return "";
	}
	int l = stack.length;
	if(index<=l/4) {//25% of array is filled-half the array
	resize(l/2);
	}
	String s = stack[--index];
	stack[index] = null;
	return s;
	}
	public void print() {
	System.out.println("============================");
	for(int i=0;i<index;i++) {
	System.out.println(stack[i]);
	}
	}
	public void resize(int cap) {
	String copy[] = new String[cap];
	for(int i=0;i<index;i++) {
	copy[i]=stack[i];
	}
	stack = copy;
	}
	public static void main(String[] args) {
	StackResizeArray stack = new StackResizeArray(5);
	stack.push("to");
	stack.push("be");
	stack.push("or");
	stack.push("not");
	stack.push("to");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.push("be");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.print();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	}
	}

view raw StackResizeArray.java hosted with ❤ by GitHub

Related Posts:  

Stack Using Linked List - Coursera Algorithms

Stack Using Array - Coursera Algorithms

Stack Using Array - Coursera Algorithms

Stack works in a LIFO order. It supports insert, remove, iteration and test for empty operations.

They can be represented using array. An initial capacity for this array is taken as input. We manipulate an index variable for push and pop, instead of actually deleting items from stack.

If using objects in stack, avoid loitering(holding references to objects and preventing GC) by using following code in pop operation:

public String pop() { String item = s[--N]; s[N] = null; return item; } 

Following is the complete program:

	package stacks;
	import stacks.StackLL.Node;
	public class StackA {
	int[] stack;
	int index=0;
	public StackA(int cap) {
	stack = new int[cap];
	}
	public void push(int v) {
	stack[index++] = v;
	}
	public int pop() {
	if(isEmpty()) {
	System.out.println("stack empty");
	return Integer.MIN_VALUE;
	}
	return stack[--index];
	}
	public boolean isEmpty() {
	return (index==0);
	}
	public int size() {
	return index;
	}
	public void print() {
	System.out.println("============================================");
	for(int j=index-1;j>=0;j--) {
	System.out.println(stack[j]);
	}
	}
	public static void main(String[] args) {
	StackA stack = new StackA(10);
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	stack.push(5);
	stack.print();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("size is "+stack.size());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	}
	}

view raw StackA.java hosted with ❤ by GitHub

Related Posts:  

Stack Using Linked List - Coursera Algorithms

Stack Using Linked List - Coursera Algorithms

Stack works in a LIFO order. It supports insert, remove, iteration and test for empty operations.

They can be represented using linked list. Push and pop operations are done on the first element. This takes constant time for any operation and about ~36N Bytes for N stack items - 16B overhead + 8B inner Node class + 8B reference to Node object + 4B for integer values.

Following is the program:

	package stacks;
	public class StackLL {
	private Node first = null;
	static int size = 0;
	public class Node{
	int value;
	Node next;
	}
	public void push(int val) {//insert at the beginning of the LL
	Node n1 = new Node();
	n1.value = val;
	n1.next = first;
	first = n1;
	size++;
	}
	public int pop() {//pop the first ele - LIFO
	if(isEmpty()) {
	System.out.println("stack empty");
	return Integer.MIN_VALUE;
	}
	int val = first.value;
	first = first.next;
	size--;
	return val;
	}
	public int size() {
	return size;
	}
	public boolean isEmpty() {
	return (first==null);
	}
	public void print() {
	System.out.println("============================================");
	Node n = first;
	while(n!=null) {
	System.out.println(n.value);
	n = n.next;
	}
	}
	public static void main(String[] args) {
	StackLL stack = new StackLL();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	stack.push(5);
	stack.print();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("size is "+stack.size());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	}
	}

view raw StackLL.java hosted with ❤ by GitHub