Write a C function popToQueue() that pop (insert) the stack integers into the queue in front of a matching value. Note that the popToQueue() function only uses pop() when removing integers from the stack and only uses enqueue() and dequeue() when adding or removing integers into/from the queue. A new queue is returned.

The function prototype is given as follows:

Queue popToQueue(Queue *q, Stack *s, int value);

A sample input and output session is given below :

1: Insert an integer into the queue and stack;

2: Pop the stack to the queue;

0: Quit;

Please input your choice(1/2/0): 1

Input an integer that you want to insert into the queue and stack:7

The queue is:7

The stack is:7

Please input your choice(1/2/0): 1

Input an integer that you want to insert into the queue and stack:9

The queue is:7 9

The stack is:9 7

Please input your choice(1/2/0): 2

The queue is7 9

The stack is9 7

Enter the integer in the queue that you want to pop the stack to :9

The resulting queue after popping the stack elements is:7 9 7 9

Please input your choice(1/2/0): 2

The queue isEmpty

The stack isEmpty

Please input your choice(1/2/0): 1

Input an integer that you want insert into the queue and stack:5

The queue is:5

The stack is:5

Please input your choice(1/2/0): 1

Input an integer that you want insert into the queue and stack:7

The queue is:5 7

The stack is:7 5

Please input your choice(1/2/0): 1

Input an integer that you want to insert into the queue and stack:8

The queue is:5 7 8

The stack is:8 7 5

Please input your choice(1/2/0): 2

The queue is5 7 8

The stack is8 7 5

Enter the integer in the queue that you want to pop the stack to :7

The resulting queue after popping the stack elements is:5 8 7 5 7 8

Please input your choice(1/2/0): 1

Input an integer that you want to insert into the queue and stack:9

The queue is:9

The stack is:9

Please input your choice(1/2/0): 2

The queue is9

The stack is9

Enter the integer in the queue that you want to pop the stack to :9

The resulting queue after popping the stack elements is:9 9

Please input your choice(1/2/0): 1

Input an integer that you want insert into the queue and stack:8

The queue is:8

The stack is:8

Please input your choice(1/2/0): 2

The queue is8

The stack is8

Enter the integer in the queue that you want to pop the stack to :9

The resulting queue after popping the stack elements is:8

Please input your choice(1/2/0):

Sample Code:

#include

#include

#include

//////////////////////////////////linked list /////////////////////////////////

typedef struct _listnode{

int item;

struct _listnode *next;

} ListNode;

typedef struct _linkedlist{

int size;

ListNode *head;

ListNode *tail;

} LinkedList;

////////////////////////////////// stack///////////////////////////////////////////////////////

typedef struct stack{

LinkedList ll;

} Stack;

//////////////////////////////////// queue ////////////////////////////////////////////////////////

typedef struct _queue{

LinkedList ll;

} Queue;

///////////////////////////////////////////////////////////////////////////////////////////////////

Queue popToQueue(Queue *q, Stack *s, int value);

///////////////////////////////////////////////////////////////////////////////////////////////////

void push(Stack *s, int item);

int pop(Stack *s);

int peek(Stack *s);

int isEmptyStack(Stack *s);

void enqueue(Queue *q, int item);

int dequeue(Queue *q);

int isEmptyQueue(Queue *s);

///////////////////////////////////////////////////////////////////////////////////////////////////

void printList(LinkedList *ll);

ListNode * findNode(LinkedList *ll, int index);

int insertNode(LinkedList *ll, int index, int value);

int removeNode(LinkedList *ll, int index);

void removeAllItems(LinkedList *ll);

///////////////////////////////////////////////////////////////////////////////////////////////////

int main()

