VecDeque - rust-course

The VecDeque (VECtor Double Ended QUEue) structure is a double-ended queue (see Program 1).

                 ┌────┬────┬────┬────┐
push_front() ──> │    │    │    │    │ <── push_back()
   O(1)          │ 10 │  5 │ 47 │ 13 │        O(1)
 pop_front() <── │    │    │    │    │ ──>  pop_back()
                 └────┴────┴────┴────┘
                             │
                             │
                             ▼
                           get()  O(1)

Program 1:A FIFO (queue)

Elements can be added or retrieved using the four following methods, whose performance is in 𝒪(1):

push_front(): push an item at the front of the queue.
push_back(): push an item at the back of the queue.
pop_front(): pop an item from the front of the queue.
pop_back(): pop an item from the back of the queue.

This means that we can use it either as a stack (a.k.a.: LIFO) or a queue (a.k.a.: FIFO). See Table 1 for a list of some of VecDeque’s most important methods.

Table 1:Some methods of VecDeque

Method	Description
`append(other)`	Appends another `VecDeque` object to this one.
`back()`	Provides a reference to the back element.
`binary_search(v)`	Binary searches for the value `v`. Supposes that this queue is sorted.
`clear()`	Removes all elements.
`contains(v)`	Returns `true` if this queue contains the value `v`.
`front()`	Provides a reference to the front element.
`get(i)`	Gets the element at index `i`. This is an 𝒪(1) operation.
`insert(i, v)`	Inserts the value `v` at a position `i`. Index `0` is the front of the queue.
`is_empty()`	Returns `true` if the queue contains no elements.
`iter()`	Returns a front-to-back iterator.
`len()`	Returns the number of elements.
`make_contiguous()`	Rearranges the ring-buffer so that the front element is at the start of the buffer. This is an 𝒪(n) operation as we need to move all the values.
`new()`	Creates a new vector.
`pop_back()`	Removes the back element and returns it.
`pop_front()`	Removes the front element and returns it.
`push_back(v)`	Appends an element to the back.
`push_front(v)`	Appends an element to the front.
`remove(i)`	Removes and returns the item at index `i`.
`resize(sz, v)`	Resizes the queue to size `sz`, appending copies of `v` if required.
`swap(i, j)`	Swaps elements `i` and `j`.
`truncate(sz)`	Shortens the queue to size `sz`.

A stack, or LIFO (Last In First Out), is a data structure in which items are put in their order of arrival, and only the last one can be put out. See Program 2 for an illustration.

push_back()    pop_back()
   O(1)   │     ▲  O(1)
          │     │
          ▼     │
         ┌────────┐
         │   10   │
         ├────────┤
         │    5   │
         ├────────┤
         │   47   │
         ├────────┤
         │   13   │
         └────────┘

Program 2:A LIFO (stack)

On Program 3 we can see the illustration of a queue, or FIFO (First In First Out). In a queue, the items are put in and put out in their order of arrival.

                 ┌────┬────┬────┬────┐
push_front() ──> │ 10 │  5 │ 47 │ 13 │ ──> pop_back()
   O(1)          └────┴────┴────┴────┘       O(1)

Program 3:A FIFO (queue)

Like the Vec structure, the VecDeque uses an array as the underlying structure. This array:

is growable.
is used as a ring-buffer.

Growable (see Program 4) means it automatically expands when the underlying storage is full. However this implies a copy operation, whose performance is in 𝒪(n).

                           PUSH O(1)
                            │
                            ▼
                          ┌────┐
                          │    │
                          ├────┤
                          │    │
                          ├────┤
                          │    │
                          ├────┤
              PUSH O(1)   │ 21 │
               │          ├────┤
               ▼          │  7 │
┌────┐       ┌────┐ COPY  ├────┤
│    │       │ 10 │ ────> │ 10 │
├────┤       ├────┤ O(n)  ├────┤
│    │       │  5 │       │  5 │
├────┤       ├────┤       ├────┤
│ 47 │       │ 47 │       │ 47 │
├────┤       ├────┤       ├────┤
│ 13 │       │ 13 │       │ 13 │
└────┘       └────┘       └────┘
╰────────┬────────╯         │
  ORIGINAL BUFFER       NEW BUFFER

Program 4:A VecDeque grows to accept new items

The ring-buffer feature (see Program 5) means that the front of the queue is not always at the start of the buffer. In order to get 𝒪(1) performance for push and pop operations, the front and back of the queue move in a circular way.

  │   front          back
 T│    │              │
  │    ▼              ▼
 I│  ┌────┬────┬────┬────┬────┬────┬────┐
  │  │ 10 │  5 │ 47 │ 13 │    │    │    │
 M│  └────┴────┴────┴────┴────┴────┴────┘
  │
 E│             front          back
  │              │              │
 L│              ▼              ▼
  │  ┌────┬────┬────┬────┬────┬────┬────┐
 I│  │    │    │ 47 │ 13 │ 16 │  4 │    │
  │  └────┴────┴────┴────┴────┴────┴────┘
 N│
  │        back           front
 E│         │              │
  │         ▼              ▼
  │  ┌────┬────┬────┬────┬────┬────┬────┐
  │  │ 25 │ 17 │    │    │ 16 │  4 │ 17 │
  ▼  └────┴────┴────┴────┴────┴────┴────┘

Program 5:Demonstration of a ring-buffer usage

27.2.1Creating a new instance¶

To create a new double-ended queue VecDeque<V>, an easy way, like for the Vec type, is to let the compiler infer the type. Inserting at least one value will give the compiler the information it needs:

use std::collections::VecDeque;

let mut names = VecDeque::new();
names.push_back(String::from("Paul"));
names.push_back(String::from("John"));

Couldn't automatically determine type of variable `names`.
Please give it an explicit type.

A VecDeque may also be created from a vector or an array:

let other_names = VecDeque::from([
  "George".to_string(),
  "Ringo".to_string(),
]);
other_names

27.2.2Pushing & removing¶

We can push back or front an element in the VecDeque:

names.push_front(String::from("Paul"));
names

And also remove elements using the pop_*() methods:

names.pop_back()

27.2 VecDeque

27.2.1Creating a new instance¶

27.2.2Pushing & removing¶