<commit_before><commit_msg>add draft post about q.js<commit_after>---
layout: post
title:  "q.js"
date:   2014-07-06 19:11:11
comments: true
categories: javascript
---

A Queue can be implemented in Javascript using ```Arays``` with ```Array.pop()``` for enqueue operation and ```Array.push()``` for the dequeue operation. The problem with using ```Arrays``` is that although ```pop()``` runs in constant time ```O(1)```, ```shift()``` runs in linear time ```O(n)```. This is pretty bad when dealing with large queues.

I ended up writing [q.js](http://gsathya.in/q.js/). Here are the important parts -

## Enqeue


{% highlight js %}
/*
 * Enqueues the specified item. The parameter is: item - the item to
 * enqueue
 */

this.push = function(item) {

  var node = {
    data : item,
    next : null
  };

  if (head == null || tail == null) {
    head = tail = node;
  }
  else {
    head.next = node;
    head = node;
  }

  length += 1;
};
{% endhighlight %}

## Dequeue

{% highlight js %}
/*
 * Dequeues an item and returns it. If the queue is empty, the value
 * 'undefined' is returned.
 */
this.pop = function() {

  if (length == 0) {
    return undefined;
  }

  var item = tail.data;
  tail = tail.next;

  length -= 1;

  return item;
};
{% endhighlight %}

The full source code is here.
{'fraction_non_alphanumeric': 0.15923076923076923, 'fraction_numerical': 0.013846153846153847, 'mean_word_length': 3.065625, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1749862', 'n_tokens_mistral': 462, 'n_tokens_neox': 427, 'n_words': 156}