I am participating in the creation activity of the Nuggets newcomer to start the road of writing together.

Algorithms and Data Structures – Designing circular double-ended queues

LeetCode: address

Topic request

Design and implement a double – ended queue. Your implementation needs to support the following:

MyCircularDeque(k) : constructor, double-ended queue size k. InsertFront () : Adds an element to the head of a double-ended queue. Returns true on success. InsertLast () : Adds an element to the end of a double-ended queue. Returns true on success. DeleteFront () : Removes an element from the head of a double-ended queue. Returns true on success. DeleteLast () : Removes an element from the end of a two-ended queue. Returns true on success. GetFront () : Gets an element from the head of a two-ended queue. If the two-end queue is empty, -1 is returned. GetRear () : Gets the last element of a two-ended queue. If the two-end queue is empty, -1 is returned. IsEmpty () : checks whether the double-ended queue isEmpty. IsFull () : checks whether the two-end queue isFull. Example 1:

MyCircularDeque circularDeque = new MycircularDeque(3); Circulardeque.insertlast (1); // Set the capacity to 3 circulardeque.insertlast (1); // Return true circulardeque.insertlast (2); / / return true circularDeque. InsertFront (3); / / return true circularDeque. InsertFront (4); // Already full, return false circulardeque.getrear (); Circulardeque.isfull (); // Return true circulardeque.deletelast (); / / return true circularDeque. InsertFront (4); // Return true circulardeque.getFront (); / / return 4Copy the code

Tip:

  • The range of all values is [1, 1000]
  • The range of operation times is [1, 1000]
  • Do not use the built-in double-endian queue library.
Train of thought
  1. An array
  2. A limit
  3. Just like normal queue processing
code
/** * Initialize your data structure here. Set the size of the deque to be k. * @param {number} k */ var MyCircularDeque  = function (k) { this.limit = k; this.arr = []; }; /** * Adds an item at the front of Deque. Return true if the operation is successful. * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertFront = function (value) { if (this.limit === this.arr.length) return false; this.arr.unshift(value); return true; }; /** * Adds an item at the rear of Deque. Return true if the operation is successful. * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertLast = function (value) { if (this.limit === this.arr.length) return false;  this.arr.push(value); return true; }; /** * Deletes an item from the front of Deque. Return true if the operation is successful. * @return {boolean} */ MyCircularDeque.prototype.deleteFront = function () { if (this.arr.length === 0) return false; this.arr.shift(); return true; }; /** * Deletes an item from the rear of Deque. Return true if the operation is successful. * @return {boolean} */ MyCircularDeque.prototype.deleteLast = function () { if (this.arr.length === 0) return false; this.arr.pop(); return true; }; /** * Get the front item from the deque. * @return {number} */ MyCircularDeque.prototype.getFront = function () { return  this.arr.length > 0 ? this.arr[0] : -1; }; /** * Get the last item from the deque. * @return {number} */ MyCircularDeque.prototype.getRear = function () { return this.arr.length > 0 ? this.arr[this.arr.length - 1] : -1; }; /** * Checks whether the circular deque is empty or not. * @return {boolean} */ MyCircularDeque.prototype.isEmpty = function () { return this.arr.length === 0; }; /** * Checks whether the circular deque is full or not. * @return {boolean} */ MyCircularDeque.prototype.isFull = function () { return this.arr.length === this.limit; }; /** * Your MyCircularDeque object will be instantiated and called as such: * var obj = new MyCircularDeque(k) * var param_1 = obj.insertFront(value) * var param_2 = obj.insertLast(value) * var param_3 = obj.deleteFront() * var param_4 = obj.deleteLast() * var param_5 = obj.getFront() * var param_6 = obj.getRear() * var param_7 = obj.isEmpty() * var param_8 = obj.isFull() */Copy the code