Buonasera a tutti, ho realizzato un programma in c++ che simula il funzionamento di una coda la quale segue l’algoritmo FIFO (FIRST IN FIRST OUT), dunque, il primo elemento immesso è il primo ad uscire.
I due puntatori che ho utilizzato per gestire la coda sono END E BEGIN, entrambi inizializzati a 0. Il puntatore END viene incrementato nel momento in cui viene richiesta la PUSH (quindi di immettere il dato) mentre il puntatore BEGIN viene incrementato quando si richiede la POP(estrazione del dato)
SPIEGO IL MIO RAGIONAMENTO
Ho utilizzato una variabile temporanea “Tempend” che punta alla prima cella vuota , e l’ho incrementata progressivamente insieme ad END, nel momento in cui supera la dimensione massima della coda (MAX+1) si è verificato un overflow e non posso piu immettere dati.
La dimensione della coda sarebbe MAX+1 perché appunto tempend punta alla prima cella vuota.
Quando Begin e End si trovano allo stesso indice, VALE A DIRE CHE LA CODA RISULTA ESSERE VUOTA, e dunque non è possibile estrarre dati perché non ce ne sono. Quando invece tempend==begin la coda risulterà piena, si è verificato dunque un overflow.
In questa prima versione del programma riscontro solo un problema…quando end supera il massimo viene settato di nuovo a 0. Però poi se si verifica ciò, ho problemi perche il ciclo for della stampa scorre da begin a end e dato che end è settato a 0 begin risulterà essere maggiore di quest’ultimo.
SCRIVO IL CODICE DELLA PRIMA VERSIONE DEL PROGRAMMA
#include <iostream>
using namespace std;
const int MAX = 3; //dimensione massima della coda
int Coda[MAX]; // array per la coda
int END,BEGIN;
// prototipi delle funzioni
void SvuotaCoda();
void Pop();
void Push();
void ScriviCoda();
void PresentaMenu();
// funzione principale
int main()
{
int scelta; // scelta nel menu
SvuotaCoda();
do {
do {
PresentaMenu();
cout << "Inserisci la tua scelta =>";
cin >> scelta;
} while (scelta<1 || scelta>5);
switch(scelta) {
case 1:
SvuotaCoda();
break;
case 2:
Pop();
break;
case 3:
Push();
break;
case 4:
ScriviCoda();
break;
}
} while (scelta != 5);
return 0;
}
// inizializzazione della pila
void SvuotaCoda()
{
BEGIN = 0; //inizializziamo il puntatore begin ( da muovere con la POP)
END =0; //inizializziamo il puntatore END ( da muovere con la PUSH)
cout << "Coda vuota" << endl;
}
void Pop() // funzione POP = estrazione di un elemento dalla coda
{
if (BEGIN == END) //Se begin e end si trovano allo stesso indice la coda sarà vuota e dunque non ci sono elementi da estrarre
cout << "Non ci sono elementi da estrarre!" << endl;
else {
cout << "Elemento estratto = " << Coda[BEGIN] << endl; //altrimenti si estrae il dato
BEGIN++; if(BEGIN>MAX) BEGIN=0; //dopo aver immesso il dato, begin lo incrementiamo e se è maggiore di MAX ritorna a 0
}
}
void Push()
{
int dato,tempend; // elemento da inserire
tempend=END+1; if(tempend>MAX) tempend=0;
if (tempend==BEGIN){
cout << "Coda piena!!! NON E POSSIBILE AGGIUNGERE ALTRI DATI !!!" << endl;}
else {
cout << "Dato da inserire = ";
cin >> dato;
Coda[END] = dato;
END=tempend;
}
} // Push
void ScriviCoda()
{
cout << "INIZIO CODA" << endl;
for (int i=BEGIN ; i<=END-1; i++) cout << Coda[i] << endl; //FOR CHE ATTRAVERSA LA CODA E LA STAMPA DAL PRIMO DATO IMMESSO (CODA FIFO) PER POI PROSEGUIRE FINO ALL'ULTIMO
cout << "FINE CODA" << endl;
cout << " VALORE END " << END<<endl;
cout << "VALORE BEGIN " <<BEGIN<< endl;
}
// menu delle scelte
void PresentaMenu()
{
cout << endl;
cout << "1. SVUOTA CODA" << endl;
cout << "2. ESTRAI DATO (POP)" << endl;
cout << "3. IMMETTI DATI (PUSH)" << endl;
cout << "4. VISUALIZZA CODA " << endl;
cout << "5. FINE PER TERMINARE" << endl;
}
Inoltre il professore ci ha chiesto di modificare il programma e invece di utilizzare la variabile tempfin ci ha chiesto di gestire l’overflow e la situazione di “coda vuota” con un flag.
Ho provato a modificarlo, dichiarando una variabile booleana coda_piena nella funzione push e coda_vuota nella funzione pop .Eliminando dunque tempend la dimensione della coda non sarà piu pari a MAX +1 bensi a MAX.
Però, utilizzando la variabile temporanea nella prima versione del programma end si riavvolgeva senza alcun problema, utilizzando il flag non mi si riavvolge correttamente. Esempio:
Faccio 3 PUSH E 3 POP . Se voglio continuare a immettere i dati il programma me lo dovrebbe far fare, settando end di nuovo a 0 e facendolo ripartire, ma entra invece nella condizione di coda piena non permettendomi piu di inserire dati.
SCRIVO IL CODICE DELLA SECONDA VERSIONE DEL PROGRAMMA (CON FLAG)
#include <iostream>
using namespace std;
const int MAX = 3; //dimensione massima della coda
int Coda[MAX]; // array per la coda
int END,BEGIN;
bool coda_piena=false;
// prototipi delle funzioni
void SvuotaCoda();
void Pop();
void Push();
void ScriviCoda();
void PresentaMenu();
// funzione principale
int main()
{
int scelta; // scelta nel menu
SvuotaCoda();
do {
do {
PresentaMenu();
cout << "Inserisci la tua scelta =>";
cin >> scelta;
} while (scelta<1 || scelta>5);
switch(scelta) {
case 1:
SvuotaCoda();
break;
case 2:
Pop();
break;
case 3:
Push();
break;
case 4:
ScriviCoda();
break;
}
} while (scelta != 5);
return 0;
}
// inizializzazione della pila
void SvuotaCoda()
{
BEGIN = 0; //inizializziamo il puntatore begin ( da muovere con la POP)
END = 0; //inizializziamo il puntatore END ( da muovere con la PUSH)
cout << "Coda vuota" << endl;
}
void Pop() // funzione POP = estrazione di un elemento dalla coda
{
bool coda_vuota=false;
if (BEGIN == END){
coda_vuota=true;}
if(coda_vuota) cout << "NON CI SONO ELEMENTI DA ESTRARRE!" << endl;
if(!coda_vuota) {
cout << "Elemento estratto = " << Coda[BEGIN] << endl;
BEGIN++;
if(BEGIN==MAX) BEGIN=0; coda_vuota=false;
if(END==0) coda_piena=false;
}
}
void Push()
{
int dato; // elemento da inserire
if (END==MAX){
coda_piena=true;END=0;}
if(coda_piena) cout << "Coda piena!!! NON E POSSIBILE AGGIUNGERE ALTRI DATI !!!" << endl;
if(!coda_piena){
cout << "Dato da inserire = ";
cin >> dato;
Coda[END] = dato;
END++;
}
} // Push
void ScriviCoda()
{
cout << "INIZIO CODA" << endl;
for (int i=BEGIN ; i<=END-1; i++) cout << Coda[i] << endl; //FOR CHE ATTRAVERSA LA CODA E LA STAMPA DAL PRIMO DATO IMMESSO (CODA FIFO) PER POI PROSEGUIRE FINO ALL'ULTIMO
cout << "FINE CODA" << endl;
cout << " VALORE END " << END<<endl;
cout << "VALORE BEGIN " <<BEGIN<< endl;
}
// menu delle scelte
void PresentaMenu()
{
cout << endl;
cout << "1. SVUOTA CODA" << endl;
cout << "2. ESTRAI DATO (POP)" << endl;
cout << "3. IMMETTI DATI (PUSH)" << endl;
cout << "4. VISUALIZZA CODA " << endl;
cout << "5. FINE PER TERMINARE" << endl;
}
Spero possiate darmi qualche consiglio, vi ringrazio anticipatamente.