{"id":3104,"date":"2018-07-12T22:37:46","date_gmt":"2018-07-13T05:37:46","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3104"},"modified":"2020-07-09T22:35:56","modified_gmt":"2020-07-10T05:35:56","slug":"leetcode-622-design-circular-queue","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/desgin\/leetcode-622-design-circular-queue\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 622. Design Circular Queue"},"content":{"rendered":"\n<p>Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called &#8220;Ring Buffer&#8221;.<\/p>\n\n\n\n<p>One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.<\/p>\n\n\n\n<p>Your implementation should support following operations:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>MyCircularQueue(k)<\/code>: Constructor, set the size of the queue to be k.<\/li><li><code>Front<\/code>: Get the front item from the queue. If the queue is empty, return -1.<\/li><li><code>Rear<\/code>: Get the last item from the queue. If the queue is empty, return -1.<\/li><li><code>enQueue(value)<\/code>: Insert an element into the circular queue. Return true if the operation is successful.<\/li><li><code>deQueue()<\/code>: Delete an element from the circular queue. Return true if the operation is successful.<\/li><li><code>isEmpty()<\/code>: Checks whether the circular queue is empty or not.<\/li><li><code>isFull()<\/code>: Checks whether the circular queue is full or not.<\/li><\/ul>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">MyCircularQueue circularQueue = new MyCircularQueue(3); \/\/ set the size to be 3\ncircularQueue.enQueue(1); &nbsp;\/\/ return true\ncircularQueue.enQueue(2); &nbsp;\/\/ return true\ncircularQueue.enQueue(3); &nbsp;\/\/ return true\ncircularQueue.enQueue(4); &nbsp;\/\/ return false, the queue is full\ncircularQueue.Rear(); &nbsp;\/\/ return 3\ncircularQueue.isFull(); &nbsp;\/\/ return true\ncircularQueue.deQueue(); &nbsp;\/\/ return true\ncircularQueue.enQueue(4); &nbsp;\/\/ return true\ncircularQueue.Rear(); &nbsp;\/\/ return 4\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>All values will be in the range of [0, 1000].<\/li><li>The number of operations will be in the range of&nbsp;[1, 1000].<\/li><li>Please do not use the built-in Queue library.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Simulate with an array<\/strong><\/h2>\n\n\n\n<p>We need a fixed length array, and the head location as well as the size of the current queue.<\/p>\n\n\n\n<p>We can use q[head] to access the front, and q[(head + size &#8211; 1) % k] to access the rear.<\/p>\n\n\n\n<p>Time complexity: O(1) for all the operations.<br>Space complexity: O(k)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass MyCircularQueue {\npublic:\n  MyCircularQueue(int k): q_(k) {}\n  \n  bool enQueue(int value) {\n    if (isFull()) return false;\n    q_[(head_ + size_) % q_.size()] = value;    \n    ++size_;\n    return true;\n  }\n  \n  bool deQueue() {\n    if (isEmpty()) return false;\n    head_ = (head_ + 1) % q_.size();\n    --size_;\n    return true;\n  }\n\n  int Front() { return isEmpty() ? -1 : q_[head_]; }\n\n  int Rear() { return isEmpty() ? -1 : q_[(head_ + size_ - 1) % q_.size()]; }\n\n  bool isEmpty() { return size_ == 0; }\n\n  bool isFull() { return size_ == q_.size(); }\nprivate:\n  vector<int> q_;\n  int head_ = 0;\n  int size_ = 0;\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nclass MyCircularQueue {\n  private int[] q;\n  private int head;\n  private int size;\n  \n  public MyCircularQueue(int k) {\n    this.q = new int[k];\n    this.head = 0;\n    this.size = 0;\n  }\n  \n  public boolean enQueue(int value) {\n    if (this.isFull()) return false;    \n    this.q[(this.head + this.size) % this.q.length] = value;\n    ++this.size;\n    return true;\n  }\n\n  public boolean deQueue() {\n    if (this.isEmpty()) return false;\n    this.head = (this.head + 1) % this.q.length;\n    --this.size;\n    return true;\n  }\n\n  public int Front() {\n    return this.isEmpty() ? -1 : this.q[this.head];\n  }\n\n  public int Rear() {\n    return this.isEmpty() ? -1 : this.q[(this.head + this.size - 1) % this.q.length];\n  }\n\n  public boolean isEmpty() { return this.size == 0; }  \n\n  public boolean isFull() { return this.size == this.q.length; }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass MyCircularQueue:\n  def __init__(self, k: int):\n    self.q = [0] * k\n    self.k = k\n    self.head = self.size = 0\n\n\n  def enQueue(self, value: int) -> bool:\n    if self.isFull(): return False\n    self.q[(self.head + self.size) % self.k] = value\n    self.size += 1\n    return True\n\n\n  def deQueue(self) -> bool:\n    if self.isEmpty(): return False\n    self.head = (self.head + 1) % self.k\n    self.size -= 1\n    return True\n\n\n  def Front(self) -> int:\n    return -1 if self.isEmpty() else self.q[self.head]\n\n\n  def Rear(self) -> int:\n    return -1 if self.isEmpty() else self.q[(self.head + self.size - 1) % self.k]\n\n\n  def isEmpty(self) -> bool:\n    return self.size == 0\n\n\n  def isFull(self) -> bool:\n    return self.size == self.k\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[340],"tags":[291,214,251,213],"class_list":["post-3104","post","type-post","status-publish","format-standard","hentry","category-desgin","tag-data-structure","tag-deque","tag-design","tag-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3104","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3104"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3104\/revisions"}],"predecessor-version":[{"id":7059,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3104\/revisions\/7059"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3104"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3104"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3104"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}