3
$\begingroup$

As some examples of standard queue types:

  • C++ has deque (queue is just a wrapper around it), which is typically implemented as a doubly-linked list of arrays.
  • C# has Queue, which uses a resizable circular buffer.
  • Swift doesn't officially have a queue type, but some standard library algorithms that need one use ContiguousArray, as it implements the necessary methods.

What are the advantages and disadvantages to each approach? What approaches are the most common?

$\endgroup$
1
  • 1
    $\begingroup$ I don't think this is really a language design/implementation question; queues are implemented in many projects, not just compilers/interpreters or standard libraries, and there don't seem to be any specific concerns about implementing a queue for a language's standard library vs. for a third-party library. $\endgroup$
    – kaya3
    Commented May 18, 2023 at 3:16

1 Answer 1

2
$\begingroup$

The way they teach you in universities and data structure courses is to take a variable-length data structure (the canonical example is a LinkedList, but anything like an ArrayList, Vector or something you can resize will do), extend it into a queue and only provide queue methods, hiding the original container methods. For example:

class List {
    method append(data) {...}
    method prepend(data) {...}
    method remove(index) {...} // could be some other form of remove like remove current node if you use a linked list
    // other methods
} 

class Queue extends List {
    // could use something like private inheritance if you're using something like c++
    // otherwise, best practice is to just map original methods of list to error
    method append(data) {error} 
    method prepend(data) {error} 
    method remove(index) {error} 
    method enqueue(data) {super.append(data)}
    method dequeue() {return super.remove(0)} // assuming 0 indexing
    // other queue methods
}

How you implement enqueue and dequeue depend on which data structure/ADT you use. Contiguous memory doesn't make much of a difference here as even Linked Lists have O(1) head and tail removal (it's just removing the first/last node)

$\endgroup$
3
  • $\begingroup$ This feels like a non-answer. Perhaps my question wasn't clear, but I meant to ask about what underlying data structure to use. $\endgroup$
    – Bbrk24
    Commented May 18, 2023 at 2:45
  • $\begingroup$ > take a variable-length data structure $\endgroup$
    – lyxal
    Commented May 18, 2023 at 2:46
  • 1
    $\begingroup$ You asked which data structure to use, I answered that it doesn't matter which one so long as it's resizable. That's the answer. It may not have been what you were expecting but it's an option. @Bbrk24 $\endgroup$
    – lyxal
    Commented May 18, 2023 at 2:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .