Data Structures - Overview

README.md

Week 0 D4 - Data Structures

Overview

Data structures

• A

Types

• Queues A queue works like a line for an amusement park ride -- people enter at the end of the queue and leave from the front (FIFO: first in, first out).
• Stacks A stack works like a stack of plates -- plates are added and removed from the the top of the stack (LIFO: last in, first out).

Use for:

• Arrays Use for constant time lookup, linerar insertion/removal
• Singly LinkedLists Constant time insert, linear time lookup and removal
• Doubly LinkedLists Constant time insert/removal, but each node takes up a little more space
• Trees Constant time insert/removal, but each node takes up a little more space

Style & Syntax Considerations

Instantiation Style	Pro's	Con's
Functional	You believe your solution to be fully complete and meeting the specified requirements.
Functional-shared	Your solution is well on its way to being complete, but you ran out of time or can't remember exactly how to do one particular aspect. You believe anyone who understands the problem well would endorse your solution as the right one, and know pretty clearly how to finish up any last touches.
Prototypal	You have the right idea and were heading in a good direction. Covers everything between Mostly Complete and Attempted.
Pseudoclassical	You were very challenged by the prompt and had trouble making any significant progress on the problem, but wrote at least one meaningful line of code that appears to be a genuine attempt.

Considering Complexity

Def algorithm - The system or plan you use to arrive at a solution

• As the size of the problem gets bigger, the cost might grow quickly/slowly/not at all.
• Time complexity - Mathematical comparison between different plans, or algorithm.
• Cheat sheet- bigocheatsheet.com - An approximation of time complexity, describes worst-case performance for large n.

Approaches to complexity

Name	Big-O Notation	Operations for n items	Approach	Example
Constant	O(1)	1	Compare first & last numbers	Array lookup, hash table insertion
Logarithmic	O(log n)	1	Def	Def
Linear	O(n)	2n	Find largest & smallest numbers	Finding index of an element in an array
Quadratic	O(n^2)	n^2	Constant time operation inside two nested for-loops.
Exponential	O(c^n)	n^2	Def	Guessing an n-character long password

functional-queue.js

var Queue = function() {
  var someInstance = {};
  var storage = {};
  var enq = 0;
  var deq = 0; 

  someInstance.enqueue = function(value) {
    //Add a string to the back of the queue
    storage[enq] = value;
    enq ++;
  };

  someInstance.dequeue = function() {
    //Remove and return the string at the front of the queue
  if ( enq - deq) {
    var result = storage[deq];
    delete storage[deq];
    deq++;
    return result;
    }
  };

  someInstance.size = function() {
    return enq - deq;
  };

  return someInstance;
};

functional-shared-queue.js

var Queue = function() {
  // Hey! Rewrite in the new style. Your code will wind up looking very similar,
  // but try not not reference your old code in writing the new style.
  var someInstance = {
  	//don't mess with the variables, show by _
  	_storage: {},
  	_back: 0,
  	_front: 0,
  };

  _.extend(someInstance, queueMethods);

  return someInstance;
};

var queueMethods = {
	//Use .this
	enqueue : function(value) {
		//Add a string to the back of the queue
		this.storage[this.back] = value;
		this.back ++;
	},
 
	dequeue : function() {
		// Remove and return the string at the front of the queue
		if (this.front < this.back) {
			var value = this.storage[this.front];
			delete this.storage[this.front];
			this.front++;
			return value;
		}
	},

	size : function() {
		//Return the number of items in the queue
		return this.back - this.front ;
	}
};

functional-shared-stack.js

var Stack = function() {
  var someInstance = {
    storage : [],
    counter : 0
  };

  _.extend(someInstance, stackMethods);
  return someInstance;
}

var stackMethods = {
  push : function(value){
    this.storage[this.counter] = value;
    this.counter ++;
  },

  pop : function () {
    if (this.counter > 0) {
    this.counter --;
    var value = this.storage[this.counter];
    delete this.storage[this.counter];
    return value;
    }
  },

  size : function() {
    return this.counter;
  }
};

functional-stack.js

*/
var Stack = function() {
  var someInstance = {};

  var storage = {};
  var counter = 0;
  
  someInstance.push = function(value) {
    //Add new items to the stack
    storage[counter] = value;
    counter ++;
  };

  someInstance.pop = function() {
    //Pop - Removes the last element of the stack
    if (counter > 0) {
    counter--;
    var value = storage[counter];
    delete storage[counter];
    return value;
    }
  };

  someInstance.size = function() {
    return counter;
  };

  return someInstance;
};