{

int c, value;

Queue q;

Stack s;

//initialize the queue

q.ll.head =NULL;

q.ll.size =0;

q.ll.tail=NULL;

//initialize the stack

s.ll.head = NULL;

s.ll.size = 0;

s.ll.tail = NULL;

c =1;

printf("1: Insert an integer into the queue and stack; ");

printf("2: Pop the stack to the queue; ");

printf("0: Quit; ");

while (c != 0)

{

printf("Please input your choice(1/2/0): ");

scanf("%d", &c);

switch (c)

{

case 1:

printf("Input an integer that you want insert into the queue and stack: ");

scanf("%d", &value);

enqueue(&q, value);

push(&s, value);

printf("The queue is: ");

printList(&(q.ll));

printf("The stack is: ");

printList(&(s.ll));

break;

case 2:

printf("The queue is ");

printList(&(q.ll));

printf("The stack is ");

printList(&(s.ll));

if (isEmptyQueue(&q)) break;

printf("Enter the integer in the queue that you want to pop the stack to : ");

scanf("%d", &value);

Queue newQ = popToQueue(&q, &s, value); // You need to code this function

if (!isEmptyQueue(&newQ)) {

printf("The resulting queue after popping the stack elements is: ");

printList(&(newQ.ll));

}

break;

case 0:

removeAllItems(&(q.ll));

break;

default:

printf("Choice unknown; ");

break;

}

}

return 0;

}

///////////////////////////////////////////////////////////////////////////////////////////////////

QueuepopToQueue(Queue *q, Stack *s, int value)

{

/* add your code here */

}

///////////////////////////////////////////////////////////////////////////////////////////////////

void push(Stack *s, int item){

insertNode(&(s->ll), 0, item);

}

int pop(Stack *s){

int item;

if(!isEmptyStack(s)){

item = ((s->ll).head)->item;

removeNode(&(s->ll), 0);

return item;

}

return INT_MIN;

}

int peek(Stack *s){

return ((s->ll).head)->item;

}

int isEmptyStack(Stack *s){

if ((s->ll).size == 0)

return 1;

return 0;

}

void enqueue(Queue *q, int item){

insertNode(&(q->ll), q->ll.size, item);

}

int dequeue(Queue *q){

int item;

item = ((q->ll).head)->item;

removeNode(&(q->ll), 0);

return item;

}

int isEmptyQueue(Queue *q){

if ((q->ll).size == 0)

return 1;

return 0;

}

//////////////////////////////////////////////////////////////////////////////////

void printList(LinkedList *ll){

ListNode *cur;

if (ll == NULL)

return;

cur = ll->head;

if (cur == NULL)

printf("Empty");

while (cur != NULL)

{

printf("%d ", cur->item);

cur = cur->next;

}

printf(" ");

}

ListNode * findNode(LinkedList *ll, int index){

ListNode *temp;

if (ll == NULL || index < 0 || index >= ll->size)

return NULL;

temp = ll->head;

if (temp == NULL || index < 0)

return NULL;

while (index > 0){

temp = temp->next;

if (temp == NULL)

return NULL;

index--;

}

return temp;

}

int insertNode(LinkedList *ll, int index, int value){

ListNode *pre, *cur;

if (ll == NULL || index < 0 || index > ll->size + 1)

return -1;

// If empty list or inserting first node, need to update head pointer

if (ll->head == NULL || index == 0){

cur = ll->head;

ll->head = malloc(sizeof(ListNode));

ll->head->item = value;

ll->head->next = cur;

ll->size++;

return 0;

}

// Find the nodes before and at the target position

// Create a new node and reconnect the links

if ((pre = findNode(ll, index - 1)) != NULL){

cur = pre->next;

pre->next = malloc(sizeof(ListNode));

pre->next->item = value;

pre->next->next = cur;

ll->size++;

return 0;

}

return -1;

}

int removeNode(LinkedList *ll, int index){

ListNode *pre, *cur;

// Highest index we can remove is size-1

if (ll == NULL || index < 0 || index >= ll->size)

return -1;

// If removing first node, need to update head pointer

if (index == 0){

cur = ll->head->next;

free(ll->head);

ll->head = cur;

ll->size--;

return 0;

}

// Find the nodes before and after the target position

// Free the target node and reconnect the links

if ((pre = findNode(ll, index - 1)) != NULL){

if (pre->next == NULL)

return -1;

cur = pre->next;

pre->next = cur->next;

free(cur);

ll->size--;

return 0;

}

return -1;

}

void removeAllItems(LinkedList *ll)

{

if (ll == NULL)

return;

ListNode *cur = ll->head;

ListNode *tmp;

while (cur != NULL){

tmp = cur->next;

free(cur);

cur = tmp;

}

ll->head = NULL;

ll->size = 0;

}

Add code to this function in the sample code.

QueuepopToQueue(Queue *q, Stack *s, int value)

{

/* add your code here */

}