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 | |
| #include | |
| #include | |
| #include | |
| // 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
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
