//===================================== // shrink //===================================== // Halve the physical size of the // array for queue q. //===================================== void shrink(Queue& q) { int n = q.physicalSize; //-------------------------------------------- // Copy the old array into a new array. Move // the front to index 0 in the new array. //-------------------------------------------- int newsize = n/2; int* newA = new int[newsize]; for(int i = 0; i < q.load; i++) { newA[i] = q.contents[(q.front + i) % n]; } //-------------------------------------------- // Install the new array. //-------------------------------------------- delete [] q.contents; q.contents = newA; q.front = 0; q.physicalSize = newsize; } //===================================== // removeFirst //===================================== // Remove and return the first item in // queue q. If q is empty, return -1 // and do not modify q. //===================================== void removeFirst(Queue& q) { if(isEmpty(q)) { return -1; } else { int result = q.contents[q.front]; if(4*q.load <= q.physicalSize) { shrink(q); } q.front = (q.front + 1) % q.physicalSize; q.load--; return result; } }