Implementing Least recently used (LRU) cache in Java

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Created by gpzpati on 3/3/14.
 */
public class LRUCache {

    private final int maxSize;
    private ConcurrentHashMap map;
    private ConcurrentLinkedQueue queue;

    public LRUCache(final int maxSize) {
        this.maxSize = maxSize;
        map = new ConcurrentHashMap(maxSize);
        queue = new ConcurrentLinkedQueue();
    }

    /**
     * @param key - may not be null!
     * @param value - may not be null!
     */
    public void put(final Key key, final Value value) {
        if (map.containsKey(key)) {
            queue.remove(key); // remove the key from the FIFO queue
        }

        while (queue.size() >= maxSize) {
            Key oldestKey = queue.poll();
            if (null != oldestKey) {
                map.remove(oldestKey);
            }
        }
        queue.add(key);
        map.put(key, value);
    }

    /**
     * @param key - may not be null!
     * @return the value associated to the given key or null
     */
    public Value get(final Key key) {
        return map.get(key);
    }

    public static void main(String[] argv){
        LRUCache lruCache = new LRUCache(3);
        lruCache.put("Sunil","36");
        lruCache.put("Leena","31");
        lruCache.put("Jiya","7");
        System.out.println(lruCache.get("Sunil"));
        lruCache.put("Navya","2");
        System.out.println(lruCache.get("Sunil"));

    }
}

What is difference between HashMap, TreeMap and LinkedHashMap ?

Difference is in how the elements are ordered

1. HashMap : Does not guarantee order, the order depends on how the elements get hashed and which bucket they land in
2. TreeMap : TreeMap will order elements in the natural order, it will maintain Map in sorted order
3. LinkedHashMap: Maintains elements in order of insertion

Take a look at this small program that inserts same elements in different Map objects and then prints them in order

package com.test;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class TestMap {

 public static void main(String[] args) {
  System.out.println("*****HashMap******* ");
  printMap(new HashMap(5));
  
  System.out.println("*****TreeMap******* ");
  printMap(new TreeMap());
  System.out.println("*****LinkedHashMap******* ");
  printMap(new LinkedHashMap());

 }
 private static void printMap(Map map){
  map.put(32, "Three");
  map.put(11, "One");
  map.put(25, "Two");
  map.put(53, "Five");
  map.put(44, "Four");
  for(Map.Entry entry: map.entrySet())
   System.out.println(entry);
 }
}

This is the output

*****HashMap******* 
25=Two
32=Three
11=One
44=Four
53=Five
*****TreeMap******* 
11=One
25=Two
32=Three
44=Four
53=Five
*****LinkedHashMap******* 
32=Three
11=One
25=Two
53=Five
44=Four

MinStack

I was asked a question about how would i implement a Stack without using Linked List structure that supports push, pop and getMin operation, so this is the solution. Basic idea is you maintain Node object which has value of the node and the minimum value at that point. Every time push() is called you have to see if the value being pushed is smaller than current minimum if yes it becomes new minimum and you push it on stack with current value, if not you take current minimum and push it on stack with value being pushed. Problem with this solution is it will take twice the memory

public class MinStackArray {

 private class Node{
  private int value;
  private int minValue;
 }
 
 Node[] array;
 int N;
 
 public MinStackArray(int capacity){
  array = new Node[capacity];
  N = 0;
 }
 
 public void push(int value){
  if(N >= array.length )
   resize();
  Node newNode = new Node();
  newNode.value = value;
  
  if(N == 0){
   newNode.minValue = value;
  }else{
   Node headNode = array[N-1];
   if(headNode.minValue < value)
    newNode.minValue = headNode.minValue;
   else
    newNode.minValue = value;
  }
  array[N++] = newNode;
 }
 
 public int pop(){
  if(N == 0)
   return -1;
  Node head = array[--N];
  return head.value;
 }
 
 public int getMin(){
  if(N == 0)
   return -1;
  Node head = array[N-1];
  return head.minValue;
 }
 
 private void resize(){
  Node[] newArray = new Node[array.length*2];
  int counter  =0;
  for(Node c :array){
   newArray[counter++] =c;
  }
  array = newArray;
 }
 
 public static void main(String[] argv){
  MinStackArray msa = new MinStackArray(2);
  msa.push(5);
  msa.push(7);
  msa.push(3);
  msa.push(9);
  msa.push(1);

  System.out.println(msa.getMin());
  msa.pop();
  System.out.println(msa.getMin());
  msa.pop();
  System.out.println(msa.getMin());
  msa.pop();
  System.out.println(msa.getMin());
  msa.pop();
  System.out.println(msa.getMin());
  msa.pop();
  System.out.println(msa.getMin());
  msa.pop();
  System.out.println(msa.getMin());
  msa.pop();
  System.out.println(msa.getMin());
 }
}