Algorithm

Problem Name: 641. Design Circular Deque

Problem Link: https://leetcode.com/problems/design-circular-deque/

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

Implement the MyCircularDeque class:

  • MyCircularDeque(int k) Initializes the deque with a maximum size of k.
  • boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
  • boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
  • boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
  • boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
  • int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
  • int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
  • boolean isEmpty() Returns true if the deque is empty, or false otherwise.
  • boolean isFull() Returns true if the deque is full, or false otherwise.

 

Example 1:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

Explanation
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);  // return True
myCircularDeque.insertLast(2);  // return True
myCircularDeque.insertFront(3); // return True
myCircularDeque.insertFront(4); // return False, the queue is full.
myCircularDeque.getRear();      // return 2
myCircularDeque.isFull();       // return True
myCircularDeque.deleteLast();   // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront();     // return 4

 

Constraints:

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.
 

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class MyCircularDeque {
  
  private Node head;
  private Node tail;
  private int k;
  private int currSize;

  public MyCircularDeque(int k) {
    this.k = k;
    this.currSize = 0;
    this.head = new Node(-1);
    this.tail = new Node(-1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  public boolean insertFront(int value) {
    if (isFull()) {
      return false;
    }
    Node node = new Node(value);
    Node nextToHead = head.next;
    head.next = node;
    node.prev = head;
    node.next = nextToHead;
    nextToHead.prev = node;
    currSize++;
    return true;
  }

  public boolean insertLast(int value) {
    if (isFull()) {
      return false;
    }
    Node node = new Node(value);
    Node prevToTail = tail.prev;
    tail.prev = node;
    node.next = tail;
    prevToTail.next = node;
    node.prev = prevToTail;
    currSize++;
    return true;
  }

  public boolean deleteFront() {
    if (isEmpty()) {
      return false;
    }
    Node toDelete = head.next;
    deleteNode(toDelete);
    return true;
  }

  public boolean deleteLast() {
    if (isEmpty()) {
      return false;
    }
    Node toDelete = tail.prev;
    deleteNode(toDelete);
    return true;
  }

  public int getFront() {
    if (isEmpty()) {
      return -1;
    }
    return head.next.val;
  }

  public int getRear() {
    if (isEmpty()) {
      return -1;
    }
    return tail.prev.val;
  }

  public boolean isEmpty() {
    return currSize == 0;
  }

  public boolean isFull() {
    return currSize == k;
  }
  
  private void deleteNode(Node node) {
    Node prevToNode = node.prev;
    Node nextToNode = node.next;
    prevToNode.next = nextToNode;
    nextToNode.prev = prevToNode;
    currSize--;
  }
  
  private static class Node {
    int val;
    Node next;
    Node prev;
    
    public Node(int val) {
      this.val = val;
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []]

Output

x
–
+
cmd
[null, true, true, true, false, 2, true, true, true, 4]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const MyCircularDeque = function(k) {
  this.q = []
  this.k = k
};

MyCircularDeque.prototype.insertFront = function(value) {
  if(this.q.length < this.k) {
    this.q.unshift(value)
    return true
  }
  return false
};

MyCircularDeque.prototype.insertLast = function(value) {
  if(this.q.length  <  this.k) {
    this.q.push(value)
    return true
  }
  return false
};

MyCircularDeque.prototype.deleteFront = function() {
  if(this.q.length) {
    this.q.shift()
    return true
  }
  return false
};

MyCircularDeque.prototype.deleteLast = function() {
  if(this.q.length) {
    this.q.pop()
    return true
  }
  return false 
};

MyCircularDeque.prototype.getFront = function() {
  return this.q[0] === undefined ? -1 : this.q[0]
};

MyCircularDeque.prototype.getRear = function() {
  return this.q[this.q.length - 1] === undefined ? -1 : this.q[this.q.length - 1]
};

MyCircularDeque.prototype.isEmpty = function() {
  return this.q.length === 0
};

MyCircularDeque.prototype.isFull = function(> {
  return this.q.length === this.k
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []]

Output

x
–
+
cmd
[null, true, true, true, false, 2, true, true, true, 4]

#3 Code Example with Python Programming

Code - Python Programming


class Node:
    def __init__(self, value):
        self.val = value
        self.next = self.pre = None
        
class MyCircularDeque:

    def __init__(self, k):
        self.head = self.tail = Node(-1)
        self.head.next = self.tail
        self.tail.pre = self.head
        self.size = k
        self.curSize = 0

    def add(self, value, preNode):
        new = Node(value)
        new.pre = preNode
        new.next = preNode.next
        new.pre.next = new.next.pre = new
        self.curSize += 1
        
    def remove(self, preNode):
        node = preNode.next
        node.pre.next = node.next
        node.next.pre = node.pre
        self.curSize -= 1
    
    def insertFront(self, value):
        if self.curSize < self.size:
            self.add(value, self.head)
            return True
        return False

    def insertLast(self, value):
        if self.curSize < self.size:
            self.add(value, self.tail.pre)
            return True
        return False

    def deleteFront(self):
        if self.curSize:
            self.remove(self.head)
            return True
        return False

    def deleteLast(self):
        if self.curSize:
            self.remove(self.tail.pre.pre)
            return True
        return False

    def getFront(self):
        if self.curSize:
            return self.head.next.val
        return -1

    def getRear(self):
        if self.curSize:
            return self.tail.pre.val
        return -1

    def isEmpty(self):
        return self.curSize == 0

    def isFull(self):
        return self.curSize == self.size
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []]

Output

x
–
+
cmd
[null, true, true, true, false, 2, true, true, true, 4]
Advertisements

Demonstration

Previous
#640 Leetcode Solve the Equation Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#643 Leetcode Maximum Average Subarray I Solution in C, C++, Java, JavaScript, Python, C# Leetcode