Implementazione di una coda con due stack

di Anonimizzato10177 il
11 risposte
/
Anonimizzato10177
Utente anonimizzato
Salve mi è stato chiesto in un esercizio di implementare una coda sottoforma di array, con due stack(anch'essi sottoforma di array)..

in pratica dovrei implementare tutte le funzioni delle code (enqueue,dequeue etc) tramite le funzioni push e pop degli stack..

avete qualche idea??
a me non me ne viene neanche una..
grazie

11 Risposte

  • /
    Anonimizzato7532
    Utente anonimizzato
    Prima fai una domanda sensata. Coda = queue (FIFO), pila = stack (FILO).
    Tu vuoi creare una coda con due pile?
    cmq una implementazione di stack con array lo trovi quà:
    http://www.cs.bu.edu/teaching/c/stack/array
  • /
    Anonimizzato10177
    Utente anonimizzato
    Nn hai capito..
    io devo usa i due stack per implementare una coda..
    le implementazioni dello stack gia ce li ho..
  • /
    Anonimizzato10177
    Utente anonimizzato
    Ecco una possibile soluzione..
    voi ci capite qualcosa??

    Siano H e T sue Stack tali che la coda sia il risultato della
    concatenazione dello Stack H (partendo dal Top al Bottom) con
    lo Stack T (dal Bottom al Top).

    Nella situazione iniziale, tutti gli elementi sono posti nello Stack
    H dove l elemento al Top è la testa (Head) della coda, mentre
    quello al Bottom rappresenta la fine della coda (Tail)
    Quando H è vuoto allora si svuota il rewerse di T in H.

    In dettaglio, per ogni elemento di T, si farà il Pop in T e il Push in
    H, fino a quando T non diventa vuoto.

    Per cancellare un elemento dalla coda, si farà un POP dallo
    stack H, il quale non sarà mai vuoto a meno che l intera coda
    non diventi vuota.

    Per inserire un elemento nella coda si fa un Push nello Stack T.
  • /
    Anonimizzato9942
    Utente anonimizzato
    Non è un esempio di chiarezza ma credo di aver capito.

    Chiami 'Coda' una struttura FIFO (il primo che arriva è il primo a uscire).
    Chiami 'Stack' una struttura LIFO (l' ultimo arrivato è il primo a uscire).

    Il problema ti chiede di realizzare una coda (FIFO) usando degli stack (LIFO).
    La soluzione proposta si basa su questo principio, se usi due stack e svuoti uno stack in un altro in pratica ribalti l' ordine degli elementi, per cui se svuoti dal secondo stack scarichi nell' ordine giusto (FIFO).
  • /
    Anonimizzato10177
    Utente anonimizzato
    Si ok ma non si potrebbe fare il tutto semplicemente avendo a disposizione un solo stack ed utilizzando un algoritmo ricorsivo??


    ps:
    so che non è il massimo della correttezza.. ma avrei una soluzione da farti visionare.. a me sembra efficientissima ma mi devi dire soltanto se la logica è corretta o meno..
    hai messenger o skype??
    ti prego è una cosa lunga e sarebbe meglio parlarne a tu per tu
    grazie ancora
  • /
    Anonimizzato9942
    Utente anonimizzato

    Gauss ha scritto:

    so che non è il massimo della correttezza.. ma avrei una soluzione da farti visionare.. a me sembra efficientissima ma mi devi dire soltanto se la logica è corretta o meno..
    hai messenger o skype??
    ti prego è una cosa lunga e sarebbe meglio parlarne a tu per tu
    Perchè non la scrivi qui? Magari interessa anche ad altri e poi senti più pareri!
  • /
    Anonimizzato10177
    Utente anonimizzato
    Senti lasciamo sta va..
  • /
    Anonimizzato9668
    Utente anonimizzato
    In effetti una soluzione può essere come quella illustrata da Gauss, con due stack, uno 'che riceve' le Push chiamato ad esempio 'receive', l'altro 'che rilascia' con la Pop chiamato ad esempio 'release'. Ovviamente il contenuto di 'release' viene 'aggiornato' solo quando esso è vuoto e solo se si chiama una Pop, ad esempio : 
    
bool Queue::pop(T &e){
    T temp;
    if(release.isEmpty())
        while(receive.pop(temp)) release.push(temp);
    if (release.isEmpty()) return false;
    else{
        release.pop(temp);
        e=temp;
        return true;
    }
}
  • /
    Anonimizzato9942
    Utente anonimizzato
    Si questa soluzione è giusta e segue la traccia indicata dal prof (è un esercizio universitario, vedi in rete). La cosa che mi incuriosiva era l' idea di gauss di risolvere il problema con un solo stack e un algoritmo ricorsivo. Così ad occhio mi sembra sbagliato, nel senso che sarebbe estremamente inefficiente, per estrarre il primo elemento dallo stack dovrebbe svuotarlo e poi riempirlo di nuovo. Ma magari mi sbaglio.
  • /
    Anonimizzato9668
    Utente anonimizzato
    Per quanto l'efficienza essa è dovuta dalla richiesta stessa di implementare una coda con due stack, dato che potrebbe essere facilmente implementata con una soluzione più efficiente . Comunque penso che con due stack quello che ho scritto possa essere una buona implementazione, infatti la push della coda viene fatta solo su un solo stack dei due(ad esempio 'receive'), mentre l'altra serve solo per la pop(ad esempio 'release'). quando bisogna prelevare dalla coda poi 'receive' viene svuotato solo se 'release' è vuoto, ed una volta riversati i dati da 'receive' a 'release' i dati non vengono rimessi di nuovo in 'receive', ma rimangono in 'release' per futuri prelievi.
  • /
    Anonimizzato9942
    Utente anonimizzato
    Per quanto riguarda la soluzione con due stack, sono d'accordo con te, la soluzione che hai scritto è efficiente e non credo si possa far di meglio. L' unico problema è che Gauss sembra sparito.
Devi accedere o registrarti per scrivere nel forum
11 risposte