var sys = require('sys');

function deque()
{
    this.begin = null;
    this.end = null;
    this.length = 0;
}

deque.prototype.push = function(data)
{
    if (!this.begin)
    {
        this.begin = this.end = { 'data': data };
        this.begin.next = this.begin; 
        this.begin.prev = this.begin; 
    } else {
        var end = this.end;
        this.end = { 'data': data };
        this.end.prev = end;
        end.next = this.end;
    }
    ++this.length;
}

deque.prototype.top = function()
{
    if (this.begin)
        return this.begin.data;
    sys.p("queue empty");
}

deque.prototype.empty = function()
{
    return this.length == 0;
}

deque.prototype.shift = function()
{
    --this.length;
    if (this.begin == this.end)
    {
        this.begin = this.end = null;
        return this.begin;
    }
    var res = this.begin.data;
    this.begin = this.begin.next;
    return res;
}

exports.queue = deque;

@@ -1,12 +1,103 @@
+// doubly-linked list for constant time shift%0A// each node have prev,next,data properties%0A%0A
 var sys = re
@@ -254,24 +254,50 @@
 !this.begin)
+ // insert into empty list
 %0A    %7B%0A     
@@ -580,16 +580,33 @@
 length;%0A
+    return this;%0A
 %7D%0A%0Adeque
@@ -655,16 +655,16 @@
 .begin)%0A
+
         
@@ -691,34 +691,8 @@
 ta;%0A
-    sys.p(%22queue empty%22);%0A
 %7D%0A%0Ad

return node reference on push