We want to build a queue for integer elements that in addition to the operations we
saw during the lecture, also supports a SEESAW operation that on a given queue
holding the elements returns
All operations should run in O(1) time. Your data structure should take O(n)
space, where n is the number of elements currently stored in the data structure.
Your task is to:
a) Design a data structure that supports the required operations in the required
time and space.
b) Briefly argue the correctness of your data structure and operations.
c) Analyse the running time of your operations and space of your data structure.
We want to build a stack for elements having a colour attribute (e.g., blue, red, or-
ange, etc). We say that a bunch of consecutive positions in the array for a monochro-
matic stretch if all the elements stored in those positions have the same colour. In
addition to the usual stack operations, we want to support a MAxMoNO( operation
that on a given stack returns the maximum length of any monochromatic stretch
currently stored in the stack.
All operations should run in O(1) time. Your data structure should take O(n)
space, where n is the number of elements currently stored in the data structure.
a) Describe your algorithm in plain English.
b) Briefly argue the correctness of your data structure and operations.
c) Analyse the running time of your operations and space of your data structure