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