Skip to main content

Deque

A Deque is a container that imitates a traditional double-ended queue. It's designed for efficient pushes and pops from either the beginning or end of the queue, making it suitable for use as a queue or stack. However, it's not optimized for insertions or deletions from the middle.

tip

More information can be found in the API docs.

Deque operations​

The main operations available for a Deque are push_back, push_front, pop_back, and pop_front. It is also possible to check the length of the deque, get an element by index, and iterate over the elements.

  • push_back: Adds an element to the end of the deque. O(1) time complexity.
  • push_front: Adds an element to the beginning of the deque. O(1) time complexity.
  • pop_back: Removes and returns the last element. Returns None if the deque is empty. O(1) time complexity.
  • pop_front: Removes and returns the first element. Returns None if the deque is empty. O(1) time complexity.
  • len: Returns the number of elements in the deque. O(1) time complexity.
  • is_empty: Returns true if the deque contains no elements. O(1) time complexity.
  • get: Retrieves an element by index. Returns None if the index is out of bounds. O(1) time complexity.
  • front: Returns a reference to the first element without removing it. Returns None if the deque is empty.
  • back: Returns a reference to the last element without removing it. Returns None if the deque is empty.
  • iter: Returns an iterator over the elements of the deque.
warning

The maximum capacity of a Deque is u32::MAX - 1 elements. Attempting to push more elements is considered Undefined Behavior.

Deque lifecycle​

Creating a Deque doesn't immediately commit anything to storage. To add elements to the deque, you need to use the push_back or push_front methods.

Values in a Deque must implement the Serialize and Deserialize traits from the serde crate to be stored.

Lifecycle example​

use cw_storage_plus::Deque;

// Create a new deque. It doesn't exist in storage yet.
let deque: Deque<u32> = Deque::new("d");
assert_eq!(deque.len(&storage).unwrap(), 0);

// Add elements to the deque
deque.push_back(&mut storage, &2).unwrap();
deque.push_back(&mut storage, &3).unwrap();
deque.push_front(&mut storage, &1).unwrap();

// Check the length
assert_eq!(deque.len(&storage).unwrap(), 3);

// Remove elements
assert_eq!(deque.pop_back(&mut storage).unwrap(), Some(3));
assert_eq!(deque.pop_front(&mut storage).unwrap(), Some(1));

// Check the final state
assert_eq!(deque.len(&storage).unwrap(), 1);
assert_eq!(deque.get(&storage, 0).unwrap(), Some(2));

Usage examples​

Using Deque as a queue​

use cw_storage_plus::Deque;

let queue: Deque<String> = Deque::new("q");

// Enqueue elements
queue.push_back(&mut storage, &"first".to_string()).unwrap();
queue.push_back(&mut storage, &"second".to_string()).unwrap();

// Dequeue elements
assert_eq!(queue.pop_front(&mut storage).unwrap(), Some("first".to_string()));
assert_eq!(queue.pop_front(&mut storage).unwrap(), Some("second".to_string()));
assert_eq!(queue.pop_front(&mut storage).unwrap(), None);

Using Deque as a stack​

use cw_storage_plus::Deque;

let stack: Deque<u32> = Deque::new("s");

// Push elements
stack.push_back(&mut storage, &1).unwrap();
stack.push_back(&mut storage, &2).unwrap();
stack.push_back(&mut storage, &3).unwrap();

// Pop elements
assert_eq!(stack.pop_back(&mut storage).unwrap(), Some(3));
assert_eq!(stack.pop_back(&mut storage).unwrap(), Some(2));
assert_eq!(stack.pop_back(&mut storage).unwrap(), Some(1));
assert_eq!(stack.pop_back(&mut storage).unwrap(), None);

Iterating over elements​

use cw_storage_plus::Deque;

let deque: Deque<u32> = Deque::new("d");

deque.push_back(&mut storage, &1).unwrap();
deque.push_back(&mut storage, &2).unwrap();
deque.push_back(&mut storage, &3).unwrap();

let sum: u32 = deque.iter(&storage).unwrap().map(|r| r.unwrap()).sum();
assert_eq!(sum, 6);

Maintaining a log store​

It is possible to use a Deque to maintain a store of log events or transaction records. This is useful when you want to keep a history of production level events to ease in debugging a deployed instance of a contract.

use cw_storage_plus::Deque;
use serde::{Serialize, Deserialize};
use cosmwasm_std::testing::*;
use cosmwasm_std::Addr;

#[derive(Serialize, Deserialize, Clone, Debug, PartialEq)]
struct Log {
    block_height: u64,
    sender_addr: String,
    event: String,
}

// Initialize the Deque for storing logs
let logs: Deque<Log> = Deque::new("logs");

// Simulating contract execution context
let env = mock_env();
let info = message_info(&Addr::unchecked("sender"), &[]);
let event = "funds_transferred".to_string();

// Add a new log entry
logs.push_front(
    &mut storage,
    &Log {
        block_height: env.block.height,
        sender_addr: info.sender.to_string(),
        event: event.clone(),
    },
).unwrap();

// Optionally, limit the number of stored logs
const MAX_LOGS: u32 = 100;
if logs.len(&storage).unwrap() > MAX_LOGS {
    logs.pop_back(&mut storage).unwrap();
}

// Retrieve the most recent log
let latest_log = logs.get(&storage, 0).unwrap().unwrap();
assert_eq!(latest_log.event, "funds_transferred");
Last updated on