PDA

View Full Version : c++ queues using circular arrays?



Orphious
09-26-01, 10:09 PM
I am having problems with an option to display the queue. The logic of how to display the queue according on where in the array the values myFront and myBack are. Like this:
array[0] = 10
array[1] = 20
array[2] = 30
array[3] = 40
array[4] = 50
for example, say I started with a queue like that. then the front two are removed and another is added.
It then has become 30 40 50 60 where 60 is located on array[0]

myFront is on array[2] which is 30 and myBack is array[1].

Now for a question finally, how can you display the queue(in a loop?) so that the output will be from array[2]....to [4] and then back to [0]? Did that make any sense?

thanks very much!!

Stu
09-27-01, 06:37 PM
I wouldn't use an array, not easy enough. I'd use a queue class template (if you just need a queue--without printing all elements) or a vector class template (if you need to print all the elements--a vector, stated simply, is a resizable array)--both of which are in the Standard Template Library (STL).

Looking at the queue class template, you could do something like this:



#include <iostream>
#include <queue>

int main(int argc, char *argv[]){

// Declare a queue...
queue<int> myQueue;

// Initialize the queue...
myQueue.push(10);
myQueue.push(20);
myQueue.push(30);
myQueue.push(40);
myQueue.push(50);

// Remove front two, 10 & 20; with print...
for (int i = 0; i < 2; i++){

// Print item...
cout << "Removing " << myQueue.front() << '\n';

// Remove item...
myQueue.pop();

} // End for

// Insert new item at the end of the queue...
myQueue.push(60);

// Print the front and back elements...
cout << "Next item in queue: " << myQueue.front() << '\n'
<< "Last item in queue: " << myQueue.back() << '\n'
<< ends;

} // End main()



Looking at the vector class template version:



#include <iostream>
#include <vector>
#include <iterator>

void print_queue(vector<int> &);
void print_queue(vector<int> & myVec){

// Declare iterator...
vector<int>::iterator iter = myVec.begin();

// Loop through and print all values...
for (; iter != myVec.end(); iter++)
cout << *iter << '\n';

cout << ends;

} // End print_queue()

int main(int argc, char *argv[]){

// Declare a vector...
vector<int> myQueue;

// Initialize the vector...
myQueue.push_back(10);
myQueue.push_back(20);
myQueue.push_back(30);
myQueue.push_back(40);
myQueue.push_back(50);

// Print the queue...
print_queue(myQueue);

// Remove front two, 10 & 20; with print...
for (int i = 0; i < 2; i++){

// Print item...
cout << "Removing " << myQueue[0] << '\n';

// Remove item...
myQueue.erase(myQueue.begin());

} // End for

// Insert new item at the end of the vector...
myQueue.push_back(60);

// Print the queue...
print_queue(myQueue);

} // End main()



However, if you insist on using an array as your storage. You could wrap it in a class. Like this:




#include <iostream>

class ArrayIntQueue {

int _array[5]; // Holds data
int _count; // Holds count of data items

public:

ArrayIntQueue(){

// Initialize the array...
for(int i = 0; i < 5; i++)
this->_array[i] = 0;

// Set the count to 0; no items in array...
this->_count = 0;

} // End ArrayIntQueue::ArrayIntQueue()

void push(int value){

// Ignore data that exceeds the array bounds;
// normally we'd throw an error

// Insert the value to the end of the array,
// and increase count by one...
if( this->_count < 5 )
this->_array[this->_count++] = value;

} // End ArrayIntQueue::push()

int pop(int pos){

int temp = -1;

// pos is less than the element count...
if(pos < this->_count){

// Get value to return...
temp = this->_array[pos];

// Shift data to one cell below its
// current position...
for(; pos < this->_count; pos++){

this->_array[pos] = this->_array[pos + 1];

} // End for

// Set count to one less item...
this->_count--;

} // End if

return temp;

} // End ArrayIntQueue::pop(int)

int pop(){

// Remove the first item...
return this->pop(0);

} // End ArrayIntQueue::pop()

void print(){

// Loop through and print each item...
for(int i = 0; i < this->_count; i++)
cout << this->_array[i] << '\n';

cout << ends;

} // End ArrayIntQueue::print()

int count(){

// Return count...
return this->_count;

} // End ArrayIntQueue::count()

}; // End class ArrayIntQueue


int main(int argc, char *argv[]){

ArrayIntQueue myQueue;

// Initialize the queue...
myQueue.push(10);
myQueue.push(20);
myQueue.push(30);
myQueue.push(40);
myQueue.push(50);

// Print the queue...
myQueue.print();

// Print count...
cout << "There are " << myQueue.count() << " items in the queue."
<< '\n' << ends;

// Remove and print two items; 10 & 20...
cout << "Removing " << myQueue.pop() << '\n';
cout << "Removing " << myQueue.pop(0) << '\n';

// Insert new item at the end of the queue...
myQueue.push(60);

// Print the queue...
myQueue.print();

// Print count...
cout << "There are " << myQueue.count() << " items in the queue."
<< '\n' << ends;

} // End main()



See why I like the STL versions better?!

Orphious
09-28-01, 09:07 AM
That does look easier. Thanks once again Stu