641. Design Circular Deque

Design your implementation of the circular double-ended queue (deque).

Your implementation should support following operations:

  • MyCircularDeque(k): Constructor, set the size of the deque to be k.
  • insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
  • insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
  • deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
  • deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
  • getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
  • getRear(): Gets the last item from Deque. If the deque is empty, return -1.
  • isEmpty(): Checks whether Deque is empty or not. 
  • isFull(): Checks whether Deque is full or not.

 

Example:

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);			// return true
circularDeque.insertLast(2);			// return true
circularDeque.insertFront(3);			// return true
circularDeque.insertFront(4);			// return false, the queue is full
circularDeque.getRear();  			// return 2
circularDeque.isFull();				// return true
circularDeque.deleteLast();			// return true
circularDeque.insertFront(4);			// return true
circularDeque.getFront();			// return 4

 

Note:

  • All values will be in the range of [0, 1000].
  • The number of operations will be in the range of [1, 1000].
  • Please do not use the built-in Deque library.

Rust Solution

struct MyCircularDeque {
    k: usize,
    start: usize,
    end: usize,
    data: Vec<i32>,
    count: usize,
}

impl MyCircularDeque {
    fn new(k: i32) -> Self {
        let start = 0;
        let end = 0;
        let k = k as usize;
        let data = vec![0; k];
        let count = 0;
        MyCircularDeque {
            k,
            start,
            end,
            data,
            count,
        }
    }
    fn insert_front(&mut self, value: i32) -> bool {
        if self.count == self.k {
            false
        } else {
            self.count += 1;
            self.start = (self.start + self.k - 1) % self.k;
            self.data[self.start] = value;
            true
        }
    }

    fn insert_last(&mut self, value: i32) -> bool {
        if self.count == self.k {
            false
        } else {
            self.count += 1;
            self.data[self.end] = value;
            self.end = (self.end + 1) % self.k;
            true
        }
    }

    fn delete_front(&mut self) -> bool {
        if self.count == 0 {
            false
        } else {
            self.count -= 1;
            self.start = (self.start + 1) % self.k;
            true
        }
    }

    fn delete_last(&mut self) -> bool {
        if self.count == 0 {
            false
        } else {
            self.count -= 1;
            self.end = (self.end + self.k - 1) % self.k;
            true
        }
    }

    fn get_front(&self) -> i32 {
        if self.is_empty() {
            -1
        } else {
            self.data[self.start]
        }
    }

    fn get_rear(&self) -> i32 {
        if self.is_empty() {
            -1
        } else {
            self.data[(self.end + self.k - 1) % self.k]
        }
    }

    fn is_empty(&self) -> bool {
        self.count == 0
    }

    fn is_full(&self) -> bool {
        self.count == self.k
    }
}

#[test]
fn test() {
    let mut queue = MyCircularDeque::new(3);
    assert_eq!(queue.insert_last(1), true);
    assert_eq!(queue.insert_last(2), true);
    assert_eq!(queue.insert_front(3), true);
    assert_eq!(queue.insert_front(4), false);
    assert_eq!(queue.get_rear(), 2);
    assert_eq!(queue.is_full(), true);
    assert_eq!(queue.delete_last(), true);
    assert_eq!(queue.insert_front(4), true);
    assert_eq!(queue.get_front(), 4);
}

Having problems with this solution? Click here to submit an issue on github.