Two Queues

/*  A Tale of Two Queues
 *
 *  thisQ had the most diffuse of forms,
 *    thatQ had the most compact of forms;
 *  thisQ could increase in size indefinitely,
 *    thatQ had a finite capacity;
 *  thisQ needed space for a sentinel node,
 *    thatQ had no such need;
 *  thisQ began with nothing but an end,
 *    thatQ began with room for everything;
 *  thisQ cycled end-to-end in both directions,
 *    thatQ shifted straight in one direction;
 *  in short, thisQ's form and function was so far
 *    like thatQ's, that some of the noisiest
 *    academics insisted on thisQ or thatQ being
 *    used, instead of the other, on the basis of
 *    time- and space-efficiency comparisons only.
 *
 *  SEE ALSO
 *
 *  https://en.wikipedia.org/wiki/A_Tale_of_Two_Cities#Book_the_First:_Recalled_to_Life
 *  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/this
 */

function DiffuseQueue() {

  // Values
  const thisQ = this;
  const end = {value: null};
  end.next = end.prev = end;

  // Operations
  thisQ.push = function(value) {
    end.next = end.next.prev =
      {value: value, next: end.next, prev: end};
    return thisQ;
  };
  thisQ.shift = function() {
    const value = end.prev.value;
    end.prev = end.prev.prev;
    end.prev.next = end;
    return value;
  };
  thisQ.isEmpty = function() {
    return end.next === end;
  };

  // The End
  return thisQ;
}

function CompactQueue(capacity) {

  // Values
  const thatQ = this;
  const array = new Array(capacity);
  let first = 0, size = 0;

  // Operations
  thatQ.push = function(value) {
    if (size < capacity) {
      const i = (first + size) % capacity;
      array[i] = value;
      size = size + 1;
    }
    return thatQ;
  };
  thatQ.shift = function() {
    let value = null;
    if (size > 0) {
      value = array[first];
      first = (first + 1) % capacity;
      size = size - 1;
    }
    return value;
  };
  thatQ.isEmpty = function() {
    return size === 0;
  }

  // The End
  return thatQ;
}

Exercises

1. Why might someone insist that you should never create a JavaScript array as follows? What if the programming language was Java instead of JavaScript?

   new Array(capacity)

2. Why might someone want to create a JavaScript array by passing an initial capacity value to the Array constructor function as shown in the previous exercise?
3. When would you use DiffuseQueue instead of CompactQueue? When would you prefer CompactQueue over DiffuseQueue?
4. A “deque” is a double-ended queue. What does that mean? What word rhymes with deque?
5. What’s an example of a situation where you would use a deque?
6. Implement and test the types DiffuseDeque and CompactDeque.
7. Write a program that solves a problem using a deque.