Write a function isSimilar that takes a Queue and a Stack as parameters (contain
ID: 3708521 • Letter: W
Question
Write a function isSimilar that takes a Queue and a Stack as parameters (containing the same type of elements) and returns true if all the elements of stack is contained in the queue. The order of elements does not matter. For example, the following would return true if passed as parameters to your method:
queue: front [1, 9, 3, 4, 5] rear
stack: bottom [4, 5, 1, 9, 3] top
The following parameters would return false, because the element 6 from the stack is not contained in the queue and the element 3 from the queue is not contained in the stack:
queue: front [1,2 ,3 ,7 ,4 ] rear
stack: bottom [6,1 ,2 ,4 ,7 ] top
You may use stack or queue as auxiliary storage. Assumptions: all valid operations for stack and queue are availableitems contained in both structure are not repeated.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct element {
int data;
struct element *next;
};
struct element *stack_head = NULL;
struct element *stack_top = NULL;
struct element *queue_front = NULL;
void insert_element(int data)
{
struct element *cur = NULL;
/* Insert element in Stack */
cur = calloc(1, sizeof(struct element));
cur->data = data;
cur->next = NULL;
if (!stack_head) {
stack_head = cur;
stack_top = cur;
} else {
stack_top->next = cur;
stack_top = cur;
}
/* Insert element in Queue */
cur = calloc(1, sizeof(struct element));
cur->data = data;
cur->next = queue_front;
queue_front = cur;
}
void print_stack()
{
struct element *cur = stack_head;
while (cur) {
printf("%d ", cur->data);
cur = cur->next;
}
}
void print_queue()
{
struct element *cur = queue_front;
while (cur) {
printf("%d ", cur->data);
cur = cur->next;
}
}
void clean_up()
{
struct element *cur = NULL;
struct element *next = NULL;
/* Cleanup Stack */
cur = stack_head;
while (cur) {
next = cur->next;
free(cur);
cur = next;
}
/* Cleanup Queue */
cur = queue_front;
while (cur) {
next = cur->next;
free(cur);
cur = next;
}
}
int isSimilar(struct element *stack_head, struct element *queue_front)
{
struct element *cur_stack = stack_head;
struct element *cur_queue = NULL;
while (cur_stack) {
/*
* Every time cur_queue is initilaized to queue_front
* to compare each stack element with all queue elements
*/
cur_queue = queue_front;
while (cur_queue) {
if (cur_stack->data == cur_queue->data)
break;
cur_queue = cur_queue->next;
}
/*
* Returning false(0) because queue is completely
* traversed but element didn't matched
*/
if (!cur_queue)
return 0;
cur_stack = cur_stack->next;
}
/*
* If cur_stack is NULL at this point means it completed
* traversing all the stack elements and each element
* in stack is present in queue, so we are returning true(1)
*/
return 1;
}
int main()
{
struct element *stack = NULL;
struct element *queue = NULL;
insert_element(1);
insert_element(2);
insert_element(3);
insert_element(4);
insert_element(5);
insert_element(6);
insert_element(7);
/* This is made to check if the stack and queue are not similar */
/* Comment this line and check if the stack and queue are similar */
queue_front->data = 39;
printf("Stack Elements are : ");
print_stack();
printf(" ");
printf("Queue Elements are : ");
print_queue();
printf(" ");
if (isSimilar(stack_head, queue_front))
printf("Stack and Queue are similar ");
else
printf("Stack and Queue are not similar ");
clean_up();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.