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; }