Question 5: Consider the unique queue, or UQUE. Let the operations be new, add,

Question

Question 5:

Consider the unique queue, or UQUE. Let the operations be new, add, peek, rest, size: add puts an item on the tail of the queue peek returns the head item rest returns the queue that remains when the head item is taken off size tells how many items are in the queue In a UQUE, we add elements to the queue at the back, and we remove them from the front like a normal queue. However, we do not allow two or more elements in the queue to have the same value. If we do (for example) add(Q, 5) and 5 is already in Q, then nothing is added, and the queue remains the same length as before the add. If 5 is not in Q, the length of Q grows by one, and 5 is at the back of the queue. Describe the data structures you would use to implement the UQUE so that the "add" operation can be done in O(1) worst case time. Explain how it all works, and justify your claims. Describe the optimal space used by your solution in terms of N (size of the UQUE).

Explanation / Answer

HashSet offers O(1) time for add, remove, contains operations.

We can maintain a HashSet containing a key that uniquely identifies the items in the queue. Then just check the HashSet to see if the item is present. If it already exists, then we won't insert it into the Queue. This takes O(1) in HashSet. When you remove an item from the Queue, simply remove the key from the HashSet as well.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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