Newsgroup: it.comp.lang.c
Titolo: Implementazione coda a doppia entrata con array.

Ciao a tutti.
Innanzitutto grazie per le risposte, sempre puntuali ed esaurienti.
L'esercizio che vi propongo adesso mi chiede di implementare con un 
array una coda a doppia entrata.
Ho cercato di realizzarlo gestendo tutte le situazioni possibili 
(aggiunta di elementi a code piene, eliminazione da code vuote, code 
disposte circolarmente nel vettore, ecc.). L'unica cosa che non riesco a 
realizzare è una funzione di stampa che funzioni in tutti i casi. 
Sapreste aiutarmi?
Vi posto il mio codice: 
***Nel file dequeue.h:
//File di intestazione per il programma stampa_dequeue.
#include <stdio.h>
#include <stdlib.h>
#define MaxLung 5 //numero massimo di elementi nella dequeue.
typedef enum boolean {false, true} boolean;
typedef int data; //Cambiarla per implementare dequeue contenenti 
elementi di altro tipo.
typedef enum stato {empty, normal, full} stato; //normal = né piena né 
vuota 
typedef struct dequeue {
 data items[MaxLung]; //la dequeue vera e propria.
 int front; //la posizione nell'array dell'elemento in testa alla 
dequeue.
 int back; //la posizione nell'array dell'elemento in coda alla dequeue.
 stato state; //Dice se la dequeue è vuota o piena.
} dequeue;
void reset(dequeue *dq); 
//Cancella tutti gli elementi della dequeue. Utilizata di solito 
all'inizio dei programmi.
void AddToFront(dequeue *dq, data x);
//Inserisce un elemento in testa alla dequeue.
void AddToBack(dequeue *dq, data x);
//Inserisce un elemento in coda alla dequeue.
data TakeFromFront(dequeue *dq);
//Preleva l'elemento in testa alla dequeue e lo restituisce.
data TakeFromBack(dequeue *dq);
//Preleva l'elemento in coda alla dequeue e lo restituisce.
boolean vuota(const dequeue *dq);
//Restituisce true se la dequeue è vuota, false altrimenti.
boolean piena(const dequeue *dq);
//Restituisce true se la dequeue è piena, false altrimenti.
void stampa(dequeue *d); //Stampa la dequeue, dalla coda fino alla 
testa.
***Nel file dequeue.c:
/*Funzioni per gestire la dequeue nel programma stampa_dequeue. Assieme 
al file di intestazione dequeue.h,
possono essere utilizzate per gestire code a doppia entrata di qualsiasi 
tipo, implementate con un array. */
#include "dequeue.h"
void reset(dequeue *dq) {
//Cancella tutti gli elementi della dequeue. Utilizata di solito 
all'inizio dei programmi.
 dq -> front = -1;
 dq -> back = 0;
 dq->state = empty;
}
void AddToFront(dequeue *dq, data x) {
//Inserisce un elemento in testa alla dequeue.
 if (piena(dq))
  printf("AddToFront errore: coda piena.\n");
 else {
  dq -> front = (dq->front + 1) % MaxLung;
  dq -> items[dq -> front] = x;
  if (dq->back == (dq->front + 1) % MaxLung)
   dq->state = full;
  else
   dq->state = normal;
 }
}
void AddToBack(dequeue *dq, data x) {
//Inserisce un elemento in coda alla dequeue.
 if (piena(dq))
  printf("AddToBack errore: coda piena.\n");
 else {
  dq -> back = (dq->back + MaxLung - 1) % MaxLung;
  dq -> items[dq -> back] = x;
  if (dq->back == (dq->front + 1) % MaxLung)
   dq->state = full;
  else
   dq->state = normal;
 }
}
data TakeFromFront(dequeue *dq) {
//Preleva l'elemento in testa alla dequeue e lo restituisce.
 data x;
 if (vuota(dq)) {
  printf("TakeFromFront errore: coda vuota.\n");
  exit(1);
 }
 else {
  x = dq -> items[dq -> front];
  dq -> front = (dq -> front + MaxLung - 1) % MaxLung;
  if (dq->back == (dq->front + 1) % MaxLung)
   dq->state = empty;
  else
   dq->state = normal;
 }
 return x;
}
data TakeFromBack(dequeue *dq) {
//Preleva l'elemento in coda alla dequeue e lo restituisce.
 data x;
 if (vuota(dq)) {
  printf("TakeFromBack errore: coda vuota.\n");
  exit(1);
 }
 else {
  x = dq -> items[dq -> back];
  dq -> back = (dq -> back + 1) % MaxLung;
  if (dq->back == (dq->front + 1) % MaxLung)
   dq->state = empty;
  else
   dq->state = normal;
 }
 return x;
}
boolean vuota(const dequeue *dq) {
//Restituisce true se la dequeue è vuota, false altrimenti.
 return (boolean) (dq->state == empty);
}
boolean piena(const dequeue *dq) {
//Restituisce true se la dequeue è piena, false altrimenti.
 return (boolean) (dq->state == full);
}
***Nel file stampa_dequeue.c:
//Inserisce ed elimina elementi in una dequeue ed effettua delle stampe.
#include "dequeue.h"
int main(void) {
 int i;
 dequeue d;
 reset(&d);
 AddToFront(&d, 1);
 AddToFront(&d, 2);
 AddToFront(&d, 3);
 AddToFront(&d, 4);
 AddToFront(&d, 5);
 stampa(&d);
 AddToFront(&d, 6);
 stampa(&d);
 TakeFromBack(&d);
 stampa(&d);
 TakeFromBack(&d);
 stampa(&d);
 TakeFromBack(&d);
 stampa(&d);
 TakeFromBack(&d);
 stampa(&d);
 TakeFromBack(&d);
 stampa(&d);
 TakeFromBack(&d);
 stampa(&d);
 TakeFromFront(&d);
 stampa(&d);
 AddToBack(&d, 20);
 stampa(&d);
 return 0;
}
void stampa(dequeue *d) {
//Stampa la coda, dalla coda fino alla testa.
 int i = d->back;
 if (d->state == empty)
  printf("%s", "Nessun elemento presente.");
 else
  do {
   printf("%d ", d->items[i]);
   i = (i + 1) % MaxLung;
  } while (i != d->front); 
 putchar('\n');
}
Grazie a chi ha avuto la pazienza di arrivare fin qui e un saluto a 
tutti.
Bizio.

 realizzare è una funzione di stampa che funzioni in tutti i casi. 
