Question
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
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 */
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started