Skip to content

Instantly share code, notes, and snippets.

@ifndefdeadmau5
Created October 13, 2016 11:40
Show Gist options
  • Save ifndefdeadmau5/34151c3d7a988ef046f55375febeedb6 to your computer and use it in GitHub Desktop.
Save ifndefdeadmau5/34151c3d7a988ef046f55375febeedb6 to your computer and use it in GitHub Desktop.
Unlimited queue
class UnlimitedQueue {
constructor() {
this.queueArray = [];
}
enqueue(val) {
// Create new queue if there is no available queue
if (this.queueArray.length === 0 ||
this.queueArray[this.queueArray.length - 1].length === 5) {
this.queueArray.push(new Queue());
}
this.queueArray[this.queueArray.length - 1].array.push(val);
}
dequeue( ) {
if( this.queueArray.length === 0 )
return false;
let result = this.queueArray[0].array.shift();
if( this.queueArray[0] === 0)
this.queueArray.shift();
return result;
}
}
class Queue {
constructor() {
this.size = 5;
this.array = [];
this.front = 0;
this.rear = 0;
}
push(val) {
if(this.isFull())
return false;
if(this.rear === this.size)
this.rear = 0;
else {
this.array[this.rear] = val;
this.rear++;
}
}
pop() {
if(this.isEmpty())
return false;
if(this.front === this.size)
this.front = 0;
else {
this.array[this.rear] = 0;
this.front++;
}
}
isEmpty() {
return this.front === this.rear;
}
isFull() {
if(this.front < this.rear)
return (this.rear - this.front) === this.size;
else
return this.front + 1 === this.rear;
}
peek() {
return this.array[this.front];
}
}
let myQ = new UnlimitedQueue();
@hohyon-ryu
Copy link

Python solution

class LimitedQueue:
  CHUNK_SIZE = 5

  def __init__(self):
    self.queue = []
    self.next = None
    self.tail = self
    self.i = 0

  def enqueue(self, val):
    if self.tail.full():
      self.tail.next = LimitedQueue()
      self.tail = self.tail.next
    self.tail.queue.append(val)

  def full(self):
    return len(self.queue) == self.CHUNK_SIZE

  def empty(self):
    return len(self.queue) == self.i

  def dequeue(self):
    if self.empty():
      raise IndexError("The queue is empty.")
    ret = self.queue[self.i]
    self.i += 1
    if self.i == self.CHUNK_SIZE and self.next:
      self.unlink_current()
    return ret

  def unlink_current(self):
    self.queue = self.next.queue
    self.i = 0
    self.next = self.next.next

@hohyon-ryu
Copy link

hohyon-ryu commented Oct 13, 2016

You cannot use this.queueArray as all the arrays are limited to the length of 5. Make it to be a linked list.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment