User Tools

Site Tools


This is an old revision of the document!


λ 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 reverse the right stack onto it. this.left = this.right.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> /* Unit tests… function testA() { if (!ok) { throw "Not ok." } } */ </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", "0") .attr("dy", "40"); } var poppedMarker = {}; function globals() { // Return a unique marker that enables to identify when popped has not been set. return {"popped": poppedMarker}; } function updateD3(x, clean, duration) { var stack = x.lookupInScope("queue"); var poppedValue = x.lookupInScope("popped"); var slots = svg.selectAll(".slot") .data(stack.array); slots.exit().remove(); // Create the array var g = slots.enter() .append("g") .attr("class", "slot"); 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) + "," + y*40 +")"; }); returnText.text(function(){return poppedValue !== poppedMarker? "Popped: "+ poppedValue : ""}); returnText.attr("transform", function() { var y = Math.floor(stack.array.length/10); return "translate(0," + y*40 +")"; }); } 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.1459665399.txt.gz · Last modified: 2016/04/02 23:36 by will