CS 201 - 9/15/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;


         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 */

       
              /* 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 */


              /* 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 */
    

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