Adding `final class Deque` to PHP

Hi internals, I've created a new RFC https://wiki.php.net/rfc/deque to add a final class Deque This is based on the Teds\Deque implementation I've worked on for the https://github.com/TysonAndre/pecl-teds PECL. While SplDoublyLinkedList and its subclass SplQueue/SplStack exist in the SPL, they have several drawbacks that are addressed by this RFC to add a Deque class (to use instead of those): 1. SplDoublyLinkedList is internally represented by a doubly linked list, making it use roughly twice as much memory as the proposed Deque 2. push/pop/unshift/shift from SplDoublyLinkedList are slower due to needing to allocate or free the linked list nodes. 3. Reading values in the middle of the SplDoublyLinkedList is proportional to the length of the list, due to needing to traverse the linked list nodes. 4. foreach Iteration behavior cannot be understood without knowing what constructed the SplDoublyLinkedList instance or set the flags. It would be useful to have an efficient Deque container in the standard library to provide an alternative without those drawbacks, as well as for the following reasons: 1. To save memory in applications or libraries that may need to store many lists of values or run for long periods of time. Notably, PHP's array type will never release allocated capacity. See https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html 2. To provide a better alternative to SplDoublyLinkedList, SplStack, and SplQueue for use cases that require stacks or queues. 3. As a more efficient option than array and SplDoublyLinkedList as a queue or Deque, especially for unshift. A Deque is more efficient than an array when used as a queue, more readable, and easier to use correctly. While it is possible to efficiently remove elements from the start of an array (in terms of insertion order), it is very inefficient to prepend elements to the start of a large array due to needing to either copy the array or move all elements in the internal array representation, and an array would use much more memory than a Deque when used that way (and be slower). There are also several pitfalls to using an array as a queue for larger queue sizes, some of which are not obvious and discovered while writing the benchmarks. (Having a better (double-ended) queue datastructure (Deque) than the SplDoublyLinkedList would save users from needing to write code with these pitfalls): 1. array_key_first() takes time proportional to the number of elements unset from the start of an array, causing it to unexpectedly be extremely slow (quadratic time) after unsetting many elements at the start of the queue. (when the array infrequently runs out of capacity, buckets are moved to the front) 2. reset() or end() will convert a variable to a reference, and php is significantly less efficient at reading or writing to reference. Opcache is also less efficient at optimizing uses of variables using references. 3. More obviously, array_unshift and array_shift will take time proportional to the number of elements in the array (to reindex and move existing/remaining elements). After the discussion period ends, I currently plan to start voting on the Deque RFC and await the results to determine next steps for the Vector RFC. ---- The thread for my other open proposal final class Vector (https://externals.io/message/116048) has prior discussion on implementation choices, naming choices, and motivation for adding datastructures to php-src. - E.g. the question of why we should add general-purpose datastructures to php-src itself rather than have users rely on PECLs, and why this proposal doesn't and can't use php-ds/ext-ds. Thanks, Tyson