<p>As some examples of standard queue types:</p>
<ul>
<li>C++ has <a href="https://en.cppreference.com/w/cpp/container/deque" rel="nofollow noreferrer"><code>deque</code></a> (<code>queue</code> is just a wrapper around it), which is typically implemented as a doubly-linked list of arrays.</li>
<li>C# has <a href="https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.queue-1?view=net-7.0" rel="nofollow noreferrer"><code>Queue</code></a>, which uses a resizable circular buffer.</li>
<li>Swift doesn't officially have a queue type, but some standard library algorithms that need one use <a href="https://developer.apple.com/documentation/swift/contiguousarray" rel="nofollow noreferrer"><code>ContiguousArray</code></a>, as it implements the necessary methods.</li>
</ul>
<p>What are the advantages and disadvantages to each approach? What approaches are the most common?</p>

<implementation><queue><standard-library>
What are options for implementing a standard queue type?
CC BY-SA 4.0
2023-05-18T03:16:19.987Z
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.
kaya3
<p>The way they teach you in universities and data structure courses is to take a variable-length data structure (the canonical example is a <code>LinkedList</code>, but anything like an <code>ArrayList</code>, <code>Vector</code> or something you can resize will do), extend it into a queue and only provide queue methods, hiding the original container methods. For example:</p>
<pre><code>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
}
</code></pre>
<p>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)</p>

CC BY-SA 4.0
2023-05-18T02:42:15.243Z
2023-05-18T02:49:58.390Z
2023-05-18T02:49:58.390Z
lyxal
CC BY-SA 4.0
2023-05-18T02:45:04.393Z
This feels like a non-answer. Perhaps my question wasn't clear, but I meant to ask about what underlying data structure to use.
Bbrk24
CC BY-SA 4.0
2023-05-18T02:46:29.947Z
> take a variable-length data structure
lyxal
CC BY-SA 4.0
2023-05-18T02:51:02.607Z
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
lyxal
# What are options for implementing a standard queue type?
Posted by: username_0 on 2023-05-17
As some examples of standard queue types:

* C++ has [`deque`](https://en.cppreference.com/w/cpp/container/deque) (`queue` is just a wrapper around it), which is typically implemented as a doubly-linked list of arrays.
* C# has [`Queue`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.queue-1?view=net-7.0), which uses a resizable circular buffer.
* Swift doesn't officially have a queue type, but some standard library algorithms that need one use [`ContiguousArray`](https://developer.apple.com/documentation/swift/contiguousarray), as it implements the necessary methods.

What are the advantages and disadvantages to each approach? What approaches are the most common?
**Tags:** implementation queue standard-library
> **Comments:**
> **username_1**: 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.  
---
## 1 answers
### Answer by username_2 on 2023-05-18. Score: 2
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)
> **Comments:**
> **username_0** (2023-05-18): This feels like a non-answer. Perhaps my question wasn't clear, but I meant to ask about what underlying data structure to use.  
> **username_2** (2023-05-18): > take a variable-length data structure  
> **username_2** (2023-05-18): 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  
---
