#include <iostream> #include <vector> #include \"Queue.h\" using namespace std;

Question

#include <iostream>
#include <vector>
#include "Queue.h"

using namespace std;

long k = 10;

long f (long x){
    return x % k;
}

int main() {
  
    // Declare a vector of Queue pointers
    vector<Queue*> hashtable;
  
    // Initialize the vector with k empty Queues
    for (long i = 0; i < k; i++) {
        hashtable.push_back(new Queue());
    }
  
    // This is the value I want to insert
    long value = 234;
  
    // Run it through the hash function to determine
    // to which queue we need to push it
    long index = f(value);
  
    // Push value to the index-th Queue
    hashtable[index]->push(value);
  
    // One more time
    value = 23;
  
    index = f(value);
    hashtable[index]->push(value);
  
    // One more time
    value = 23453;
  
    index = f(value);
    hashtable[index]->push(value);
  
  
    // Let's do some searching
  
    // This is what I am searching for
    value = 7;
  
    // Which queue should I be looking at
    index = f(value);
  
    // Look for it in the queue pointed to by index
    cout << hashtable[index]->find(value) << endl << endl;
  
    // Print contents of hash table
    for (long i = 0; i < k; i++) {
        Queue* current = hashtable[i];
      
        cout << i << ": ";
      
        current->print();
        cout << endl;
    }
  
    for (long i = 0; i < k; i++) {
        delete hashtable[i];
    }
  
    return 0;
}

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#ifndef Queue_h
#define Queue_h

#include <iostream>

struct Link {
    long data;
    Link* next;
  
    Link(){
        data = 0;
        next = NULL;
    }
  
    Link (long d){
        data = d;
        next = NULL;
    }
};

struct Queue {
    Link* front;
    Link* back;
  
    Queue (){
        front = NULL;
        back = NULL;
    }
  
    long peek () {
        return front->data;
    }
  
    void push(long value){
        if (isEmpty()){
            front = new Link(value);
            back = front;
        }
        else {
            back->next = new Link(value);
            back = back->next;
        }
    }
  
    bool find (long value){
        // Provide your code here

    }
  
    bool isEmpty(){
        return (front == NULL);
    }
  
    long pop(){
        long val = front->data;
      
        Link* oldFront = front;
        front = front->next;
      
        delete oldFront;
      
        return val;
    }
  
    void print() {
        // Provide your code here

    }
  
    ~Queue(){
        // Provide your code here

    }
};

#endif

the Queue struct needs 3 more functions to be implemented. A find function, which tells us it a given value appears in the queue, without being destructive. A function called print, which prints out the contents of the queue, again without being destructive. Finally, there is a need for a destructor. To implement it, you can just keep popping elements off the queue until there are no elements left.

Explanation / Answer

#include <stdio.h>
#include <iostream>
#include <vector>
#include "Queue.h"
using namespace std;
long k = 10;
long f (long x){
return x % k;
}
int main() {
  
// Declare a vector of Queue pointers
vector<Queue*> hashtable;
  
// Initialize the vector with k empty Queues
for (long i = 0; i < k; i++) {
hashtable.push_back(new Queue());
}
  
// This is the value I want to insert
long value = 234;
  
// Run it through the hash function to determine
// to which queue we need to push it
long index = f(value);
  
// Push value to the index-th Queue
hashtable[index]->push(value);
  
// One more time
value = 23;
  
index = f(value);
hashtable[index]->push(value);
  
// One more time
value = 23453;
  
index = f(value);
hashtable[index]->push(value);
  
  
// Let's do some searching
  
// This is what I am searching for
value = 7;
  
// Which queue should I be looking at
index = f(value);
  
// Look for it in the queue pointed to by index
cout << hashtable[index]->find(value) << endl << endl;
  
// Print contents of hash table
for (long i = 0; i < k; i++) {
Queue* current = hashtable[i];
  
cout << i << ": ";
  
current->print();
cout << endl;
}
  
for (long i = 0; i < k; i++) {
delete hashtable[i];
}
  
return 0;
}
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#ifndef Queue_h
#define Queue_h
#include <iostream>
struct Link {
long data;
Link* next;
  
Link(){
data = 0;
next = NULL;
}
  
Link (long d){
data = d;
next = NULL;
}
};
struct Queue {
Link* front;
Link* back;
Link* temp;
Queue (){
front = NULL;
back = NULL;
}
  
long peek () {
return front->data;
}
  
void push(long value){
if (isEmpty()){
front = new Link(value);
back = front;
}
else {
back->next = new Link(value);
back = back->next;
}
}
  
bool find (long value){
int flag = 0;
while(front != NULL)
{
if(front->data == value)
{
flag =1;
break;
}   
front = front -> next;
}
if(flag == 1)
cout<<"Given value appears in the queue";
else
cout<<"Given value is not present in the queue";
}
  
bool isEmpty(){
return (front == NULL);
}
  
long pop(){
long val = front->data;
  
Link* oldFront = front;
front = front->next;
  
delete oldFront;
  
return val;
}
  
void print() {
temp = front;
cout<<"The values in the queue are ";
while(front != NULL)
{
cout<<temp->data<<" ";   
front = front -> next;
}
}
  
~Queue(){
temp = front;
while(front != NULL)
{
cout<<pop();
front = front -> next;
}
}
};
#endif

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.