A 2 level priority queue (Normal and VIP priority), like in night clubs. Any VIP element will be queued with other VIP element, and will be picked up in priority

VipQueue.java

import java.util.Random;
import java.util.concurrent.Semaphore;

/**
 * A 2 level priority queue (Normal and VIP priority).
 * Any VIP element will be queued with other VIP element, and will
 * be available in priority. Picking an element can be blocking if needed.
 * @author Pierre-Henri Symoneaux
 *
 * @param <E> Type of the objects to store
 */
public class VipQueue<E> {
	
	/** Head of the fifo **/
	private Node head = null;
	
	/** Tail of VIP fifo if any vip is in it **/
	private Node vipTail = null;
	
	/** Tail of the fifo **/
	private Node tail = null;
	
	/** Maximum capacity **/
	private int maxCapa;
	
	/** Number of elements in the fifo **/
	private int size = 0;
	
	/** Semaphore for blocking access when the fifo is empty **/
	private Semaphore sem;
	
	/**
	 * Construct a queue with maximum capacity {@link Integer#MAX_VALUE}
	 * @param fair 	When picking an element in blocking mode, treat
	 * 				waiting thread in a fair manner
	 */
	public VipQueue(boolean fair) {
		this(Integer.MAX_VALUE, fair);
	}

	/**
	 * Constructor with max capacity
	 * @param capacity 	Maximum queue capacity
	 * @param fair		When picking an element in blocking mode, treat
	 * 					waiting thread in a fair manner
	 */
	public VipQueue(int capacity, boolean fair){
		this.maxCapa = capacity;
		sem = new Semaphore(0, fair);
	}
	
	/**
	 * Insert an element in the queue. No capacity limitation is applied to VIPs
	 * @param obj Object to insert
	 * @param vip Treat the object as a VIP
	 * @return 	<code>true</code> if the element has been inserted,
	 * 			<code>false</code> if the maximum capacity has been reached
	 */
	public boolean offer(E obj, boolean vip){
		if(obj == null)
			throw new NullPointerException();
		Node n = new Node(obj);
		synchronized(this) {
			if(!vip) { // Put at the tail
				if(size >= maxCapa)
					return false;
				n.prev = tail;
				if(tail != null)
					tail.next = n;
				if (head == null)
					head = n;
				tail = n;
			}
			else {
				if(vipTail != null) {
					//Insert node at vipTail's place
					//If vipTail is not null, the queue is not empty
					n.prev = vipTail;
					n.next = vipTail.next;
					if(vipTail.next != null)
						vipTail.next.prev = n;
					vipTail.next = n;
					if(vipTail == tail) // if vip is the last
						tail = n;
					vipTail = n;
				}
				else { //No vip in the queue
					//Create vipTail and put it at the head
					n.next = head;
					if(head != null)
						head.prev = n;
					else // There's nothing in the queue
						tail = n;
					head = n;
					vipTail = n;
				}
			}
			size ++;
		}
		sem.release();
		return true;
		
	}
	
	/**
	 * Take and remove the head element from the queue
	 * @param wait	If no element is available, wait until one is inserted
	 * @return		The head element
	 * @throws InterruptedException
	 */
	public E poll(boolean wait) throws InterruptedException {
		if(wait)
			sem.acquire();
		else {
			if(!sem.tryAcquire())
				return null;
		}
		Node e;
		synchronized(this) {
			e = head;
			if(head == vipTail) // Last vip in queue
				vipTail = null;
			if(head == tail) // last element in queue 
				tail = null;
			head = head.next;
			if(head != null)
				head.prev = null;
			size --;
		}
		return e.obj;
	}
	
	/**
	 * @return The number of element in the queue
	 */
	public int size() {
		return size;
	}
	
	/**
	 * A node element for the queue
	 * @author Pierre-Henri Symoneaux
	 *
	 */
	protected class Node {
		
		/** Next node in the queue **/
		protected Node next = null;
		
		/** Previous node in the queue **/
		protected Node prev = null;
		
		/** Stored object **/
		protected E obj = null;
		
		/**
		 * 
		 */
		public Node(E obj){
			this(obj, null, null);
		}
		
		/**
		 * 
		 */
		public Node(E obj, Node next, Node prev){
			this.obj = obj;
			this.next = next;
			this.prev = prev;
		}
	}
}