题目

622. 设计循环队列 - 力扣（LeetCode）

题解

rust 设计循环队列
设计循环队列 - 提交记录 - 力扣（LeetCode）

go 设计循环队列
设计循环队列 - 提交记录 - 力扣（LeetCode）

解题思路

思路一： 使用 std::Containers::VecDeque （A double-ended queue implemented with a growable ring buffer.） 数据结构

思路二： 使用 Vec （A contiguous growable array type） 数据结构

（未实践）思路三：使用 array 数据结构

共同点：

1. 任何时候都要注意 队列的容量 cap
2. 注意初始化方法 k值的处理。
3. isEmpty 和 isFull 是很重要的，先想好这两个方法的细节。
4. 使用 Vec 数据结构实现的时候，队列的长度 len （length） 是必要的。
5. 使用固定长度的数组来实现双端循环队列的时候，为了方便可以保留一个空位。

代码

// 使用 std::collections::VecDeque 数据结构
use std::collections::VecDeque;

struct MyCircularQueue {
    vec: VecDeque<i32>,
    cap: usize,

}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyCircularQueue {

    fn new(k: i32) -> Self {
        MyCircularQueue{
            vec: VecDeque::with_capacity(k as usize),
            cap: k as usize,
        }
    }
    
    fn en_queue(&mut self, value: i32) -> bool {
        if self.is_full(){
            false
        } else {
            self.vec.push_back(value);
            true
        }
    }
    
    fn de_queue(&mut self) -> bool {
        if self.is_empty(){
            return false
        }
        self.vec.pop_front();
        true
    }
    
    fn front(&self) -> i32 {
        if self.is_empty() {
            return -1
        }
        self.vec[0]
    }
    
    fn rear(&self) -> i32 {
        if self.is_empty() {
            return -1
        }
        self.vec[self.vec.len()-1]
    }
    
    fn is_empty(&self) -> bool {
        self.vec.len() == 0
    }
    
    fn is_full(&self) -> bool {
        self.vec.len() >= self.cap 
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * let obj = MyCircularQueue::new(k);
 * let ret_1: bool = obj.en_queue(value);
 * let ret_2: bool = obj.de_queue();
 * let ret_3: i32 = obj.front();
 * let ret_4: i32 = obj.rear();
 * let ret_5: bool = obj.is_empty();
 * let ret_6: bool = obj.is_full();
 */

// 使用 Vec 数据结构
struct MyCircularQueue {
    vec: Vec<i32>,
    cap: usize,
    len: usize,
    head: usize,
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyCircularQueue {

    fn new(k: i32) -> Self {
        let k = k as usize;
        Self {
            vec: vec![0; k],
            cap: k,
            len: 0,
            head: 0,
        }
    }
    
    fn en_queue(&mut self, value: i32) -> bool {
        if self.is_full(){
            false
        } else {
            self.vec[(self.head + self.len)%self.cap] = value;
            self.len += 1;
            true
        }
    }
    
    fn de_queue(&mut self) -> bool {
        if self.is_empty(){
            return false
        }
        self.head += 1 ;
        self.head %= self.cap;
        self.len -= 1;
        true
    }
    
    fn front(&self) -> i32 {
        if self.is_empty() {
            return -1
        }
        self.vec[self.head]
    }
    
    fn rear(&self) -> i32 {
        if self.is_empty() {
            return -1
        }
        self.vec[(self.head + self.len - 1)%self.cap]
    }
    
    fn is_empty(&self) -> bool {
        self.len == 0
    }
    
    fn is_full(&self) -> bool {
        self.len == self.cap
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * let obj = MyCircularQueue::new(k);
 * let ret_1: bool = obj.en_queue(value);
 * let ret_2: bool = obj.de_queue();
 * let ret_3: i32 = obj.front();
 * let ret_4: i32 = obj.rear();
 * let ret_5: bool = obj.is_empty();
 * let ret_6: bool = obj.is_full();
 */