CS 201 - 9/16/14

Chapter 6 - Queues as a data structure

  First in First Out

   Operations - enque (add to the end)
              - deque (remove from the front)
              - front (access the first element)
              - isEmpty
              - isFull
              - clear

   Queues can be supported by an array 
        (via a "circular array")

   a quick look at the array implementation:

   typedef struct queueStruct
   {
      int que [100];
      int backPos;    /* initialize to 0 */
      int frontPos;   /* initialize to 0 */
      int size;       /* size of the array */
   } queue;

         initialize code (in main)

         queue q1;
         q1.backPos = 0;
         q1.frontPos = 0;
         q1.size = 100;


         enque 8 different values
            values are stored in locations 0 - 7
 
            call to enque from main()
                enque (&q1, val);
      
         void enque ( queue* q, int val)
           {
              /* check if array is full */
              if ( isFull ( q ) == TRUE )
                 {
                  printf ("Error: Queue is empty\n");
                  return;
                 }

       
              /* add the value to the queue */
              q->que[q->backPos] = val;
              q->backPos = q->backPos + 1;
              /* check if backPos needs to wrap around */
              if (q->backPos >= q->size)
                   q->backPos = 0;

           }




      now assume we deque 3 of those values 
        the que is using positions 3 - 7

         the call from main()
             deque (&q1);

         void deque ( queue* q )
           {
              /* check if queue is empty */
              if ( isEmpty ( q ) == TRUE )
                 {
                  printf ("Error: Queue is empty\n");
                  return;
                 }


              /* remove the value from the array */
              q->frontPos = 
                   (q->frontPos + 1) % q->size;

          }


     to return the value at the front of the queue

         the call from main() would be:

               val = front (&q1);
 

           int front (queue* q)
             {
              /* check that the queue is not empty */
              if ( isEmpty ( q ) == TRUE )
                 {
                  printf ("Error: Queue is empty\n");
                  return -9999;
                 }

              /* return the value at the front */
              return ( q->que [q->frontPos] );
             }
     

      Code for isEmpty 
        call from main()
             if ( isEmpty(&q1) == TRUE )

        int isEmpty (queue* q)
            {
              if (q->backPos == q->frontPos )
                  return TRUE;
              else 
                  return FALSE;
            }


   Code for isFull (based on checking the values
       of backPos and frontPos)  which means the
       array of size N is "full" when it stores
       N-1 values.

        call from main()

             if (isFull( &q1 ) == TRUE) 

         int isFull (queue* q)
           {
             if ((q->backPos+1)%q->size == q->frontPos )
                  return TRUE;
              else 
                  return FALSE;
            }


Implementation 2 which has a array that grows when full


   typedef struct queueStruct
   {
      int* que;       /* address of a dynamic array */
      int backPos;    /* initialize to 0 */
      int frontPos;   /* initialize to 0 */
      int size;       /* size of the array */
   } queue;

The only code that needs to be modified from the
  static array version is the initialization code
  and the enque() code

         initialize code (in main)

         queue q1;
         q1.backPos = 0;
         q1.frontPos = 0;
         q1.size = 10; 
         q1.que = (int*) malloc ( sizeof(int) * q1.size);


         enque 8 different values
            values are stored in locations 0 - 7
 
            call to enque from main()
                enque (&q1, val);
      
         void enque ( queue* q, int val)
           {
              /* check if array is full */
              if ( isFull ( q ) == TRUE )
                 {
                  /* code to grow the array */

                 }

       
              /* add the value to the queue */
              q->que[q->backPos] = val;
              q->backPos = q->backPos + 1;
              /* check if backPos needs to wrap around */
              if (q->backPos >= q->size)
                   q->backPos = 0;

           }