Generalized queue: Design a data structure that supports the following API for a

Question

Generalized queue:

Design a data structure that supports the following API for a generalized queue.

Here is a sample client, showing the contents of the queue after each insertion / deletion.

The data structure should implement all operations in logarithmic time (or better) as a function of the size of the queue. Please use either a union-find, stack / queue, deque, randomized queue, or binary heap data structure. The solution should contain correctness, eciency, clarity, and conciseness.

(a) Describe the underlying data structure.

(b) Draw it after the first 7 insertions for the example above.

(c) Describe how to implement get().

(d) Describe how to implement addFirst() and addLast().

(e) Describe how to implement remove().

Even if you can't answer all of the parts, any help is appreciated. I am totally lost :(

Explanation / Answer

a) Describe the underlying data structure.
=> We can use deque where the Time Complexity are :-
1) addFirst -> O(1)
2) addLast -> O(1)
3) get      -> O(n) but can with O(log n) with little modification
4) remove   -> O(n) but can with O(log n) with little modification

b) Draw it after the first 7 insertions for the example above.
"F E B A C D G"

c) Describe how to implement get().
Save the Address of Item Node for a corresponding String in Hashmap;
dereferenced the address of the Node corresponding to a String at this index.
To the String corresponding to an index, we can use Binary heap data structure;

d) Describe how to implement addFirst() and addLast().
def addFirst(string s):
   if (first == last){
       Item item = new Item(s);
       item->next = last;
       last->prev = item;
       first = item;
   }
   else{
       Item item = new Item(s);
       item->next = first;
       first->prev = item;
       first = item;
   }

def addLast(string s):
   Item item = new Item(s);
   last->next = item;
   item->prev = last;
   last = item;

e) Describe how to implement remove().
Save the Address of Item Node for a corresponding String in Hashmap;
dereferenced the address of the Node corresponding to a String at this index.
To the String corresponding to an index, we can use Binary heap data structure;

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.