In quali casi non funziona?
E.


 data items[MaxLung]; //la dequeue vera e propria.
Perché tu possa implementare la coda con un array, hai bisogno - a mio
avviso - di shiftare gli elementi quando "pushi" e "poppi" in testa,
altrimenti non credo che piena e vuota abbiano alcun senso...

Andrea Laforgia ha scritto:

Perchè? E' computazionalmente molto costoso shiftare gli elementi. Il 
flag piena/vuota serve proprio a distinguere i due casi quando i 
puntatori front/back coincidono.
E.

E' computazionalmente molto costoso shiftare gli elementi.
E' ovvio che č computazionalmente molto costoso e per lo stesso
motivo, per implementare le code NON si usano gli array.

 motivo, per implementare le code NON si usano gli array.
Invece ci sono situazioni in cui è la soluzione migliore, non puoi 
essere categorico in queste affermazioni. Se c'è un limite superiore 
alla lunghezza che può avere la coda, e se questo limite viene raggiunto 
frequentemente allora mi sento di affermare che questa E' la soluzione 
migliore. (sono anch'io categorico, ma con premessa).
E.

 testa.
Sostanzialmente vuoi gestire un buffer circolare come una FIFO e
anche come un LIFO.
Invece dello stato forse ti conviene usare un contatore di elementi
inseriti, provo a modificare un po' il tuo codice, per vedere come 
potrebbe essere la modifica (ma non l' ho provato ;-))
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
#define MAX_ELEM		(100)
typedef struct ring_str{
	int	ringIn;		// Puntatore elementi al fondo
	int	ringOut;    // Puntatore elementi in testa
	int	ringCnt;	// Contatore elementi nella coda
	int	ringSize;	// Dimensione buffer
}RING_T;
typedef int data;
typedef struct queue{
	RING_T	h;
	data    buf[MAX_ELEM];   // pari a ringSize...
}QUEUE_T;
typedef enum boolean {false, true} boolean;
//void reset(dequeue *dq);
void rngReset(QUEUE_T* pRing)
{
  //-------> Accesso concorrente lock
  pRing->h.ringIn=0;
  pRing->h.ringOut=pRing->h.ringCnt=0;
 
  pRing->h.ringSize=MAX_ELEM;	// Dimensione buffer statico
  //-------> Accesso concorrente unlock
}
//Inserisce un elemento in testa alla coda (FIFO)
int rngAddToFront(QUEUE_T* pRing, data x)
{
   if (pRing->h.ringCnt >= pRing->h.ringSize)
     return(-1); // Coda piena
    //-------> Accesso concorrente lock
    if ( ++pRing->h.ringOut >= pRing->h.ringSize)
      pRing->h.ringOut=0;	/* roll-over */
   pRing->buf[pRing->h.ringOut]=x;
   pRing->h.ringCnt++;
   //-------> Accesso concorrente unlock
   return(1);  // elemento inserito
}
//Preleva l'elemento in coda e lo restituisce (FIFO)
int rngTakeFromBack(QUEUE_T* pRing, data* px)
{
    if (0==pRing->h.ringCnt )
      return(-1); // Coda vuota
   //-------> Accesso concorrente lock
   if ( ++pRing->h.ringIn >= pRing->h.ringSize)
      pRing->h.ringIn=0;	/* roll-over */
   pRing->h.ringCnt--;
   *px = pRing->buf[pRing->h.ringIn];
   //-------> Accesso concorrente unlock
   return(1);  // elemento rimosso
}
//Inserisce un elemento in coda (LIFO)
int rngAddToBack(QUEUE_T* pRing, data x)
{
    if (pRing->h.ringCnt >= pRing->h.ringSize)
      return(-1); // Coda piena
   //-------> Accesso concorrente lock
    pRing->buf[pRing->h.ringIn]=x;
    (pRing->h.ringIn) ? (pRing->h.ringIn--):
                        (pRing->h.ringIn=(pRing->h.ringSize-1));
   pRing->h.ringCnt++;
   //-------> Accesso concorrente unlock
   return(1);  // elemento inserito
}
//Preleva l'elemento in testa alla coda (LIFO)
int rngTakeFromFront(QUEUE_T* pRing, data* px)
{
   if (0==pRing->h.ringCnt )
     return(-1); // Coda vuota
    //-------> Accesso concorrente lock
   *px = pRing->buf[pRing->h.ringOut];
   (pRing->h.ringOut) ? (pRing->h.ringOut--):
                        (pRing->h.ringOut=(pRing->h.ringSize-1));
    pRing->h.ringCnt--;
    //-------> Accesso concorrente unlock
    return(1);  // elemento rimosso
}
//boolean vuota(const dequeue *dq);
boolean rngIsEmpty(QUEUE_T* pRing)
{
    return( ((pRing->h.ringCnt)? true: false));
}
//boolean piena(const dequeue *dq);
boolean rngIsFull(QUEUE_T* pRing)
{
    return( ((pRing->h.ringCnt>=pRing->h.ringSize)? true: false));
}
// Stampa elementi come FIFO
void stampa(QUEUE_T* pRing)
{
    int ringIn,j;
    if(pRing->h.ringCnt)
    {
        printf("Nessun elemento presente.\n");
        return;
    }
    //-------> Accesso concorrente lock
    printf("\nLista elementi:\n");
    ringIn= pRing->h.ringIn;
    for(j=0; j < pRing->h.ringCnt; j++)
    {
       if ( ++ringIn >= pRing->h.ringSize)
          ringIn=0;	/* roll-over */
       printf("%d ", pRing->buf[ringIn]);
     }
     //-------> Accesso concorrente unlock
}
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Invece ci sono situazioni in cui è la soluzione migliore
Può essere. In realtà una coda a me fa pensare direttamente a una
linked list.

 
Non stampava mai la testa della dequeue, ed altre soluzioni alternative 
che avevo provato avevano altri difetti.
Stamattina ho avuto il colpetto di genio ed ho risolto così.
***
void stampa(dequeue *d) {
//Stampa la dequeue, dalla coda fino alla testa.
 int i = d->back;
 if (d->state == empty)
  printf("%s", "Nessun elemento presente.");
 else if (d->back == d->front) //se la dequeue ha un solo elemento...
  printf("%d ", d->items[d->back]);
 else { //se la dequeue ha almeno due elementi...
  do {
   printf("%d ", d->items[i]);
   i = (i + 1) % MaxLung;
  } while (i != d->front);
  printf("%d ", d->items[d->front]);
 }
 putchar('\n');
}
Ciao e grazie per gli input, sempre interessanti, compresi quelli che 
scaturiscono dal dibattito tra voi. 
Bizio.

 puntatori front/back coincidono.
Ciao.
Per amor di precisione, la confusione si ha non quando front e back 
coincidono, bensì quando back == front + 1. 
Nel primo caso, infatti, la coda ha esattamente un elemento.
Scommetterei comunque che Manu lo sapeva già e che è stato solo un 
refuso.
Ciao 
Bizio.

 codice postato dall'OP lo mostri.
Perdonatemi, che vuol dire OP? 
Aggiungo che questa implementazione costituisce un esercizio presente su 
un libro, in un punto in cui non sono ancora state introdotte le 
stutture autoreferenzianti, come le liste concatenate.
Ciao 
Bizio.

 Perdonatemi, che vuol dire OP? 
Original Poster... cioč tu!
E.

 coincidono, bensì quando back == front + 1. 
sì, è vero... Una soluzione alternativa (simile a quella postata da 
brix*) è quella di memorizzare front e numero di elementi.
E.