class Elem {
	int valore;
	Elem next;
}

class Pila {
	Elem top;
	int size;
}

class Coda {
	Elem first;
	Elem last;
	int size;
}



public class MainClass {

	public static Elem aggiungiInTesta (Elem lista, Elem e){
		if (e==null) return lista;
		e.next=lista;
		return e;		
	}
	
	public static int size (Elem lista){
		if (lista==null) return 0;
		return 1+size(lista.next);
	}
	
	public static Elem search (Elem lista, int valore){
		Elem i = lista;
		while (i!=null){
			if (i.valore==valore) {return i;}
			i=i.next;
		}
		return null;
	}
	
	public static Elem searchRec (Elem lista, int valore){
		if (lista==null) return null;
		if (lista.valore==valore) return lista;
		return searchRec (lista.next, valore);
	}
	
	public static Elem delete (Elem lista, Elem e){
		if (lista==null) return null;
		if (e==null) return lista;
		if (lista==e) {
			Elem secondo=lista.next;
			lista.next=null;
			return secondo;
		}
		Elem corrente=lista;
		Elem precedente=null;
		while (corrente!=null && corrente!=e){
			precedente=corrente;
			corrente=corrente.next;
		}
		if (corrente==null) return lista;
		precedente.next=corrente.next;
		return lista;		
	}
	
	//aggiunge e dopo l'elemento rif della lista lista
	public static Elem aggiungiInMezzo (Elem lista, Elem e, Elem rif){
		if (e==null) return lista;
		if (lista==null || rif==null) return null;
		Elem i =lista;
		while (i!=null){
			if (i==rif) {
				e.next=rif.next;
				rif.next=e;
				return lista;
			}
			i=i.next;
		}
		return lista;
	}
	
	public static Elem creaElem (int valore) {
		Elem e = new Elem();
		e.valore=valore;
		e.next = null;
		return e;
	}
	
	public static Pila creaPila (){
		Pila p = new Pila();
		p.top=null;
		p.size = 0;
		return p;
	}
	
	public static Coda creaCoda (){
		Coda c = new Coda();
		c.first=null;
		c.last=null;
		c.size = 0;
		return c;
	}
	
	public static boolean isEmpty (Coda c){
		if (c==null) return true;
		return c.first==null;
	}
	
	public static int size (Coda c){
		return c.size;
	}		
	
	
	public static void enqueue (Coda c, Elem e){
		if (c==null || e==null) return;
		if (isEmpty(c)){
			c.first=e;
			c.last=e;
			e.next=null;
		} else {
			c.last.next=e;
			c.last=e;
			e.next=null;
		}
		c.size++;
	}
	
	public static Elem dequeue (Coda c){
		if (c==null || isEmpty(c)) return null;
		c.size--;
		Elem e = c.first;
		c.first=e.next;
		e.next=null;
		if (c.first==null) c.last=null;
		return e;		
	}
	public static boolean isEmpty (Pila p){
		if (p==null) return true;
		return p.top==null;
	}
	
	public static void push (Pila p, Elem e){
		if (p==null || e==null) return;
		e.next=p.top;
		p.top=e;
		p.size++;
	}
	
	public static Elem pop (Pila p){
		if (p==null || p.top==null) return null;
		Elem e = p.top;
		p.top = e.next;
		e.next=null;
		p.size--;
		return e;
	}
	
	public static int size (Pila p){
		return p.size;
	}
	
	public static void stampaCoda (Coda c){
		if (c==null) return;
		System.out.print ("{");
		boolean first = true;
		Elem i = c.first;
		while (i!=null){
			if (first) {
				first = false;
			} else {
				System.out.print (" -> ");
			}
			System.out.print (i.valore);
			i=i.next;
		}
		System.out.println ("}");
	}
	
	public static void stampaPila (Pila p){
		if (p==null) return;
		System.out.print ("{");
		boolean first = true;
		Elem i = p.top;
		while (i!=null){
			if (first) {
				first = false;
			} else {
				System.out.print (" -> ");
			}
			System.out.print (i.valore);
			i=i.next;
		}
		System.out.println ("}");
	}
	
	
	public static void testPila(){
		Pila p = creaPila();
		Elem e1= creaElem(1);
		Elem e2= creaElem(5);
		Elem e3= creaElem(12);
		push(p,e1);
		push(p,e2);
		stampaPila(p);
		pop (p);
		stampaPila(p);
		push (p,e3);
		stampaPila(p);		
		pop (p);
		pop (p);
		stampaPila(p);	
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		testPila();

	}

}