{"id":3147,"date":"2018-07-14T20:58:04","date_gmt":"2018-07-15T03:58:04","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3147"},"modified":"2018-07-14T21:21:07","modified_gmt":"2018-07-15T04:21:07","slug":"leetcode-641-design-circular-deque","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-641-design-circular-deque\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 641. Design Circular Deque"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p>Design your implementation of the circular double-ended queue (deque).<br \/>\nYour implementation should support following operations:<\/p>\n<ul>\n<li>MyCircularDeque(k): Constructor, set the size of the deque to be k.<\/li>\n<li>insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.<\/li>\n<li>insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.<\/li>\n<li>deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.<\/li>\n<li>deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.<\/li>\n<li>getFront(): Gets the front item from the Deque. If the deque is empty, return -1.<\/li>\n<li>getRear(): Gets the last item from Deque. If the deque is empty, return -1.<\/li>\n<li>isEmpty(): Checks whether Deque is empty or not.<\/li>\n<li>isFull(): Checks whether Deque is full or not.<\/li>\n<\/ul>\n<p><strong>Example:<\/strong><\/p>\n<pre class=\"crayon:false \">MyCircularDeque circularDeque = new MycircularDeque(3); \/\/ set the size to be 3\r\ncircularDeque.insertLast(1);\t\t\t\/\/ return true\r\ncircularDeque.insertLast(2);\t\t\t\/\/ return true\r\ncircularDeque.insertFront(3);\t\t\t\/\/ return true\r\ncircularDeque.insertFront(4);\t\t\t\/\/ return false, the queue is full\r\ncircularDeque.getRear();  \t\t\t\t\/\/ return 32\r\ncircularDeque.isFull();\t\t\t\t\/\/ return true\r\ncircularDeque.deleteLast();\t\t\t\/\/ return true\r\ncircularDeque.insertFront(4);\t\t\t\/\/ return true\r\ncircularDeque.getFront();\t\t\t\t\/\/ return 4\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li>All values will be in the range of [1, 1000].<\/li>\n<li>The number of operations will be in the range of\u00a0[1, 1000].<\/li>\n<li>Please do not use the built-in Deque library.<\/li>\n<\/ul>\n<h1><strong>Solution<\/strong><\/h1>\n<p>Using head and tail to pointer to the head and the tail in the circular buffer.<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 20 ms\r\nclass MyCircularDeque {\r\npublic:\r\n  \/** Initialize your data structure here. Set the size of the deque to be k. *\/\r\n  MyCircularDeque(int k): k_(k), q_(k), head_(1), tail_(-1), size_(0) {}\r\n\r\n  \/** Adds an item at the front of Deque. Return true if the operation is successful. *\/\r\n  bool insertFront(int value) {\r\n    if (isFull()) return false;\r\n    head_ = (head_ - 1 + k_) % k_;\r\n    q_[head_] = value;\r\n    if (size_ == 0) tail_ = head_;\r\n    ++size_;\r\n    return true;\r\n  }\r\n\r\n  \/** Adds an item at the rear of Deque. Return true if the operation is successful. *\/\r\n  bool insertLast(int value) {\r\n    if (isFull()) return false;\r\n    tail_ = (tail_ + 1 + k_) % k_;\r\n    q_[tail_] = value;\r\n    if (size_ == 0) head_ = tail_;\r\n    ++size_;\r\n    return true;  \r\n  }\r\n\r\n  \/** Deletes an item from the front of Deque. Return true if the operation is successful. *\/\r\n  bool deleteFront() {\r\n    if (isEmpty()) return false;\r\n    head_ = (head_ + 1 + k_) % k_;\r\n    --size_;\r\n    return true;\r\n  }\r\n\r\n  \/** Deletes an item from the rear of Deque. Return true if the operation is successful. *\/\r\n  bool deleteLast() {\r\n    if (isEmpty()) return false;\r\n    tail_ = (tail_ - 1 + k_) % k_;\r\n    --size_;\r\n    return true;\r\n  }\r\n\r\n  \/** Get the front item from the deque. *\/\r\n  int getFront() {\r\n    if (isEmpty()) return -1;\r\n    return q_[head_];\r\n  }\r\n\r\n  \/** Get the last item from the deque. *\/\r\n  int getRear() {\r\n    if (isEmpty()) return -1;\r\n    return q_[tail_];\r\n  }\r\n\r\n  \/** Checks whether the circular deque is empty or not. *\/\r\n  bool isEmpty() {\r\n    return size_ == 0;\r\n  }\r\n\r\n  \/** Checks whether the circular deque is full or not. *\/\r\n  bool isFull() {\r\n    return size_ == k_;\r\n  }\r\nprivate:\r\n  const int k_;\r\n  int head_;\r\n  int tail_;\r\n  int size_;\r\n  vector&lt;int&gt; q_;\r\n};<\/pre>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-622-design-circular-queue\/\">\u82b1\u82b1\u9171 LeetCode 622. Design Circular Queue<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem 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&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[331,214,330,222],"class_list":["post-3147","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-circular","tag-deque","tag-desgin","tag-easy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3147","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=3147"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3147\/revisions"}],"predecessor-version":[{"id":3153,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3147\/revisions\/3153"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3147"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3147"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3147"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}