come progettare uno stack senza usare la libreria java o usando la lista [chiuso]

Uno stack può essere vuoto (che è davvero facile da scrivere), o non può essere vuoto, nel qual caso ha un elemento superiore e un puntatore al resto dello stack. Per implementare uno stack senza usare la libreria java,

• crea una classe chiamata Nodo, che contiene un riferimento a un puntatore al solo inserimento successivo.

• crea una classe chiamata MyStack, che contiene l'ultima voce dello stack. Vuoi anche includere queste due funzioni:

  push (valore):

  pop:

Uno stack è in realtà solo un'interfaccia, che fornisce almeno le seguenti operazioni:

• inserisci un nuovo elemento nello stack
• fai scoppiare un elemento fuori dallo stack

L'implementazione sottostante può essere qualsiasi cosa che soddisfi queste operazioni. Le matrici e gli elenchi sono implementazioni comuni per gli stack, ma è possibile creare uno stack (inefficiente) utilizzando una tabella hash o file su disco o anche pezzi di carta numerati sparsi per una stanza. Finché la capacità di push e pop è disponibile in qualche modo, è una pila.

Dato che tagghi la domanda come java risolviamo la domanda con ..... Oggetti! In realtà stiamo praticamente implementando una lista collegata singolarmente. Uno stack può essere vuoto (che è veramente facile da scrivere), o non può essere vuoto, nel qual caso ha un elemento in cima e un puntatore al resto dello stack.

Di seguito è riportato il codice per uno stack immutabile (uno in cui push o popping restituisce un nuovo stack invece di modificare quello esistente). Dovrai perdonare la formattazione, non so come inserire correttamente il codice nell'editor qui.

Prima hai un'interfaccia che dice cosa costituisce uno stack

public interface IStack<A> {

public boolean isEmpty();

public A peek();

public IStack<A> push(A a);

public IStack<A> pop();
}

Ci sono 2 tipi di IStack. Quelli che sono vuoti e quelli che non lo sono. Diamo un'occhiata a EmptyStack perché è più semplice.

import java.util.EmptyStackException;

public class EmptyStack<A> implements IStack<A> {

//Since all empty stacks are the same, you would want it to follow the singleton pattern instead of relying on the default constructor

public boolean isEmpty() {
    return true;
}

public A peek() {
    throw new EmptyStackException();
}

public IStack<A> push(A a) {
    return new Stack<A>(this, a);
}

public IStack<A> pop() {
    throw new EmptyStackException();
}
}

Ora esaminiamo una pila che non è vuota.

public class Stack<A> implements IStack<A>{

private IStack<A> _stack;
private A _a;

public Stack(IStack<A> stack, A a) {
    _stack = stack;
    _a = a;
}

public boolean isEmpty() {
    return false;
}

public A peek() {
    return _a;
}

public IStack<A> push(A a) {
    return new Stack<A>(this, a);
}

public IStack<A> pop() {
    return _stack;
}
}

Proviamo ad usarlo

public class Test {

public static void printInfo(String stackName, IStack<?> stack){
    System.out.println("-----------");
    System.out.println(stackName + ":");
    boolean isEmpty = stack.isEmpty();
    System.out.println("Is Empty: " + isEmpty);
    if(!isEmpty){
        System.out.println("Item: " + stack.peek());
    }
}

public static void main(String[] args) {
    IStack<Character> empty1 = new EmptyStack<Character>();
    IStack<Character> aStack1 = empty1.push('a');
    IStack<Character> abStack = aStack1.push('b');
    IStack<Character> aStack2 = abStack.pop();
    IStack <Character> empty2 = aStack2.pop();

    printInfo("empty1", empty1);
    printInfo("aStack1", aStack1);
    printInfo("abStack", abStack);
    printInfo("aStack2", aStack2);
    printInfo("empty2", empty2);
}
}

L'output dal test è

-----------
empty1:
Is Empty: true
-----------
aStack1:
Is Empty: false
Item: a
-----------
abStack:
Is Empty: false
Item: b
-----------
aStack2:
Is Empty: false
Item: a
-----------
empty2:
Is Empty: true

Non devi usare un array o un elenco, puoi creare uno stack semplice effettuando le seguenti operazioni:

• crea una classe chiamata StackEntry, che contiene solo un riferimento alla successiva voce dello stack.

• crea una classe denominata MyStack, che contiene l'ultima voce dello stack e due funzioni:

  push (valore):

  • crea una nuova voce dello stack.
  • lo imposta per fare riferimento alla voce dello stack corrente,
  • e impostalo come attuale sostituendo quello esistente.

  pop:

  • utilizza la voce dello stack corrente e ottiene la voce dello stack di riferimento,
  • imposta la corrente come voce dello stack di riferimento
  • restituisce la vecchia voce "corrente"

Concettualmente, una pila è una lista collegata senza accesso casuale e solo un punto di entrata: la parte superiore, mentre una lista ha spesso accesso casuale e due punti di entrata: la parte anteriore e quella posteriore. Mentre di solito c'è un T peek (), non è possibile utilizzare Peek per la manipolazione dei contenuti. L'accesso casuale viene generalmente spiegato come la capacità di manipolare in un dato punto della collezione.

Quindi, se stai dicendo senza usare una lista, intendi senza usare una classe List API Java come base per il tuo lavoro, o davvero non usando una lista? Quest'ultimo è quasi impossibile, in quanto fondamentalmente è un elenco, e l'implementazione in un altro modo sarebbe un esercizio paragonabile a fare una macchina Rube Goldberg.