Domanda Array generici dinamici

[Excdt77]

Salve a tutti, mi servirebbe un array generico dinamico, in pratica mi sto esercitando con gli stuck e ne vorrei uno che si ingrandisse quando è pieno. Visto che non compila quando si cerca di creare un nuovo array generico come posso fare senza , ovviamente, modificare il codice?
ad esempio se fosse un array di int sarebbe:

if(indice == stuck.length - 1){

    int array[] = new int[stuck.length * 2];

    //resto delle istruzioni

}

come posso fare con un array generico?

 

[CrashTest]

Credo tu voglia implementare uno stAck (una pila) piuttosto che uno stUck (inceppato). Cosa intendi per generico? Se intendi usando i generics allora non lo stai facendo. Questo pezzo di codice non vedo perché non dovrebbe compilare, sicuramente il problema è nel resto delle istruzioni. Magari se mostri una sezione di codice più ampia possiamo aiutarti meglio

 

[Excdt77]

Si intendevo stack.
ma infatti non ho scritto che è quello il pezzo di codice che non compila, l'ho messo solo per farvi capire cosa voglio fare ma lo voglio implementare con i generics, sta scritto anche sotto al pezzo di codice. visto che con i generics non compila volevo sapere se c'era un altro modo

 

[Kaysan]

Quello di cui hai bisogno è già fatto da LinkedList. Se è un esercizio, ti consiglierei prima di studiare cosa voglia dire "generics", se hai già fatto una classe generica, ma non compila, posta quella così possiamo dirti dove hai sbagliato.

 

[St3ve]

se hai già fatto una classe generica, ma non compila, posta quella così possiamo dirti dove hai sbagliato.

Thumbs up perché è questo il modo corretto di procedere, in alternativa andava bene anche postare uno stack non generico e chiedere come trasformarlo in generico. Avrei voluto aspettare una risposta, ma dopo 4-5 giorni ho un po' perso la fiducia. Lo reputo comunque un esercizio carino (aiuta a capire come sono implementati i generics in Java) e un po' diverso dalle richieste tipiche di questa sezione. Posto direttamente la soluzione, nella speranza che interessi a qualcuno.

import java.util.Arrays;

public class Stack<T> {
  private Object[] data;
  private int size = 0;

  public Stack() { this(1); }
  public Stack(int size) { data = new Object[size]; }

  public int size() { return size; }

  public T top () {
    if (size == 0) throw new IndexOutOfBoundsException("No such element");
    return element(size - 1);
  }

  public T pop() {
    T result = top();
    size--;
    return result;
  }

  public void push(T e) {
    if (data.length < size + 1) grow();
    data[size++] = e;
  }

  @SuppressWarnings("unchecked")
  private T element(int i) { return (T) data[i]; }

  private void grow() {
    int capacity = data.length * 2;
    data = Arrays.copyOf(data, capacity);
  }
}

Se a qualcuno interessano spiegazioni, se ne può discutere.

 

[nullptr]

L'alternativa a LinkedList sarebbe ArrayList.

L'idea di @St3ve sembra carina e semplice per capire la parte rudimentale del contesto, ma secondo me sarebbero molto più efficienti le prime due invece di copiare ogni volta i valori con Arrays.copyOf().

 

[St3ve]

Quello di cui hai bisogno è già fatto da LinkedList

L'alternativa a LinkedList sarebbe ArrayList.

LinkedList non è quello che vuole l'utente, ma ArrayList lo è: un'area contigua di memoria (che si espande automaticamente) per mantenere i dati. L'ideale ovviamente sarebbe usare Deque: lo stack (stack + queue) implementato nella libreria standard, che può essere istanziato sia come ArrayDeque (memoria contigua) che come LinkedList ("puntatori").

L'idea di @St3ve sembra carina e semplice per capire la parte rudimentale del contesto, ma secondo me sarebbero molto più efficienti le prime due invece di copiare ogni volta i valori con Arrays.copyOf().

Quello che ho fatto io è quello che succede nell'implementazione di ArrayList (o ArrayDeque), nonché quello che ha grossomodo proposto @Excdt77. La copia è inevitabile se si vuole la memoria contigua. Può essere altrettanto didattica un'implementazione a basso livello (i.e., senza usare LinkedList) di uno stack generico implementato con il meccanismo dei link. Se qualcuno è curioso e non sa farla se ne può discutere... mal che vada scrivo io il codice (tanto è corto), basta chiedere.

 

