In the lecture you learned about the data structures stacks and queues. The aim of this task is to deepen your

understanding of both data structures.

$($a$)$ Let $Q$ be a queue implemented on an $($initially empty$)$ array of size $5.$ Represent the array after each of the

following operations: enqueue $(Q,8)$; enqueue $(Q,7)$; enqueue $(Q,6)$; dequeue $(Q)$; dequeue $(Q)$; enqueue $(Q,7)$;

enqueue$($Q$\mathrm{.}2)$: dequeue$($

Q$)($b$)$ Let $S$ be a stack. which is implemented on an Arrav of size $6$ and initially contains the following letters:

$R^{\text{'}},E^{\text{'}},G^{\text{'}},{?}^{\text{'}\text{'}},L^{\text{'}},E^{\text{'}}.$ Represent the array after each of the following operations: pop$($S$)$; pop$($S$)$; push$($S$,\text{'}$X$)$

pop$(S)$;pop$(S)$;push$(S,E^{\text{'}})$; push$($S$,$ N$).$

$($c$)$ Consider a data structure DoubleStack, which contains two stacks. This should be implemented here in an

$n$ array of size EN$.$ Neither stack should overflow as long as the total number of elements in both

stacks is at most $n.$ To do this, implement the methods new, push$1,$ push$2,$ popl, pop$2.$ Both push

and pop methods should run in constant time, i$.$e$.O(1).$ The pop methods are supposed to return an

error symbol $L$ if the associated stack is empty. Justify your design.

$($d$)$ Design an algorithm that inverts a stack, i$.$e$.$ reverses the order of the entries. You may only use stacks

$($in addition to the input stack$)$ as additional memory and no other data structures. Furthermore

$,$ the algorithm should not have a return value, but should perform the reversal in the passed

stack. Do not perform unnecessary copy operations. Justify your design

$($e$)$ Design an algorithm that inverts a stack, i$.$e$.$ reverses the order of the entries. You may only use

queues $($in addition to the input stack$)$ as additional memory and no other data structures.

Furthermore, the algorithm should not have a return value, but should perform the reversal in

the passed stack. Do not perform unnecessary copy operations. Justify your design.