Stacks,Queues and Linked lists

1)Explain how to implement two stacks in one array A[1,...,n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The run time of PUSH and POP is O(1).

2)Explain how to implement a queue using two stacks. Analyse the running time of the queue operations.

3)Explain how to implement a stack using two queues. Analyse the running time of the stack operations.

4)Write four O(1)-time procedures to insert elements into and delete elements from both ends of a deque constructed from an array.

5)Implement a stack using a singly linked list L. The run time of PUSH and POP should be O(1).

6)Implement a queue using a singly linked list L. The run time of ENQUEUE and DEQUE should be O(1).

7)Can the dynamic-set operation INSERT be implemented on a singly linked list in O(1) time? What about DELETE?

8)Implement the dictionary operations INSERT,DELETE and SEARCH using singly linked,circular lists.What are the running times of the procedures?

9)Give a THETA(n)-time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself.

10)Write the operations of INSERT, DELETE and SEARCH in a linked list.Also, how do we reverse a linked list?