User Tools

Site Tools


λ Queue array-based

======= Algorithm ======= <syntax js> function Queue() { this.left = []; this.right = []; } Queue.prototype = { enqueue: function(data) { // Adds new data to the top of the 'right' stack. this.right.push(data); }, dequeue: function() { if (this.left.length === 0) { // If both stacks are empty then return 'null' if (this.right.length === 0) { return null; } // If the left stack is empty copy right 'slice()' and // reverse the order of the elements. this.left = this.right.slice().reverse(); this.right.length = 0; } return this.left.pop(); } }</syntax> ======= Support ======= <syntax js> // Initial starting stack. queue = new Queue(); queue.enqueue("A"); queue.enqueue("B"); queue.enqueue("C"); function preRun() { if (!(queue instanceof Queue)) { // Copy the queue from data - used for web-workers. var myqueue = new Queue(); myqueue.left = queue.left; myqueue.right = queue.right; // Replace the global 'queue' with the converted one. queue = myqueue; } } </syntax> ======= Tests ======= <syntax js> function testA() { var q = new Queue(); q.enqueue(1); q.enqueue(2); q.enqueue(3); assert(q.dequeue() === 1); assert(q.dequeue() === 2); assert(q.dequeue() === 3); assert(q.dequeue() === null, "End of queue."); } function testB() { var q = new Queue(); q.enqueue(1); q.enqueue(2); assert(q.dequeue() === 1); q.enqueue(3); q.enqueue(4); assert(q.dequeue() === 2); q.enqueue(5); assert(q.dequeue() === 3); assert(q.dequeue() === 4); assert(q.dequeue() === 5); assert(q.dequeue() === null, "End of queue."); }</syntax> ======= Options ======= <syntax js> { "title": "Queue array-based", "height": "320px", "preRunSource": true, "persistentGlobals": ["queue"] } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <script src="http://d3js.org/d3.v2.js"></script> <style type='text/css'> .slot rect { fill: #eee; stroke: #ccc; } .selected rect { fill: #fee; stroke: #f00; } svg { font-family: Verdana, Helvetica; font-size: 12px; } </style> <script> function setup() { svg = d3.select("#result") .append("svg") .attr("width", 348) .attr("height", 400) .append("g").attr("transform", "translate(20.5,20.5)"); returnText = svg.append("text") .attr("dx", "-10") .attr("dy", "40"); leftLabel = svg.append("text").text("Left") .attr("dx", "-10") .attr("dy", "0"); rightLabel = svg.append("text").text("Right") .attr("dx", "-10") .attr("dy", "0"); } var poppedMarker = {}; function globals() { // Return a unique marker that enables to identify when popped has not been set. return {"popped": poppedMarker}; } function drawArray(slots, name, yoffset) { slots.exit().remove(); // Create the array var g = slots.enter() .append("g") .attr("class", "slot "+name); g.append("rect") .attr("x", -15) .attr("y", -15) .attr("width", 30) .attr("height", 30); g.append("text") .attr("class", "text") .attr("dx", "0") .attr("dy", ".35em") .attr("text-anchor", "middle") .text(function(d) {return ""+d;}); g.attr("transform", function(d, i) { var y = Math.floor(i/10); return "translate(" + (i%10*30) + "," + (yoffset+y*40) +")"; }); return yoffset + Math.max(Math.floor(slots.length/10),1) * 40; } function updateD3(x, clean, duration) { var stack = x.lookupInScope("queue"); var poppedValue = x.lookupInScope("popped"); var slots = svg.selectAll(".slot.left") .data(stack.left); var slotsR = svg.selectAll(".slot.right") .data(stack.right); var y = drawArray(slots, "left", 20); rightLabel.attr("dy", y) y = drawArray(slotsR, "right", y+20); returnText.text(function(){return poppedValue !== poppedMarker? "Popped: "+ poppedValue : ""}); returnText.attr("dy", y); } function update(n, x, isRunning, duration) { // Update the d3 visualisation. updateD3(x, false, duration); document.getElementById("addButton").disabled = isRunning; document.getElementById("removeButton").disabled = isRunning; } function addNode() { var data = document.getElementById('input').value; data = data.replace(/"/g, '\\\"'); runScript("queue.enqueue(\""+ data +"\")"); } function removeNode() { runScript("popped = queue.dequeue()"); } window.onload = function() { setup(); }; </script> </head> <body style="height:480px"> <button id="addButton" onclick="addNode()">Enqueue</button><button id="removeButton" onclick="removeNode()">Dequeue</button> <input id="input" value="7"><br><br> <div id=result> </div> </body> </html> </syntax>

algorithm/queue_array-based.txt · Last modified: 2016/04/03 00:06 by will