Question: Program Doubly-linked queue in C #include // stardard input/output library #include // standard boolean library: bool, true, false #include // library that contains malloc, rand,

Program Doubly-linked queue in C

#include // stardard input/output library
#include // standard boolean library: bool, true, false
#include // library that contains malloc, rand, and srand
#include // time functions
// https://www.tutorialspoint.com/c_standard_library/
#define MAXMAGNITUDE 100 // the biggest number to be inserted in the queue
#define HOWMANY 10 // how many numbers to be inserted in the queue
/*
* queue
* +--------+--------+
* | tail_p | head_p +----------------------------------------+
* +--+-----*--------+ |
* | |
* V V
* +--------+------+---------+ +--------+------+---------+ +--------+------+---------+
* | left_p | data | right_p +->| left_p | data | right_p +->| left_p | data | right_p +->NULL
* | | | |<-+ | | |<-+ | | |
* +--+-----+------+---------+ +--------+------+---------+ +--------+------+---------+
* | node node node
* V
* NULL
*/
//---------------------------- NODE ----------------------------
// doubly linked list node
typedef struct nd {
int data;
struct nd* left_p;
struct nd* right_p;
} node_t;
// create new node with value d and NULL left & right pointers
node_t* newNode (int d) {
node_t* n_p = NULL; // temp pointer to hold new node
n_p = (node_t*)malloc(sizeof(node_t)); // create new node
if (n_p != NULL) {
n_p->data = d; // put data in node
n_p->left_p = NULL;
n_p->right_p = NULL;
}
return n_p;
};
// free the node pointed to by n_p
// fragile assumption: this function does not free up nodes pointed to by left/right pointers
void freeNode (node_t* n_p) {
if (n_p != NULL) {
free(n_p);
}
return;
};
//---------------------------- QUEUE ----------------------------
// a queue - combining a head and a tail pointer
typedef struct q {
node_t* head_p;
node_t* tail_p;
} queue_t;
// create new empty queue (head and tail are set to NULL)
queue_t* newQueue() {
queue_t* q_p; // temp pointer to hold newly created queue
// ***** INSERT YOUR CODE HERE *****
return q_p;
};
// is the queue empty?
bool isEmpty(queue_t* q_p) {
bool b = true; // temporary bool to hold return value - initalize to default value
// ***** INSERT YOUR CODE HERE *****
return b;
};
// function to add a new node with data d to tail of the queue
void enqueue(queue_t* q_p, int d) {
node_t* n_p = NULL; // temp node pointer
if (q_p != NULL) {
if (isEmpty(q_p)) {
// queue is empty so insertion is easy
// ***** INSERT YOUR CODE HERE *****
} else {
// queue is not empty
// ***** INSERT YOUR CODE HERE *****
}
}
return;
};
// function to take the node off the head of the queue and return its value
int dequeue(queue_t* q_p) {
int t = -9999; // temp int to hold return val with arbitrary error value of -9999
node_t* n_p = NULL; // temp node poitner
if (q_p != NULL) {
n_p = q_p->head_p; // get a pointer to the head of the queue
if (n_p != NULL) {
t = n_p->data; // get the value of data in the head of the queue
if (q_p->head_p == q_p->tail_p) {
// only one node in the queue, clear queue head and tail
// ***** INSERT YOUR CODE HERE *****
} else {
// mulitple nodes in queue, clean up head pointer and new head of queue
// ***** INSERT YOUR CODE HERE *****
}
freeNode(n_p); // free up the node that was dequeued
}
}
return t;
};
// if queue is not empty, then clean it out -- then free the queue struct
void freeQueue(queue_t* q_p) {
if (q_p != NULL) {
// make sure the queue is empty
while (!isEmpty(q_p)) {
dequeue(q_p);
}
// free up the queue itself
free(q_p);
}
return;
};
queue_t* q1_p;
queue_t* q2_p;
int i; // loop variable
int t; // temporary integer
// create a random integer between 1 and n
int getRandom(int n) {
return ((rand() % n) + 1);
}
int main () {
// create two queues
queue_t* q1_p = newQueue();
queue_t* q2_p = newQueue();
// get random number seed
srand((unsigned)time(NULL));
for (i=0; i
t = getRandom(MAXMAGNITUDE);
printf("enqueue[1] %d ", t);
enqueue(q1_p, t);
t = getRandom(MAXMAGNITUDE);
printf("enqueue[2] %d ", t);
enqueue(q2_p, t);
}
printf(" ");
printf("dequeue[1]: ");
while (!isEmpty(q1_p)) {
printf("%d ", dequeue(q1_p));
}
printf(" ");
printf("dequeue[2]: ");
while (!isEmpty(q2_p)) {
printf("%d ", dequeue(q2_p));
}
printf(" ");
freeQueue(q1_p);
freeQueue(q2_p);
return 0;
}

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!