This part we will talk about some classic date structure and algorithm.
First, we all know binary search:
/**
* Return the index of the array whose a[index] is equal to key
* Return -1 if not found
* @param key
* @param a
* @return
*/
public static int rank(int key,int[] a){
int lo=0;
int hi=a.length-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(key<a[mid]) hi=mid-1;
else if(key>a[mid]) lo=mid+1;
else return mid;
}
return -1;
}
Here we take the array as int. The time complexity is O(logn).
Second, as it happens, it was a question asked by an interviewer. How to make the array random. Actually he asked not like this, he gave me a group people with their own gifts. All they want exchange gift with each other, please find a way to make the progress as random as possible. On the other hand, after exchanging, no one get his own gift.
public static void shuffle(int[] a){
int N=a.length;
for(int i=0;i<N-1;i++){
//Exchange a[i] with the random element in a[i+1...N-1]
int r=i+1+(int)((N-i-1)*Math.random());
int temp=a[i];
a[i]=a[r];
a[r]=temp;
}
}
I call it as shuffle, the main idea is exchange a[i] with the a[i+1...].
Attention! if
int r=i+(int)((N-i)*Math.random());
we can also shuffle, but maybe some can get his own gift as
(int)((N-i)*Math.random())==0
Third, how a simple stack data structure be constructed? Here is a stack with fixed size:
import java.util.Iterator;
//What the difference of Iterable and Iterator
public class FixedCapacityStackOfStrings implements Iterable<String> {
private String[] a;//stack entries
private int N=0;//size
//Initialize
public FixedCapacityStackOfStrings(int capSize){
a = new String[capSize];
}
public boolean isEmpty(){
return N==0;
}
public int size(){
return N;
}
//what if N>=a.length?
public void push(String item){
a[N++]=item;
}
public String pop(){
return a[--N];
}
public String toString(){
String s="";
for(String e:a){
s+=e+" ";
}
return s;
}
//Iterator
@Override
public Iterator<String> iterator() {
return new HelpIterator();
}
private class HelpIterator implements Iterator<String>{
private int i=N;
public boolean hasNext(){return i>0;}
public String next(){return a[--i];}
public void remove(){ }
}
/**
* Test unit
* @param args
*/
public static void main(String[] args) {
FixedCapacityStackOfStrings test=new FixedCapacityStackOfStrings(5);
test.push("hello");
test.push("you");
test.push("panic");
System.out.println("first");
for(String e:test)
System.out.println(e);
test.pop();
System.out.println("second:");
for(String e:test)
System.out.println(e);
}
}
The main operations are pop, push and the iterator. You can test it with your own test case. After overflow it'll break.
Fourth, how to construct a stack which can adjust size as the change of the number of element:
import java.util.Iterator;
public class ResizingArrayStack<Item> implements Iterable<Item> {
private Item[] a = (Item[]) new Object[1];//Stack item
private int N=0;//Number of stack
public boolean isEmpty(){ return N==0;}
public int size(){return N;}
//See the Item[] size
public int ItemSize(){return a.length;}
private void resize(int max){
//Move stack to a new array of size max
Item[] temp= (Item[]) new Object[max];
//Copy
for(int i=0;i<N;i++)
temp[i]=a[i];
a=temp;
}
public void push(Item item){
//Add item to the top of stack
if(N==a.length) resize(2*a.length);
a[N++]=item;
}
public Item pop(){
//Remove the top of the stack
Item item=a[N--];
a[N]=null;//??
if(N>0 && N==a.length/4) resize(a.length/2);
return item;
}
public String toString(){
String s="";
for(Item e:a){
s+=e+" ";
}
return s;
}
//Iterator methods
@Override
public Iterator<Item> iterator() {
return new helpIterator();
}
public class helpIterator implements Iterator<Item>{
//Support the LILO iteraion
private int i=N;
public boolean hasNext(){return i>0; }
public Item next() {return a[--i];}
public void remove() { }
}
/**
* Test unit
* @param args
*/
public static void main(String[] args) {
ResizingArrayStack<Integer> test=new ResizingArrayStack<>();
//Push
for(int i=0;i<15;i++){
test.push(i);
System.out.println(test);
System.out.println(test.ItemSize());
}
//Pop
while(!test.isEmpty()){
test.pop();
System.out.println(test);
System.out.println(test.ItemSize());
}
}
}
The main idea is resize, new an array and copy the date from old to new. The same idea occur in many places.
Fifth, we can see that the above way to construct stack is based on array, so what if with Linked-list?
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item> {
//The stack is based on Linked-list
private class Node{
Item item;
Node next;
}
private Node top;
private int N;//The number of the elements
public boolean isEmpty(){
return top==null;//or return N==0
}
public int size(){
return N;
}
public void push(Item item){
//Add the item to the top of stack
Node oldTop=top;
top=new Node();
top.item=item;
top.next=oldTop;
N++;
}
public Item pop(){
//Remove item from the top of stack
Node oldTop=top;
Item item=top.item;
top=top.next;
N--;
oldTop=null;//Let GC to do
return item;
}
public String toString(){
String s="";
Node temp=top;
while(temp!=null){
s+=temp.item+" ";
temp=temp.next;
}
return s;
}
//Iterator
@Override
public Iterator<Item> iterator() {
return new helpIterator();
}
public class helpIterator implements Iterator<Item>{
private Node curr=top;
public boolean hasNext(){return curr!=null;}
public Item next(){
Item item=curr.item;
curr=curr.next;
return item;
}
}
/**
* Test unit
* @param args
*/
public static void main(String[] args) {
Stack<Integer> test=new Stack<>();
for(int i=0;i<10;i++){
test.push(i);
}
System.out.println(test);
while(!test.isEmpty())
test.pop();
System.out.println(test);
}
}
As you can see, the structure set the top node as the top of stack. If push, we set the new node of the top, and make its next is oldTop. If pop, we just make top equal to top.next, and set the oldTop as null and make the GC to deal with it.
Sixth, let's see the queue based on Linked-list.
import java.util.Iterator;
public class Queue<Item> implements Iterable<Item>{
private class Node{
Item item;
Node next;
}
private Node first;//The head of the queue
private Node last; //The tail of the queue
private int N; //The number of the item of the queue
public boolean isEmpty(){return N==0;}//or first==null
public int size(){return N;}
public void enqueue(Item item){
//Add the item to the tail of the list
Node oldLast=last;
last = new Node();
last.item=item;
last.next=null;
if(first==null) first=last;
else oldLast.next=last;
N++;
}
public Item dequeue(){
//Remove the item form the head of the list
Item item=first.item;
first=first.next;
if(isEmpty()) last=null;
N--;
return item;
}
public String toString(){
String s="";
Node temp=first;
while(temp!=null){
s+=temp.item+" ";
temp=temp.next;
}
return s;
}
//Iterator
@Override
public Iterator<Item> iterator() {
return new helpIterator();
}
private class helpIterator implements Iterator<Item>{
Node curr=first;
public boolean hasNext(){
return curr!=null;
}
public Item next(){
Item item=curr.item;
curr=curr.next;
return item;
}
public void remove(){
}
}
/**
* Test unit
* @param args
*/
public static void main(String[] args) {
Queue<Integer> test = new Queue<>();
for(int i=0;i<10;i++)
test.enqueue(i);
System.out.println(test);
test.dequeue();
System.out.println(test);
for(Integer e:test){
System.out.println(e);
}
}
}
As the other article I wrote, of the operation of Linked-list, we must care about whether it is null. The stack we don't need care for the problem, but in queue, we must. Because we need to maintain two pointers, one is head, other is tail. The detail you can read the enqueue and dequeue.
