queueops.c

Trees are natural structures for representing certain kinds of hierarchical data. A (rooted) tree co

#include <stdio.h>
#include "Queue.h"

int emptyq( Queue Q ) { return Q==NULL ? 1 : 0; }

void addq(QueueElementType E, Queue *Q /*byref*/)
/* Add E as the last element of Q which is changed as a side-effect */
 { Queue P;
   P = (Queue)malloc(sizeof(Cell));              /*L*/
   QueueElementMove(E, &(P->elt));               /*.*/
   if( emptyq(*Q) )                              /*A*/
      P->tl = P;                                 /*l*/
   else                                          /*l*/
    { P->tl = (*Q)->tl; /*front*/                /*i*/
      (*Q)->tl = P;     /*new tail*/             /*s*/
    }                                            /*o*/
   *Q = P;                                       /*n*/
 }/*addq*/                                       /*(c)*/

void popq(QueueElementType *E /*byref*/, Queue *Q /*byref*/)
/* pre: not emptyq(*Q) */
/* Return last element of Q as E, and delete it from Q */
 { Queue P;
   P = (*Q)->tl; /* front of Q */
   QueueElementMove(P->elt, E);
   if( P == (*Q) )/* Q==<E> */
      *Q = NULL;
   else/* Q=<E, e2, ..., en> */
      (*Q)->tl = P->tl;
   P->tl = NULL; free(P);
 }/*popq*/

/* Queue by Circular List; Operations as Side-Effects */