For such an implementation an array would seem to be a logical choice (rather than a linked-list style of implementation).
If we keep track of the 'back' of the queue it is easy to enqueue:
const int QueueSize = 10; float Queue[QueueSize]; int back = 0; // position to enqueue at int front = -1; // position to dequeue from, -1 when queue is empty // to enqueue items simply put them at position 'back' and increment it, // and as long as back < QueueSize it is ok // enqueue 1.0 Queue[back] = 1.0; back++; // now enqueue 3.1 Queue[back] = 3.1; back++;However, there is a problem: what do we do when we dequeue?
If we want to keep position 0 in the array as the front then we need to shuffle everything forward one position every time we dequeue. This is a slow/cumbersome way of doing things if the array is large and we do a lot of enqueues/dequeues.
We could increment front every time we dequeue, e.g.
// dequeue and print front element cout << Queue[front]; front++;There are some problems though
The typical solution is to 'wrap-around' when back or front hit the end of the array. E.g. every time we increment back we check and see if it has reached QueueSize in the example above, and if so we reset it to 0. Similarly anytime we increment front we check to see if it has reached QueueSize, in which case we reset it to 0.
The example below fills in some of the gaps and special cases:
#include <iostream> using namespace std; // maximum number of values that can be // stored at any given moment const int BufferSize = 4; int main() { // the buffer for storing values float buffer[BufferSize]; // location of current first and last elements in buffer, // both are set to -1 when nothing is in the queue int front = -1; int back = -1; // the number of values currently stored in the queue int bsize = 0; // let the user go for as long as they want, // on each turn they can do any one of: // enqueue an item at the back (if the buffer isn't full) // dequeue the front item (if the buffer isn't empty) // quit char cmd; do { // get the user's command cout << "Enter E to enqueue, D to dequeue, or Q to quit" << endl; cin >> cmd; cmd = toupper(cmd); // (convert to uppercase for simplicity) // handle quit commands if (cmd == 'Q') { cout << "Bye!" << endl; } // handle enqueue commands else if (cmd == 'E') { // make sure the buffer isn't full if (bsize >= BufferSize) { cout << "Cannot enqueue, buffer is full" << endl; } // get the new value from the user // if the queue is empty // then start front and back at 0 // otherwise // increment back, wrap-around if needed // insert the new value // and update the buffer size else { float value; cout << "Enter the new value:" << endl; cin >> value; if (front < 0) { front = 0; back = 0; bsize = 1; buffer[0] = value; } else { back++; if (back >= BufferSize) { back = 0; } buffer[back] = value; bsize++; } cout << "Enqueued value " << value << endl; } } // handle dequeue commands else if (cmd == 'D') { // make sure the buffer isn't empty if (bsize < 1) { cout << "Cannot dequeue, buffer is empty" << endl; } // copy out the front value, // increment front, and wrap-around if needed // decrement the size, // and if size drops to 0 reset front/back to -1 else { cout << "Dequeued value " << buffer[front] << endl; front++; if (front >= BufferSize) { front = 0; } bsize--; if (bsize <= 0) { front = -1; back = -1; } } } // handle invalid commands else { cout << "Invalid command entered" << endl; } } while (cmd != 'Q'); } |