Merging Queues and Hash Tables

[jheard901]

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:

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
};

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;
  }
}

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).

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

void ThemePark::AddName(const string& value)
{
  Hash(value);
  Store(value);
  cout << value << " successfully added to Ride " << hashValue+1;
}

[o3hC5Di1]

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:

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.

Does that answer your question?

All the best,
NwN