### Merging Queues and Hash Tables

I am stuck on how to do this without using vectors. Is it possible to create a queue for each entry of a hash table using just arrays? Or would it be necessary to implement the queues as a linked list for each hash table entry?

EDIT: I figured a solution out for this. Using an array of structs I can store both the hash table and queue together.

This is what I have figured so far:

 ``1234567891011121314151617181920212223`` ``````class ThemePark { private: int front; //beginning of queue int rear; //end of queue int maxQue; string* queue; int hashValue; int hashSize; int MAX_SIZE; //max number of rides int MAX_SIZE_QUEUE; //max size of queue string location[7]; //represents the rides public: ThemePark(); ~ThemePark(); bool IsFull() const; //checks if queue is full bool Empty() const { return rear == front; } //checks if queue is empty void Store(const string&); //stores values in a specific ride void Hash(const string&); //hash function void Enqueue(const string&); //add to rear of queue void Dequeue(const string&); //remove front of queue void AddName(const string&); //adds a person to a queue };``````

 ``12345678910111213141516171819202122232425262728293031`` ``````ThemePark::ThemePark() //constructor { MAX_SIZE = 7; MAX_SIZE_QUEUE = 3; //max queue size is 3 hashValue = 0; hashSize = MAX_SIZE; //max number of rides is 7 maxQue = MAX_SIZE_QUEUE + 1; front = maxQue - 1; rear = maxQue - 1; queue = new string[maxQue]; } ThemePark::~ThemePark() //destructor { delete [] queue; } bool ThemePark::IsFull() const { return ((rear + 1) % MAX_SIZE_QUEUE == front); } void ThemePark::Hash(const string& value) { int strLength = value.length(); //length of the string hashValue = 0; for(unsigned int index = 0; index < strLength; index++) { hashValue = (hashValue * 31) + value[index]; hashValue %= hashSize; } }``````

 ``123456789101112131415161718192021`` ``````void ThemePark::Enqueue(const string& value) { if(IsFull()) { cout << "\nThis queue is full.\n"; } else { rear = (rear + 1) % maxQue; queue[rear] = value; } } void ThemePark::Dequeue(const string& value) { if(Empty()) { cout << "\nThis queue is empty.\n"; } else { front = (front + 1) % maxQue; queue[front] = value; } }``````

This is where I am having trouble figuring out how to combine the queue and hash table. I only have one queue with a max size of 3, but I need a queue for each hash entry(total of 7).

 ``12345`` ``````void ThemePark::Store(const string& value) { Enqueue(value); location[hashValue] = queue; //stores the value in one of the 7 rides }``````

 ``123456`` ``````void ThemePark::AddName(const string& value) { Hash(value); Store(value); cout << value << " successfully added to Ride " << hashValue+1; }``````
Last edited on
Hi there,

It sounds a lot like you're trying to reinvent std::unordered_map, but I'm assuming this is an assignment and you aren't allowed to use STL containers?

What I would suggest is that you separate hashtable, queue and themepark into separate classes, because they each fulfil a distinct function. A quick mock up:

 ``1234567891011121314151617`` ``````struct queue { //your queue implementation }; struct hashtable { queue* table = new queue[MAX_TABLE_SIZE]; //hashing implementation }; struct themepark { hashtable attraction_lines; //themepark funcitonalities };``````

So your hashtable is basically an array of queue-objects. That's possible because you convert the name of an attraction to a number.