Part 1

Illustrate the result of each operation in the sequence PUSH(S, 4), PUSH(S, 1), PUSH(S,3), POP(S), PUSH(S, 8), and POP(S) on an initially empty stack S stored in array S[1 6]. When you begin, the stack is empty. You will need to draw a diagram of the stack showing the result after each operation.

Part-2:

Implement a stack using a singly linked list L in Python or Java.

Do the operations PUSH and POP take O(1) time?

Explain why?

Test your code with PUSH(10), PUSH(30), POP(), PUSH(80), and POP

Part-3:

Implement a queue by a singly linked list L in Python or Java.

Do the operations ENQUEUE and DEQUEUE take O(1) time?

Why?

Test your code with ENQUEUE(4), ENQUEUE(1), ENQUEUE(3), DEQUEUE(), ENQUEUE(8), and DEQUEUE().