Data Structure

Suggest an implementation of a sorted stack. That is, write modified push() method so that the elements are always ordered (the largest item appearing at top). Without loss of generality, you can assume integer elements. Also you can assume the support of pop(), peek(), isEmpty() and isFull() methods. However, you are not allowed to use anything other than stacks. Indicate the big-O complexity of your push() methods.

Is it possible to implement a simple Stack data structure using simple Queue (one or more) structure? If no, explain why it is not possible. If yes, suggest how the two stack operations (push() and pop()) would be implemented using standard queue operations (enqueue() and dequeue()). Also indicate whether the big-oh time for push() and pop() would change. If they change, explain the new runtime complexities of the operations. [7 points]

Suppose you have a stack S containing N distinct elements and a simple queue Q that is initially empty. Describe how you can use Q to scan S to see if it contains a certain element x, with the additional constraint that your algorithm must not violate the integrity of the stack (that is, the elements should remain in their original order after the scan is over). You may not use an extra array or other storage. Only S, Q, and a constant number of reference variables are allowed. What is the runtime complexity of your algorithm?