Queue

Linked List Implementation

Rust

Java

import java.util.Optional;

public class Queue<T> {
    Node<T> head, tail;

    public void enqueue(T value) {
        var node = new Node<T>(value);

        if (tail == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = tail.next;
        }
    }

    public Optional<T> dequeue() {
        if (head == null)
            return Optional.empty();

        var result = head.value;
        head = head.next;
        if (head == null)
            tail = null; // Queue is empty

        return Optional.of(result);
    }
}

Array Implementation

Rust

#![allow(unused)]
fn main() {
pub struct Queue<T> {
    buffer: Box<[T]>,
    start: usize,
    end: usize,
    size: usize,
}

impl<T> Queue<T> {
    pub fn from(buffer: Box<[T]>) -> Self {
        Self {
            buffer,
            start: 0,
            end: 0,
            size: 0,
        }
    }

    pub fn len(&self) -> usize {
        self.size
    }

    pub fn enqueue(&mut self, value: T) -> Result<(), &'static str> {
        if self.size == self.buffer.len() {
            return Err("The Queue is full");
        }

        self.buffer[self.end] = value;
        self.size += 1;
        self.end = (self.end + 1) % self.buffer.len();

        Ok(())
    }

    pub fn dequeue(&mut self) -> Option<&T> {
        if self.size == 0 {
            return None;
        }

        let result = self.buffer.get(self.start);

        self.start = (self.start + 1) % self.buffer.len();
        self.size -= 1;

        result
    }
}

impl<T: Copy> Iterator for Queue<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.dequeue().and_then(|&v| Some(v))
    }
}
}

Java

import java.util.Optional;

public class ArrayQueue<T> {
    Object[] queue;
    Integer head = 0, tail = 0, size = 0;

    public ArrayQueue(Integer size) {
        queue = new Object[size];
    }

    public void enqueue(T value) throws IndexOutOfBoundsException {
        if (size == queue.length)
            throw new IndexOutOfBoundsException();

        queue[tail] = value;
        tail++;
        if (tail >= queue.length)
            tail = 0;
    }

    public Optional<Object> pop() {
        if (size == 0)
            return Optional.empty();

        var result = queue[head];
        head++;
        if (head >= queue.length)
            head = 0;
        return Optional.of(result);
    }
}