Quick double-ended queue (deque) for V
This is a V module implementing
deque
[]T
Ignoring the cost of internal resize actions, it supports
O(1)
Installation
v install avitkauskas.deque
Usage
Default initialization:
import avitkauskas.deque
mut q := deque.new[int]()
Definitions of supported functions:
// push new element to the front or back of the queue
q.push_front(x T)
q.push_back(x T)
// pop (delete and return) the first or last element of the queue
q.pop_front() ?T
q.pop_back() ?T
// many functions return `none` if the queue is empty
q.pop_front() or { 0 }
q.pop_back() or { 0 }
// to use it as a single-ended queue, you can use aliases
q.push(x T) // same as q.push_back(x T)
q.pop() ?T // same as q.pop_front() ?T
// append or predend several elements at once (given in an array)
q.append(a []T)
q.prepend(a []T)
// the order of the elements will remain unchanged
// given the queue like [1, 1, 1] and an array of [7, 8, 9],
// `append` results in a queue of [1, 1, 1, 7, 8, 9]
// and `prepend` results is [7, 8, 9, 1, 1, 1]
// to check the first or last element in the queue without removing it
q.front() ?T
q.back() ?T
// for single-ended queue you can use an alias
q.peek() ?T // same as q.front() ?T
// to get and set any individual element at any index
q.get(i int) ?T // `none` if empty or `i` is out of range
q.set(i int, x T) ! // error if empty or `i` is out of range
// number of elements in a queue
q.len() int
// max number of elements allowed in a queue (when max: parameter is set)
// before starting to drop the oldest elements from the other end on `push`
q.max_len() int
// check if the queue is empty
q.is_empty() bool
// clear the queue (delete all elements) but keep the buffer in memory
q.clear()
// keep all the elements in a queue but shrink the buffer
// to the size of the nearest power of two in elements count
q.shrink()
// get the array representation of the queue
q.array() []T
// get the string representation of the queue
// also called implicitly by print() and println()
q.str() string
// str() returns the string representation of the array
// if the size of the queue is less than or equal to 25 elements.
// Otherwise, gives the first 10 and the last 10 elements in a string like
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
// ... 190 other elements ...,
// 201, 202, 203, 204, 205, 206, 207, 208, 209, 210]
Initialization: parameters and optimization
You should find deque being quick and efficient by default for most common use cases. But if you want to further optimize for speed and know certain characteristics of your queue at run time (most likely size etc.), you can provide certain parameters during the initialization of the queue to make it run faster. Speed gain can be significant if you avoid the queue growing and shrinking as this also requires copying of the existing elements and is expensive.
Parameters
The
new[T]()
@[params]
pub struct DequeParams {
pub:
min int = 64
max int = -1
shrink bool = true
}
The default initial size of deque is
64 elements
If you know that the size of your queue will grow to the certain number and should stay there for the most of the time, dropping to lower numbers just occasionally, you can provide the
min:
new[int]()
min
min/2
mut q := deque.new[int](min: 100_000)
Avoiding resizing (re-allocations of the underlying array and copying of the elements of the queue to the new location) you can gain a lot of speed at the expense of the higher memory usage.
If you do not know the max size of your queue in advance, but you still want to be as quick as possible - you can tell deque not to shrink at any time. Then the queue will grow as needed but will never shrink.
mut q := deque.new[int](shrink: false)
You can combine these two parameters together, if needed:
mut q := deque.new[int](min: 100_000, shrink: false)
This will initially allocate space for the
min
And finally, you can provide the
max:
max
mut q := deque.new[int](max: 100_000)
Limitations
Maximum elements allowed in deque is
2^30 - 1
1_073_741_823
bitwise and
&
modulus
%
32-bit int
2^31
As a simple rule to remember, the number of elements in your queue should not ever roughly exceed
1 billion
Let's go queuing!