1. Ef?ciently implement a stack class using a singly linked list, with no header or tail nodes.

2. Ef?ciently implement a queue class using a singly linked list, with no header or tail nodes.

3. Ef?ciently implement a queue class using a circular array. You may use a vector (rather than a primitive array) as the underlying array structure.

4. A linked list contains a cycle if, starting from some node p, following a suf?cient number of next links brings us back to node p. p does not have to be the ?rst node in the list. Assume that you are given a linked list that contains N nodes; however, the value of N is unknown.

a. Design an O(N) algorithm to determine if the list contains a cycle. You may use O(N) extra space.

b. Repeat part (a), but use only O(1) extra space. (Hint: Use two iterators that are initially at the start of the list but advance at different speeds.)