Stacks, Queues, and Interfaces 3.1 Consider the following interface for stack t that stores elements of type bool /Stack Interface * // typedef* stack t bool stack empty(stackt S) /* 0(1), check if stack empty / /m@requires S != NULL ; @*/s stack t stack new) /*@ensures esult != NULL; @*/ /*@ensures stack_empty( esult); / /* 0(1), create new empty stack void push(stackt S, bool x) /*0(1), add item on top of stack */ /@requires S!-NULL; @/ bool pop(stackt S) /@requires S!NULL; @ /*@requires stack empty (S); @/ Write a client function stack_bottom(stack t S) that returns the bottom ele- ment of the given stack, assuming the stack is not empty. The final stack should be identica to the inal stack. For this task, use only the nterface since, as a client, you do not know how this data structure is implemented. Do not use any stack functions that are not in the interfac inluding specification functions like isstack since these belong to the implementation) /*0(1), remove item from top*/ bool stackbottom (stack t S) //@requires S != NULL; //@requires stack empty (S)