One, foreword

So this is going to be a little bit of a preview of what I did in my last article designing a circular queue and the main difference between a circular two-ended queue and a regular circular queue

  • A circular two-end queue can be inserted and deleted at the head of the queue or at the end of the queue, not following the fifO.
  • The normal circular queue can only be inserted at the end of the queue, deleted at the head of the queue, or follow the first-in, first-out.

With that out of the way, I’m going to use arrays to simulate real looping double-ended queues

Ii. Title Description:

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:

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

See Leetcode Connection for a more detailed description

Third, the problem solving

If you’ve designed a loop queue before, this is actually pretty easy. Next I’ll walk you through the operations that a two-ended queue needs to support

3.1 MyCircularDeque(k) : constructor, the size of the two-ended queue is K

Using an array to simulate the space requested by a circular double-ended queue, two Pointers are required to simulate the head and tail of the queue, and a variable is required to record the maximum size of the space

/** * @param {number} k */ var MyCircularDeque = function(k) {this. Max = k this.front = 0 // [front, rear) this.rear = 0 this.queue = new Array(k).fill(null)}Copy the code

3.2 insertFront() : Adds an element to the head of a double-ended queue. Returns true on success

  • The insert operation first considers whether the queue is full
  • Team leader insertion, to consider two situations: 1, team tail 2, non-team tail
  • Front = this.front – 1
  • Front = this. Max – 1
/ * * * @ param value * @ return {Boolean} {number} * / MyCircularDeque prototype. InsertFront = function (value) {/ / if the queue is full, If (this.isfull ()) return false This. front = this.front === 0? This. Max - 1: This. front - 1 // Insert this.queue[this.front] = value return true};Copy the code

3.3 insertLast() : Adds an element to the end of a double-ended queue. Returns true on success

  • First to full
  • There are two situations to consider: 1. The end of the team; 2
  • You can write both cases separately, or you can write one line of code to do the separate code, and I commented it out
/ * * * @ param value * @ return {Boolean} {number} * / MyCircularDeque prototype. InsertLast = function (value) {/ / if the queue is full, If (this.isfull ()) return false // Insert this.queue[this.rear] = value // move back // this.rear = this.rear === this.max - 1 ? Rear = (this.rear + 1) % this. Max = (this.rear + 1) % this. Max = (this.rear + 1) % this. Max);Copy the code

3.4 deleteFront() : Deletes an element from the head of a two-end queue. Returns true on success

  • The delete fails if the delete fails
  • Team head deletion, to consider two situations: 1, team tail 2, non-team tail
/ * * * @ return {Boolean} * / MyCircularDeque prototype. DeleteFront = function () {/ / sentenced to empty, If (this.isEmpty()) return false this.queue[this.front] = null this.front = (this.front + 1) % This. Max // delete successfully return true};Copy the code

3.5 deleteLast() : Removes an element from the end of a two-ended queue. Returns true on success

  • The delete fails if the delete fails
  • Team head deletion, to consider two situations: 1, team tail 2, non-team tail
/ * * * @ return {Boolean} * / MyCircularDeque prototype. DeleteLast = function () {/ / sentenced to empty, Rear = this.rear === 0? This. Max - 1: This. Rear - 1 // delete this.queue[this.rear] = null return true};Copy the code

3.6 getFront() : Retrieves an element from the head of a two-ended queue. If the two-end queue is empty, -1 is returned

  • Call blank, return -1
  • Returns the first element
/ * * * @ return {number} * / MyCircularDeque prototype. GetFront = function () {/ / to empty the if (this. IsEmpty ()) return 1 / / return return this.queue[this.front] };Copy the code

3.7 getRear() : Gets the last element of the two-ended queue. If the two-end queue is empty, -1 is returned

  • Call blank, return -1
  • Returns the last element
  • Notice the rear is pointing to the front of the tail
/ * * * @ return {number} * / MyCircularDeque prototype. GetRear = function () {/ / to empty the if (this. IsEmpty ()) return 1 / / rear Return this.queue[this.rear === 0? This.rear -1: this.rear -1]}; return this.queue[this.rear == 0? This.rear -1: this.rear -1];Copy the code

3.8 isEmpty() : checks whether the two-end queue isEmpty

  • The condition is that front and rear point to the same position and the element in that position is null
/ * * * @ return {Boolean} * / MyCircularDeque prototype. IsEmpty = function () {/ / front and rear point to the same place, Return (this.front === this.rear) && (this.queue[this.front] === null)}; return (this.front === this.rear) && (this.queue[this.front] === null)};Copy the code

3.9 isFull() : checks whether the two-end queue isFull

  • If front and rear point to the same position and the element in that position is not null, the check is complete
/ * * * @ return {Boolean} * / MyCircularDeque prototype. IsFull = function () {/ / front and rear point to the same place, Return (this.front === this.rear) && (this.queue[this.front]! == null) };Copy the code

3.10 Complete code

Git code address

/** * https://leetcode-cn.com/problems/design-circular-deque/ */ /** * @param {number} k */ var MyCircularDeque = function(k) {this. Max = k // this.front = 0 // this. This. Queue = new Array(k).fill(null)} /** * @param {number} value * @return {Boolean} * / MyCircularDeque. Prototype. InsertFront = function (value) {/ / if the queue is full, If (this.isfull ()) return false This. front = this.front === 0? This. Max - 1: This. front - 1 // Insert this.queue[this.front] = value return true}; / * * * @ param value * @ return {Boolean} {number} * / MyCircularDeque prototype. InsertLast = function (value) {/ / if the queue is full, If (this.isfull ()) return false // Insert this.queue[this.rear] = value // move back // this.rear = this.rear === this.max - 1 ? 0: Rear = (this.rear + 1) % this. Max return true}; / * * * @ return {Boolean} * / MyCircularDeque prototype. DeleteFront = function () {/ / sentenced to empty, If (this.isEmpty()) return false this.queue[this.front] = null this.front = (this.front + 1) % This. Max // delete successfully return true}; / * * * @ return {Boolean} * / MyCircularDeque prototype. DeleteLast = function () {/ / sentenced to empty, Rear = this.rear === 0? This. Max - 1: This. Rear - 1 // delete this.queue[this.rear] = null return true}; / * * * @ return {number} * / MyCircularDeque prototype. GetFront = function () {/ / to empty the if (this. IsEmpty ()) return 1 / / return return this.queue[this.front] }; / * * * @ return {number} * / MyCircularDeque prototype. GetRear = function () {/ / to empty the if (this. IsEmpty ()) return 1 / / rear Return this.queue[this.rear === 0? This. Max - 1: return this.queue[this.rear === 0? This. Max - 1: this.rear -1] }; / * * * @ return {Boolean} * / MyCircularDeque prototype. IsEmpty = function () {/ / front and rear point to the same place, Return (this.front === this.rear) && (this.queue[this.front] === null)}; return (this.front === this.rear) && (this.queue[this.front] === null)}; / * * * @ return {Boolean} * / MyCircularDeque prototype. IsFull = function () {/ / front and rear point to the same place, Return (this.front === this.rear) && (this.queue[this.front]! == null) }; /** * 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