-
Notifications
You must be signed in to change notification settings - Fork 98
Stack
In computer science, a stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop. The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure. In a LIFO data structure, the last element added to the structure must be the first one to be removed. This is equivalent to the requirement that, considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack.
Wikipedia
var stackA = new Stack(); //an empty stack
var stackB = new Stack(0, 1, 2, 3); //stackB contains (from the top) 3, 2, 1, 0
var stackC = new Stack(Range(0, 3)); //stackC contains (from the top) 3, 2, 1, 0This method returns an iterator for scanning the stack. The iterator is useful in order to get a full decoupling in your classes. This avoid, to the class that uses the iterator, to know what type of data structure stores the data.
var stack = new Stack();
var it = stack.getIterator();
for(it.first(); !it.isDone(); it.next()) {
var item = it.getItem();
//do something
}The iterator starts from the top of the stack.
This method pushes the item at the top of the stack. The item could be whatever you want.
var stack = new Stack();
stack.push(4); //stack contains (from the top) 4
stack.push(2); //stack contains (from the top) 2, 4This method pushes the items at the top of the stack. The items could be whatever you want.
var stack = new Stack();
stack.multiPush([4, 2]); //stack contains (from the top) 2, 4
stack.multiPush([5, 6]); //stack contains (from the top) 6, 5, 2, 4This method pops the item at the top of the stack. The item is returned.
var stack = new Stack(4, 2); //stack contains (from the top) 2, 4
stack.pop(); //2 and stack contains 4In this case the method require to restore indexes of the array that mantains the items of the stack.
This method pops the first times items at the top of the stack. The items are returned as an array.
var stack = new Stack(6, 8, 4, 2); //stack contains (from the top) 2, 4, 8, 6
stack.multiPop(2); //[2, 4] and stack contains (from the top) 8, 6This method takes the item at the top of the stack without removing it.
var stack = new Stack(6, 8, 4, 2); //stack contains (from the top) 2, 4, 8, 6
stack.peek(); //2 and stack contains (from the top) 2, 4, 8, 6This method empty the stack.
var stack = new Stack(6, 8, 4, 2);
stack.clear(); //the stack is emptyThis method checks if the stack contains an item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method checks if the item is simply contained in the stack.
var stack = new Stack(6, 8, 4, 2);
stack.contains(4); //true
stack.contains(1); //falseIf you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var stack = new Stack(6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
stack.contains(null, callback); //trueIn this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var stack = new Stack(itemA, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
stack.contains(null, callback); //trueThis method execute the callback function for each item stored in the stack. The callback must accept the item the iteration is working on. The callback must also return a value to assign to the item.
var stack = new Stack(6, 8, 4, 2);
var callback = function(item) { //this function returns the square for each item
return item * item;
};
stack.execute(callback); //stack contains (from the top) 4, 16, 64, 36In this example we deal with more complex items.
var stack = new Stack(0, 1);
var callback = function(item) { //this function encapsulate each item into an object
return {x: item, y: item + 2};
};
stack.execute(callback); //stack contains (from the top) {x: 1, y: 3}, {x: 0, y: 2}This method returns the item at position index starting from the top of the stack. So index 0 will be for the item at the top of the stack, 1 is for the second and so on.
var stack = new Stack(6, 8, 4, 2);
stack.getItem(0); //2
stack.getItem(1); //4This method returns the length of the stack so the number of items stored.
var stack = new Stack();
stack.getLength() //0 - the stack is empty
stack.multiPush([6, 8, 4, 2]);
stack.getLength(); //4This method checks if the stack is empty or not.
var stack = new Stack();
stack.isEmpty() //true
stack.multiPush([6, 8, 4, 2]);
stack.isEmpty(); //falseThis method returns all the items that satisfies the condition represented by the callback. The callback must accept the item the iteration is working on. The method starts from the top of the stack.
var stack = new Stack(6, 8, 4, 2);
var callback = function(item) { //this function checks if the item is lower than 4 or greater than 6
return item < 4 || item > 6;
};
stack.filter(callback); //[2, 8];In this example we deal with more complex items.
var itemA = {parent: null, item: 0};
var itemB = {parent: itemA, item: 1};
var itemC = {parent: itemB, item: 2};
var itemD = {parent: null, item: 3};
var stack = new Stack(itemA, itemB, itemC, itemD);
var callback = function(item) { //this function checks if itemA is in the same hierarchy of the item
while(item.parent || item === itemA)
item = item.parent;
return item === itemA;
};
stack.filter(callback); //[itemC, itemB, itemA]This method returns the first position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the first position where the item is stored. If nothing has been found, the method returns -1, otherwise the position relates to the top of the stack.
var stack = new Stack(6, 8, 4, 2);
stack.indexOf(4); //1
stack.indexOf(5); //-1If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var stack = new Stack(6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
stack.indexOf(null, callback); //0In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var stack = new Stack(itemA, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
stack.indexOf(null, callback); //0This method returns the last position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the last position where the item is stored. If nothing has been found, the method returns -1, otherwise the position is relates to the top of the stack.
var stack = new Stack(6, 2, 4, 8, 6, 8, 4, 2);
stack.lastIndexOf(4); //5
stack.lastIndexOf(5); //-1If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var stack = new Stack(6, 2, 4, 8, 6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
stack.lastIndexOf(null, callback); //6In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var stack = new Stack(itemA, itemB, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
stack.lastIndexOf(null, callback); //1This method returns all the positions of the items that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns all the positions where the item is stored. The positions relate to the top of the stack.
var stack = new Stack(6, 2, 4, 8, 6, 8, 4, 2);
stack.allIndexesOf(4); //[1, 5]
stack.allIndexesOf(5); //[]If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var stack = new Stack(6, 2, 4, 8, 6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
stack.allIndexesOf(null, callback); //[0, 1, 5, 6]In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var stack = new Stack(itemA, itemB, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
stack.allIndexesOf(null, callback); //[0, 1]This method returns a clone of the stack. The items are cloned only if there's a method clone() to invoke, otherwise they will be shared with the old stack. This problem there is not if items are not object.
var stack = new Stack(6, 8, 4, 2);
var clone = stack.clone(); //clone contains (from the top) 2, 4, 8, 6This method returns a clone of the stack containing only one copy of the same item. The items are cloned only if there's a method cloneDistinct() to invoke or at least a method clone(), otherwise they will be shared with the old stack. This problem there is not if items are not object.
var stack = new Stack(2, 8, 4, 6, 8, 4, 2, 6);
var clone = stack.cloneDistinct(); //clone contains (from the top) 6, 2, 4, 8m: the number of distinct elements stored in the stack. The time required depends strongly from the number of items duplicated. If the number of items duplicated is very high, then m tend to be near 1 (when the stack contains only one distinct item) so complexity will be O(n). If the number of items duplicated is very low, then m tend to be near n (when the stack doesn't contain any duplicated items) so complexity will be O(n2).