Definizione di uno stack di caratteri in Java

1. Panoramica

In questo tutorial, discuteremo come creare uno stack di caratteri in Java. Vedremo prima come possiamo farlo utilizzando l'API Java, quindi esamineremo alcune implementazioni personalizzate.

Stack è una struttura dati che segue il principio LIFO (Last In First Out). Alcuni dei suoi metodi comuni sono:

  • push (E item) : spinge un oggetto in cima alla pila
  • pop () : rimuove e restituisce l'oggetto in cima alla pila
  • peek () : restituisce l'oggetto in cima alla pila senza rimuoverlo

2. Char Pila Usando Java API

Java ha un'API incorporata denominata java.util.Stack . Poiché char è un tipo di dati primitivo , che non può essere utilizzato nei generici, dobbiamo utilizzare la classe wrapper di java.lang.Character per creare uno Stack :

Stack charStack = new Stack();

Ora possiamo usare i metodi push , pop e peek con il nostro Stack .

D'altra parte, ci potrebbe essere chiesto di creare un'implementazione personalizzata di uno stack. Pertanto, esamineremo un paio di approcci diversi.

3. Implementazione personalizzata utilizzando LinkedList

Implementiamo uno stack di caratteri utilizzando un LinkedList come struttura dati di back-end:

public class CharStack { private LinkedList items; public CharStack() { this.items = new LinkedList(); } }

Abbiamo creato una variabile di elementi che viene inizializzata nel costruttore.

Ora dobbiamo fornire un'implementazione dei metodi push , peek e pop :

public void push(Character item) { items.push(item); } public Character peek() { return items.getFirst(); } public Character pop() { Iterator iter = items.iterator(); Character item = iter.next(); if (item != null) { iter.remove(); return item; } return null; }

I metodi push e peek utilizzano i metodi incorporati di un LinkedList . Per il pop , abbiamo prima usato un Iterator per verificare se c'è un elemento in alto o meno. Se è presente, rimuoviamo l'elemento dall'elenco chiamando il metodo di rimozione .

4. Implementazione personalizzata utilizzando un array

Possiamo anche usare un array per la nostra struttura dati:

public class CharStackWithArray { private char[] elements; private int size; public CharStackWithArray() { size = 0; elements = new char[4]; } }

Sopra, creiamo un array di caratteri , che inizializziamo nel costruttore con una capacità iniziale di 4. Inoltre, abbiamo una variabile di dimensione per tenere traccia di quanti record sono presenti nel nostro stack.

Ora implementiamo il metodo push :

public void push(char item) { ensureCapacity(size + 1); elements[size] = item; size++; } private void ensureCapacity(int newSize) { char newBiggerArray[]; if (elements.length < newSize) { newBiggerArray = new char[elements.length * 2]; System.arraycopy(elements, 0, newBiggerArray, 0, size); elements = newBiggerArray; } }

Mentre si inserisce un elemento nello stack, dobbiamo prima verificare se il nostro array ha la capacità di memorizzarlo. In caso contrario, creiamo un nuovo array e ne raddoppiamo le dimensioni. Copiamo quindi i vecchi elementi nell'array appena creato e lo assegniamo alla nostra variabile di elementi .

Nota: per una spiegazione del motivo per cui vogliamo raddoppiare la dimensione dell'array, piuttosto che aumentare semplicemente la dimensione di uno, fai riferimento a questo post di StackOverflow.

Infine, implementiamo i metodi peek and pop :

public char peek() { if (size == 0) { throw new EmptyStackException(); } return elements[size - 1]; } public char pop() { if (size == 0) { throw new EmptyStackException(); } return elements[--size]; }

Per entrambi i metodi, dopo aver verificato che lo stack non è vuoto, restituiamo l'elemento alla posizione size - 1. Per pop , oltre a restituire l'elemento, diminuiamo la dimensione di 1.

5. conclusione

In questo articolo, abbiamo imparato come creare uno stack di caratteri utilizzando l'API Java e abbiamo visto un paio di implementazioni personalizzate.

Il codice presentato in questo articolo è disponibile su GitHub.