Name a data structure that you could use to implement a queue such that all of the standard queue operations are O(1). If you are thinking of a data structure based on Python's built in list, you need to be more specific then just writing "list".

O(1) is constant time and I know that you can use lists to replace using ADTs but what does the question mean by being more specific? Also I thought that lists are O(n), linear time. How would I return something in constant time?

Note: I am a beginner comp sci student who is learning with Python

  • 2
    $\begingroup$ Welcome to CS Stack Exchange! When you copy-paste material from another source, you need to credit the source appropriately. I encourage you to edit the question accordingly. If have doubts about what is meant by a question that was assigned to you, I suggest you ask your instructor or teaching assistant -- they will know what they intended. We can't speak authoritatively about what their intent was. $\endgroup$ – D.W. Apr 18 '17 at 5:11
  • $\begingroup$ "lists are O(n), linear time" -- that sentence makes little sense. A data structure "is" not a Landau class. Some of it's operations may have certain costs that fall into one. And, believe it or not, for some problems lists are more efficient than arrays! $\endgroup$ – Raphael Apr 18 '17 at 20:23

Have a look at this post here. Data structure with search, insert and delete in amortised time $O(1)$? To summarise, it is not possible to have all operations in constant time. If usage of parallelism is an option for you, have a look at this paper titled "A Parallel Priority Queue with Constant Time Operations", http://dx.doi.org/10.1006/jpdc.1998.1425.

| cite | improve this answer | |
  • $\begingroup$ That is probably way over the top for this question. Note also that the OP writes "queue", not "priority queue". $\endgroup$ – Raphael Apr 18 '17 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy