onsider a sequence a of elements a0=1, a1=5, a2=7, a3=8, a4=9, and a5=2.The following operations are performed on a stack S and a queue Q, both of which are initially empty. I: push the elements of a from a0 to a5 in that order into S.II: enqueue the elements of a from a0 to a5 in that order into Q. III: pop an element from S. IV: dequeue an element from Q. V: pop an element from S. VI: dequeue an element from Q. VII: dequeue an element from Q and push the same element into S. VIII: Repeat operation VII three times. IX: pop an element from S. X: pop an element from S. The top element of S after executing the above operations is _______.Question 2Answera.9b.2c.8d.7Clear my choiceCheckQuestion 2

An implementation of a queue Q, using two stacks S1 and S2, is given below:void insert(Q, x) {   push (S1, x);}  void delete(Q){   if(stack-empty(S2)) then      if(stack-empty(S1)) then {          print(“Q is empty”);          return;      }      else while (!(stack-empty(S1))){          x=pop(S1);          push(S2,x);      }   x=pop(S2);}Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?n+m <= x < 2n and 2m <= y <= n+mn+m <= x < 2n and 2m<= y <= 2n2m <= x < 2n and 2m <= y <= n+m2m <= x <2n and 2m <= y <= 2n

What will be the final elements on the queue and stack if the following sequence of operations are executed? Queue q = new Queue(); Stack s = new Stack(); q.push("a"); s.push("b"); q.push("c"); s.push("d"); s.push( q.pop() ); q.push( s.peek() ); q.push( s.pop() );

Stack interleavingGiven a stack of `N` elements(integers), interleave the first half of the stack with the second half reversed using only one other queue. This should be done in-place.Recall that you can only push or pop from a stack, and enqueue or dequeue from a queue.For example,if the stack is `[1, 2, 3, 4, 5]`, it should become `[1, 5, 2, 4, 3]`.If the stack is `[1, 2, 3, 4]`, it should become `[1, 4, 2, 3]`.Hint: Try working backwards from the end state.Instruction: To test your code and to run your custom test cases, provide input as mentioned in the visible sample test cases.Sample Test CasesTest Case 1:Expected Output:Enter·the·elements·of·the·stack·separated·by·space:·1 2 3 4 5Stack:·[1,·2,·3,·4,·5]Stack·after·interleaving·the·first·half·with·the·reversed·second·half:[1,·5,·2,·4,·3]

Suppose that Q is a queue implemented with a circular array A,  initially empty (with size/capacity = 0). You run the following operations in the order given:1. Q.enqueue(7) 2. Q.enqueue(42) 3. Q.enqueue(3) 4. Q.dequeue()5. Q.enqueue(10)6. Q.first()7. Q.enqueue(5)8. Q.enqueue(30)9. Q.enqueue(15)10. Q.dequeue()11. Q.dequeue()12. Q.dequeue()13. Q.dequeue()14. Q.dequeue()Assuming that insertion and deletion in dynamic arrays use the resizing strategy we have seen during the lectures, describe the entries of the array A after performing the above operations, separating each entry by a comma and no space. If an entry is empty, write "None" (case-sensitive). For example, if the array was [1, 2, None, None], then write "1,2,None,None", omitting the double quotes.

Q3(a) Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Implement queue function using these three functions and only one stack.