[nullptr]

L'ideale ovviamente sarebbe usare Deque: lo stack (stack + queue) implementato nella libreria standard, che può essere istanziato sia come ArrayDeque (memoria contigua) che come LinkedList ("puntatori").

Questa idea sembra un'alternativa più fresca. Tu preferiresti utilizzarlo al posto di ArrayList<T>? Se sì, mi piacerebbe afferrarne i motivi.

La copia è inevitabile se si vuole la memoria contigua

Esattamente, in quanto non esiste nessun metodo dinamico per amplificare un array esistente (più che grow quella funzione la chiamerei recreate). Però a mio parere credo sia più utile come rimedio la collezione perchè artefatta e appositamente per quella cosa, e a mio avviso Java non è fatto per gestire la memoria manualmente (se non a scopo didattico fare qualcosa di quel tipo) a meno che bisogna provarsi per qualche memory leak.

 

[St3ve]

Questa idea sembra un'alternativa più fresca. Tu preferiresti utilizzarlo al posto di ArrayList<T>? Se sì, mi piacerebbe afferrarne i motivi.

Principalmente perché è fatta apposta per quello. Java ha anche una classe Stack, ma è deprecata in favore di Deque: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class". In termini di performance ArrayList e ArrayDeque dovrebbero essere pressoché identici, ma la prima è meno pratica da usare mentre la seconda fornisce direttamente l'astrazione dello stack: deque vuol dire stack+queue e noi ci limitiamo ad usare le sue funzionalità da stack, con una list queste astrazioni te le devi costruire a mano e sebbene per lo stack sia molto semplice (e.g., quello che io ho chiamato top, ovvero deque.getFirst(), diventa arraylist[arraylist.size() - 1]) è comunque meno diretto.

più che grow quella funzione la chiamerei recreate

Grow è il nome scelto da java per quel tipo di operazione, in C++ si chiama reserve. Semmai top avrei dovuto chiamarlo peek.

Però a mio parere credo sia più utile come rimedio la collezione perchè artefatta e appositamente per quella cosa, e a mio avviso Java non è fatto per gestire la memoria manualmente (se non a scopo didattico fare qualcosa di quel tipo) a meno che bisogna provarsi per qualche memory leak.

Yep. Immagino che ArrayDeque sia implementato usando ArrayList e ArrayList dovrebbe avere un'implementazione molto simile a quella che ho riportato io. Ovviamente è sempre meglio usare le astrazioni che abbiamo creato in precedenza per crearne delle nuove. Chi vuole usare uno stack in java dovrebbe usare quello già implementato dalla libreria standard (Deque). La mia era una risposta didattica a "come si implementa uno stack?" e implementarlo usando altre astrazioni per sembrava poco informativo: a quel punto ci si domanderebbe "come si implementa ArrayList?". Ho seguito l'idea di Excdt77 che è effettivamente quello che avviene under the hood quando usiamo ArrayDeque (o ArrayList).
Dei memory leaks non c'è da preoccuparsi perché java ha un garbage collector: se riesci a causare un memory leak senza hackerare troppo, è un bug della JVM. Comunque sì, java non è ideale per fare le cose a basso livello... ciò non toglie che certe cose si possano fare, infatti i containers della libreria standard sono implementati proprio in questo modo e trovo didattico dargli un'occhiata. Adesso, per esempio, è molto facile capire perché puoi fare un ArrayList di Integer ma non puoi farla di int.

 

[nullptr]

Dei memory leaks non c'è da preoccuparsi perché java ha un garbage collector: se riesci a causare un memory leak senza hackerare troppo, è un bug della JVM

Vabbè, questo è un argomento a parte. Sì, molto difficilmente riesci a conseguire un memory leak a livello pratico (anche se è è possibile in casi molto rari)... almeno che lo fai intenzionalmente, in questo caso ho trovato un codice campione che potrebbe farci capire come è possibile.

dovrebbe avere un'implementazione molto simile a quella che ho riportato io

Sì.

 

[ArrackHack]

Più che generics mi sembra che qui ci voglia una lettura delle Java Collections. Comunque la class Stack è deprecata, qualsiasi sia l'utilizzo che se ne voglia fare. Quella che la sostituisce è ArrayDequeue