/
bkup.js
118 lines (96 loc) · 3.33 KB
/
bkup.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/******
* dstruct.js
* Created by: Chien-Hung Chen
* Created with the intent of offering special data structures for javascript users
*/
/******
* Binary Search Tree
* Methods implemented:
* enqueue, push, add; dequeue, pop, remove; clear; size, length, count; contains; isempty; peek, front; back
*/
var bstNode = function(v, l, r){
this.value = v;
this.left = l;
this.right = r;
}
function BinarySearchTree(rootval){
var root;
if(rootval == undefined || rootval == undefined)
root = new bstNode(null, null, null);
else
root = new bstNode(rootval, null, null);
//returns the root of the tree
this.getroot = function() { return root; }
//sets the root of the tree
this.setroot = function(r) { root = r; }
}
/******
* Queue - FIFO
* Methods implemented:
* enqueue, push, add; dequeue, pop, remove; clear; size, length, count; contains; isempty; peek, front; back
*/
function Queue(){
//initializing the queue
var queue = [];
//enqueue and push adds the object on to the end
this.enqueue = function(obj) { queue.push(obj); }
this.push = this.enqueue;
this.add = this.enqueue;
//dequeues an obj and returns the object dequeued
this.dequeue = function() {
if (queue.length == 0)
return undefined;
var obj = queue[0];
queue = queue.slice(1);
return obj;
}
this.pop = this.dequeue;
this.remove = this.dequeue;
//empty the queue, there's a lot of discussion as to whether to use arr.length = 0 or arr = []; see: http://jsperf.com/emptying-arrays
this.clear = function() { queue.length = []; }
//return size of the queue
this.size = function() { return (queue.length); }
this.length = this.size;
this.count = this.size;
//returns whether or not the queue contains obj
this.contains = function(obj) {
for(o in queue) { if(queue[o] === obj) return true; }
return false;
}
//return whether or not the queue is empty
this.isempty = function() { return queue.length == 0; }
//returns the item at the front of the queue without dequeuing it
this.peek = function() { return ((queue.length > 0) ? queue[0] : undefined); }
this.front = this.peek;
//return the item at the end of the queue
this.back = function() { return ((queue.length > 0) ? queue[queue.length - 1] : undefined); }
}
/******
* Stack - LIFO
* Methods implemented:
* push, add; pop; clear; size, length, count; contains; isempty; peek;
*/
function Stack(){
//initializing the queue
var stack = [];
//push the obj on to the top of the stack
this.push = function(obj) { stack.push(obj); }
this.add = this.push;
//pops an obj from the top of the stack and returns the object popped
this.pop = function() { return stack.pop(); }
//empty the stack, there's a lot of discussion as to whether to use arr.length = 0 or arr = []; see: http://jsperf.com/emptying-arrays
this.clear = function() { stack.length = 0; }
//return size of the stack
this.size = function() { return (stack.length); }
this.length = this.size;
this.count = this.size;
//returns whether or not the stack contains obj
this.contains = function(obj) {
for(o in stack) { if(stack[o] === obj) return true; }
return false;
}
//return whether or not the stack is empty
this.isempty = function() { return stack.length == 0; }
//returns the item at the top of the stack without popping it
this.peek = function() { return ((stack.length > 0) ? stack[stack.length-1] : undefined); }
}