Write a program that uses linked lists in order to support the following operations:

1. PUSH (S, x) - pushes a value x into a stack S

2. POP (S, i) - gets a number i (positive integer) and pops i numbers of S. If S contains less than i values, the operation is impossible to execute (program prints ERROR in this case - see below).

3. REVERSE (S) - reverse the order of the elements in S (you might want to apply recursion). If, for example, S is a stack and x was the last inserted, from now on x is treated as the first inserted element.

4. QUEUE (S) - declares that from this moment S becomes and acts like a queue. Nothing is printed after this operation.

5. ENQUEUE(S, x) - adds x to a queue

6. DEQUEUE(S) - removes element when S is a queue.

7. STACK(S) - makes S into a stack. Nothing is printed after this operation is executed.

8. AVERAGE(S) - returns the average of the numbers in S

The program reads a sequence of strings, names of the operations, and additional value (when required). The program prints the values in S after each operation is executed unless it's stated otherwise. If S is empty, program prints EMPTY. The program prints ERROR in case and the operation is impossible to execute. Assume, the program starts with empty stack. Assume, the values are positive integers. The program ends when the string END is entered. Assume, the operation AVERAGE returns 0.0 if S is empty.

For every operation the program must state its running time - write this in comments.

Each important statement in your program must be documented in comments.

And give example