A queue may be implemented using an array of records by first declaring
typedef struct
{
whatever info;
}queuerecord;
typedef struct
{
queuerecord queuearray [LIMIT];
int front, rear;
}queue;
queue q;
As with stacks, overflow and underflow should be checked in a general implementation. A typical queue situation is depicted in Figure 4.10(a) for the array implementation. Figure 4.10(b) shows the situation after 18, 32, and 15 have been removed and 17 and 20 have been inserted.
Storage for insertion of more records is available at the top of the queuearray, but not at the bottom. To ensure that all the relocated storage for queue is used before overflow occurs, programs "wrap around." That is, the queue is implemented so that the queuearray is viewed as a circle of records, with 0 following the LIMIT, 7. Front is used to point to the entry at the front of the queue, and rear is used to point to the array location in which the next
(a) Initial Configuration
(b) After Three Records Are Removed and Two Records Are Inserted
Figure 4.10 Typical Queue Configuration for an Array Implementation
inserted record is to be placed. As entries are inserted, rear moves down until it "falls off" the array, then it must be "wrapped around." As entries are deleted, front moves down until it "falls off" the array, then it must "wrap around."
The insertion operation may then be implemented as follows:
Setqueue must set front and rear to minus one (-1). Empty will return the value true when front = -1, and false otherwise. The removal of a record can be implemented by a function remove, which returns in value the record that was deleted from the queue.
insert(pnewrecord,pq)
/* Inserts newrecord at the rear of queue q */
queuerecord *pnewrecord;
queue *pq;
{if ((*pq).front == -1)
{(*pq).front = 0;
(*pq).queuearray[0].info = (*pnewrecord).info;
(*pq).rear = 1;
}
else
if((*pq).rear == (*pq).front)
printf("\n overflow \n");else
{if((*pq).rear <= (LIMIT - 1))
{(*pq).queuearray[(*pq).rear].info =
(*pnewrecord).info;
(*pq).rear = (*pq).rear + 1;
}
else
{if((*pq).front == 0)
printf("\n overflow \n");else
{4 there is room to wrap around, so the new entry is inserted at the start of the array and rear set to the next location
(*pq).queuearray[0].info =
(*pnewrecord).info;
(*pq).rear = 1;
}
}
}
}
remove (pq, pvalue)
/* Deletes the front entry from
queue q and copies its contents
into value
*/
queue *pq;
queuerecord *pvalue;
{if(empty(pq))
printf("\n underflow \n");else
{(*pvalue).info = (*pq).queuearray
[(*pq).front].info;
(*pq).front = (*pq).front + 1;
if((*pq).front == (*pq).rear)
2 if queue is empty, then reinitialize it
setqueue(pq);
if((*pq).front > (LIMIT - 1))
(*pq).front = 0;
}
}