Problem 1: Generalized queue. Design a data structure that supports the following operations for a generalized queue: (i) Find(i) which returns the i-th item from the queue. (ii) InsertFirst(x) which inserts item x at the front of the queue. (iii) InsertLast(x) which inserts item x to the front of the queue. (iv) Delete(i) which removes the i-th item from the queue. Here is a simple example: Initialize Q to be an empty generalized queue. Calling InsertFirst(A) on Q results in Q = [A]. Calling InsertFirst(B) on Q results in Q = [B, A]. Calling InsertLast(C) on Q results in Q = [B, A, C]. Calling InsertLast(D) on Q results in Q = [B, A, C, D]. Calling InsertFirst(E) on Q results in Q = [E, B, A, C, D]. Calling InsertFirst(F) on Q results in Q = [F, E, B, A, C, D]. Calling InsertLast(G) on Q results in Q = [F, E, B, A, C, D, G]. Calling Find(2) on Q returns E. Calling Delete(2) on Q results in Q = [F, B, A, C, D, G]. Calling Find(2) on Q returns B. Your data structure should implement all operations in O(log n), where n is the number of elements in the data structure.
Problem 1: Generalized queue. Design a data structure that supports the following
operations for a generalized queue:
(i) Find(i) which returns the i-th item from the queue.
(ii) InsertFirst(x) which inserts item x at the front of the queue.
(iii) InsertLast(x) which inserts item x to the front of the queue.
(iv) Delete(i) which removes the i-th item from the queue.
Here is a simple example:
Initialize Q to be an empty generalized queue.
Calling InsertFirst(A) on Q results in Q = [A].
Calling InsertFirst(B) on Q results in Q = [B, A].
Calling InsertLast(C) on Q results in Q = [B, A, C].
Calling InsertLast(D) on Q results in Q = [B, A, C, D].
Calling InsertFirst(E) on Q results in Q = [E, B, A, C, D].
Calling InsertFirst(F) on Q results in Q = [F, E, B, A, C, D].
Calling InsertLast(G) on Q results in Q = [F, E, B, A, C, D, G].
Calling Find(2) on Q returns E.
Calling Delete(2) on Q results in Q = [F, B, A, C, D, G].
Calling Find(2) on Q returns B.
Your data structure should implement all operations in O(log n), where n is the number
of elements in the data structure.
Step by step
Solved in 3 steps
