[JAVA] - Pile e code

[tigerjack89]

Salve ragazzi!!!
Sto cercando di creare due classi che simulino il funzionamento di code e liste. Sono classi semplici, non parametriche, che usano soltanto un array di tipo Object. La sfida è proprio in questo .
Eccole qui. Vi chiedo: voi come le migliorereste? Partendo dal presupposto che non voglio usare ArrayList ma solo array veri e propri di tipo Object[].

/**
 * A class equals to Stack class of java, but this is not a parametric class;
 * indeed, it uses an Object[] array.
 * Methods, otherwise, are the same and with the same functionalities.
 * 
 * @author Simone
 *
 */
public class MyArrayStack
{
	public MyArrayStack(int aSize)
	{
		arraySize = aSize;
		object = new Object[arraySize];
		position = - 1;
	}
	
	public void push(Object element)
	{
		isFull();
		
		object[++position] = element;
	}
	
	public Object pop()
	{
		if (isEmpty())
			throw new IllegalStateException();
		return object[position--];
	}
	
	public Object peek()
	{
		if (isEmpty())
			throw new IllegalStateException();
		return object[position];
	}
	
	public boolean isEmpty()
	{
		return position < 0;
	}
	
	private void isFull()
	{
		if (position >= arraySize - 1)
		{
			Object[] newObject = new Object[object.length * 2];
			System.arraycopy(object, 0, newObject, 0, object.length);
			object = newObject;
		}	
	}
	
	private Object[] object;	
	private int arraySize;
	private int position;
}

import java.util.NoSuchElementException;

/**
 * A class to simulate a circular queue
 * @author Simone
 *
 */
public class MyCircularArrayQueue
{
	public MyCircularArrayQueue(int capacity)
	{
		theSize = capacity;
		elements = new Object[theSize];
		head = -1;
		tail = -1;
	}
	
	/**
	 * Add an object at the end of queue
	 * @param element
	 */
	public void add(Object element)
	{
		isFull();
		
		elements[++tail] = element;
	}
	
	/**
	 * Remove first element in queue
	 * @return
	 */
	public Object remove()
	{
		if (tail < 0)
			throw new NoSuchElementException();
		return elements[++head];
	}
	
	/**
	 * return size of queue
	 */
	public int size()
	{
		return elements.length;
	}
	
	/**
	 * Check if array is full; if it is the case, creates a new array.
	 */
	private void isFull()
	{
		if (tail >= theSize - 1)
		{
			Object[] newElements = new Object[elements.length * 2];
			for (int i = 0; i < elements.length; i++)
			{				
					System.arraycopy(elements, head + 1 +i, newElements, i, 1);
			}
			
			elements = newElements;
		}
	}
	
	private int head;
	private int tail;
	private int theSize;
	private Object[] elements;
}

Grazie mille a tutti coloro che vorranno dedicarci qualche minuto

[VincenzoTheBest]

La tecnica con cui le hai implementate non va per niente bene, in quanto la grandezza delle strutture cresce solamente e non di poco rispetto agli elementi inseriti.

Supposto che la dimensione della pila (risp. coda) venga impostata a k, dopo 3k inserimenti la struttura avrà una dimensione pari a k*2^3 per soli 3k elementi.

Ma questo con il codice java non c'entra niente..

[tigerjack89]

Originariamente inviato da VincenzoTheBest
La tecnica con cui le hai implementate non va per niente bene, in quanto la grandezza delle strutture cresce solamente e non di poco rispetto agli elementi inseriti.

Supposto che la dimensione della pila (risp. coda) venga impostata a k, dopo 3k inserimenti la struttura avrà una dimensione pari a k*2^3 per soli 3k elementi.

Ma questo con il codice java non c'entra niente..

yez questa è un'intressante pecca. Ovviamente ci saranno diversi modi per modificarla, come assegnare un valore arbitrario da aggiungere alla grandezza di newObject: qualcosa come newObject[object.length + n], con n a discrezione del programmatore.

Tuttavia non so quanto sia efficiente. Tu in che modo consiglieresti di "allungare" l'array?

Grazie mille come sempre

[bstefano79]

perchè non hai riportato gli attributi nelle classi???

[VincenzoTheBest]

Originariamente inviato da tigerjack89
Tuttavia non so quanto sia efficiente. Tu in che modo consiglieresti di "allungare" l'array?

Il problema sta nel fatto che la dimensione delle strutture cresce solamente.
Prima volevo farti notare che nei 3k inserimenti, anche se ci fossero delle rimozioni, la dimensione della struttura resta costante e quindi tale dimensione è destinata a crescere sempre.

[tigerjack89]

Originariamente inviato da bstefano79
perchè non hai riportato gli attributi nelle classi???

Che attributi intendi??

[bstefano79]

Originariamente inviato da tigerjack89
Che attributi intendi??

niente lascia perdere, li hai dichiarti dopo i metodi
essendo in genre dichiarti prima credevo non ci fossero

[tigerjack89]

Originariamente inviato da VincenzoTheBest
Il problema sta nel fatto che la dimensione delle strutture cresce solamente.

Sarebbe utile implementare un metodo che le accorciasse??
E in ogni caso...in che modo potrei farle crescere in modo efficiente senza raddoppiare la lunghezza dell'array originale?

[tigerjack89]

Originariamente inviato da bstefano79
niente lascia perdere, li hai dichiarti dopo i metodi
essendo in genre dichiarti prima credevo non ci fossero

in realtà sul mio manuale mi consiglia di dichiararli sempre dopo; è per questo che uso questo "schema" predefinito...vabbè non penso cambi molto in effetti

[lolide]

Intanto non so a csoa serva arraySize per lo stack, visto che facendo object.length lo recuperi. Poi comunque non ho capito perchè quando hai lo stack pieno in isfull allochi un array grande il doppio ... non basterebbe:

Object[] newObject = new Object[object.length + 1]

?