Question
JGrasp or Eclipse I will accept either please help In this assignment, your task is to implement a Java program to check whether a given
JGrasp or Eclipse I will accept either please help In this assignment, your task is to implement a Java program to check whether a given output (sequence of numbers) is a stack permutation. You will implement the stack and queue interfaces as described in Queue.java and Stack.java in the first references source code. You can implement these Interfaces using the ArrayQueue.java and ArrayStack.java. You can also use LinkedQueue.java and LinkedStack.java to implement the interfaces. As another option, you can come up with your own implementation of queue and stack. You are not allowed to use the default stack and queue implementations available in Java. Inputs and Outputs of the program The input to your program will be the length of the sequence (n), followed by the output sequence. For example, your sequence can be: 5 1 2 5 4 3 This means that the length of the sequence (n) is 5 and you should check if the remaining numbers are a stack permutation of input queue 1,2,3,4,5 or not (In this case, the output sequence is a stack permutation and you will print: The input sequence is a stack permutation!). As another example, if you get: 6 2 1 3 4 6 5 This means that the length of the sequence (n) is 6 and you should check if the remaining numbers are a stack permutation of input queue 1,2,3,4,5,6 or not (In this case, the entered sequence (output queue) is a stack permutation again and you will print: The entered sequence is a stack permutation!). Stack Permutation Check Algorithm Below is the step by step algorithm to check if a sequence is stack permutation or not: 1-Continuously dequeue elements from the input queue and check if it is equal to the top of output queue or not, if it is not equal to the first of output queue then we will push the element to stack. 2-Once we find an element in input queue such the first of input queue is equal to first of output queue, we will dequeue a single element from both input and output queues, and compare the top of stack and first of output queue now. If top of stack and first of output queue are equal then pop/dequeue element from both stack and output queue. If not equal, go to step 1. 3-Repeat above two steps until the input queue becomes empty. At the end, if the both of output queue and stack are empty then the entered sequence (output queue) is permutable, otherwise not. Get all elements from input (the first element (n) is the number of elements) enqueue all the elements (not the number of elements (n)!) in outputQueue. enqueue the inputQueue with the numbers of 1 to n. while (!inputQueue.IsEmpty() { inputFirst = inputQueue.dequeue() If (inputFirst == outputQueue.first()){ outputQueue.dequeue() while (!tempStack.IsEmpty()){ if (tempStack.top() == outputQueue.first()) { tempStack.pop() outputQueue.dequeue() } else break } } else tempStack.push(inputFirst) } if (outputQueue.IsEmpty()&&tempStack.IsEmpty()) print The entered sequence is a stack permutation!; else print The entered sequence is not a stack permutation!; }
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