User Tools

Site Tools


λ Stack array-based

======= Algorithm ======= <syntax js> function Stack() { this.array = []; } Stack.prototype = { // Adds new data to the top of the stack. push: function(data) { this.array[this.array.length] = data; // Array length is automatically increased. }, // Removes and returns the top of the stack. pop: function() { var popped = null; if (this.array.length > 0) { popped = this.array[this.array.length-1]; this.array.length--; } return popped; } } </syntax> ======= Support ======= <syntax js> // Initial starting stack. stack = new Stack(); stack.push("A"); stack.push("B"); stack.push("C"); function preRun() { if (!(stack instanceof Stack)) { // Copy the stack from data - used for web-workers. var mystack = new Stack(); mystack.array = stack.array; // Replace the global 'stack' with the converted one. stack = mystack; } } </syntax> ======= Tests ======= <syntax js> function testPush() { var s = new Stack(); s.push(1); s.push(2); s.push(3); assert(s.pop() === 3); assert(s.pop() === 2); assert(s.pop() === 1); assert(s.pop() === null, "End of stack."); }</syntax> ======= Options ======= <syntax js> { "title": "Stack array-based", "height": "320px", "preRunSource": true, "persistentGlobals": ["stack"] } </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("stack"); 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("stack.push(\""+ data +"\")"); } function removeNode() { runScript("popped = stack.pop()"); } window.onload = function() { setup(); }; </script> </head> <body style="height:480px"> <button id="addButton" onclick="addNode()">Push</button><button id="removeButton" onclick="removeNode()">Pop</button> <input id="input" value="7"><br><br> <div id=result> </div> </body> </html> </syntax>

algorithm/stack_array-based.txt · Last modified: 2015/02/02 08:28 (external edit)