How do you implement a Stack and a Queue in JavaScript?
var stack = [];
stack.push(2); // stack is now [2]
stack.push(5); // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i); // displays 5
var queue = [];
queue.push(2); // queue is now [2]
queue.push(5); // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i); // displays 2
taken from "9 JavaScript Tips You May Not Know"
Implementation of .pop() in Stacks and dequeue in Queues
why do we keep the last element that was popped off?
If we leave this off in the array, won't this take up more memory?
Yes, that implementation never shrinks the array size. The array will remain at its largest length. But, the values that have been popped off will be reused/ovewritten when new values are pushed onto the stack. This will not shrink the array when you pop values off it. That may or may not take more memory. Arrays are implemented internally with a bit of extra slack in them so that every time you increase or decrease their length by a small bit, they don't have to reallocate a new sized memory and copy the existing array over to the new block. So, leaving a few extra elements on the end of the array won't necessarily change things much or at all. Now, if you pushed thousands of elements onto the stack and then popped them all off, then you would indeed have a bunch of unused memory sitting in your empty stack and that would be inefficient. So, it really depends upon how much you're going to push onto the stack.
You could fairly easily insert a check for how many extra bytes are sitting on the end and (if more than some threshold), then reset the length of your array to allow the system to reallocate a smaller array. Unless you have a zillion of these stacks or unless you put a really large number of items on the stack, it's all probably inconsequential in the grand scheme of things, but if you had a proven reason that it would matter to your app, you could optimize it to use less memory in some circumstances.
For dequeue, I am simply just replacing the value with null instead of really getting [2,3], when removing the first item in the queue.
Same as Stacks, why do we have to keep a value in place?
The queue implementation seems more problematic as its implementation seems like it would grow larger forever since this.first and this.last are only ever incremented. There is no queue implementation reason to keep the old data. To keep from growing forever, this would need to copy down and resize the array or switch to more of a linked list type implementation where you can freely just remove the first link or add the last link without the restraints of an array.
If the values in the stack or queue are object references, then you can mitigate their impact by setting their stack or queue value to null after popping or dequeing them. This will allow the objects to be garbage collected when nobody else is using them.
A simple queue that doesn't accumulate memory would be like this:
const Queue = function() {
this.store = []; // stores data in an array
}
Queue.prototype.enqueue = function(value) {
// add to end of the queue
this.store.push(value);
}
Queue.prototype.dequeue = function() {
// remove oldest value from the start of the queue
return this.store.shift();
}
How to optimally implement Stack and Queue operations in this B+tree?
But my question is, is there a better more optimized way to do this? Rather than traversing the whole tree to find the first or last item, maybe we could cache them?
You could do some sort of caching. But do realise that "traversing the whole tree" is not as bad as it sounds. It is about traversing from the root to a leaf, so the number of node visits is equal to the number of levels. The number of levels of the tree is O(logn). To get a tree with 10 levels, you would have to insert hundreds of billions of values.
Still, you can avoid that downward traversal by making use of the linked list that is maintained at the bottom level. The code already has a reference to the left most node in that list (this.first), and we could add a reference to the last one and keep it in sync.
Also, we could alter removeItemAt so that it also returns the deleted value. That way you don't have to do a separate call to getItemAt.
The changes to make
To make removeItemAt return the removed value, add a line near the start of the function:
removeItemAt(offset) {
let [node, index] = this.locate(offset);
if (index >= node.childCount) return;
let value = node.children[index]; // <-- get deleted item (to return it)
... and change each of the 4 return statements to:
return value;
In the constructor, define this.last:
this.first = this.last = this.root; // Head & tail of doubly linked list at bottom level
...and potentially assign to it when inserting a node in insertItemAt:
let sibling = new Node(childCount);
if (node === this.last) this.last = sibling; // <----
...and assign to it when removing the last node in removeItemAt (near the end):
left.moveFromNext(right.childCount);
if (right === this.last) this.last = left; // <----
Then the locate method could detect a situation where the returned node should be either the first or last node in the bottom layer of the tree:
// Normalise argument
offset = offset < 0 ? Math.max(0, node.treeSize + offset) : Math.min(offset, node.treeSize);
// Add these Shortcuts:
if (offset < this.first.childCount) return [this.first, offset];
if (offset >= node.treeSize - this.last.childCount) {
return [this.last, offset - node.treeSize + this.last.childCount];
}
Finally, we'll want to add these methods:
push(value) {
this.insertItemAt(this.root.treeSize, value);
}
pop() {
return this.removeItemAt(-1);
}
unshift(value) {
this.insertItemAt(0, value);
}
shift() {
return this.removeItemAt(0);
}
Implementation - snippet
Here is the code with those changes, and the test method tailored to test these new methods:
class Node {
constructor(capacity) {
// Mimic fixed-size array (avoid accidentally growing it)
this.children = Object.seal(Array(capacity).fill(null));
this.childCount = 0; // Number of used slots in children array
this.treeSize = 0; // Total number of values in this subtree
// Maintain back-link to parent.
this.parent = null;
// Per level in the tree, maintain a doubly linked list
this.prev = this.next = null;
}
setCapacity(capacity) {
if (capacity < 1) return;
// Here we make a new array, and copy the data into it
let children = Object.seal(Array(capacity).fill(null));
for (let i = 0; i < this.childCount; i++) children[i] = this.children[i];
this.children = children;
}
isLeaf() {
return !(this.children[0] instanceof Node);
}
index() {
return this.parent.children.indexOf(this);
}
updateTreeSize(start, end, sign=1) {
let sum = 0;
if (this.isLeaf()) {
sum = end - start;
} else {
for (let i = start; i < end; i++) sum += this.children[i].treeSize;
}
if (!sum) return;
sum *= sign;
// Apply the sum change to this node and all its ancestors
for (let node = this; node; node = node.parent) {
node.treeSize += sum;
}
}
wipe(start, end) {
this.updateTreeSize(start, end, -1);
this.children.copyWithin(start, end, this.childCount);
for (let i = this.childCount - end + start; i < this.childCount; i++) {
this.children[i] = null;
}
this.childCount -= end - start;
// Reduce allocated size if possible
if (this.childCount * 2 <= this.children.length) this.setCapacity(this.children.length / 2);
}
moveFrom(neighbor, target, start, count=1) {
// Note: `start` can have two meanings:
// if neighbor is null, it is the value/Node to move to the target
// if neighbor is a Node, it is the index from where value(s) have to be moved to the target
// Make room in target node
if (this.childCount + count > this.children.length) this.setCapacity(this.children.length * 2);
this.children.copyWithin(target + count, target, Math.max(target + count, this.childCount));
this.childCount += count;
if (neighbor !== null) {
// Copy the children
for (let i = 0; i < count; i++) {
this.children[target + i] = neighbor.children[start + i];
}
// Remove the original references
neighbor.wipe(start, start + count);
} else {
this.children[target] = start; // start is value to insert
}
this.updateTreeSize(target, target + count, 1);
// Set parent link(s)
if (!this.isLeaf()) {
for (let i = 0; i < count; i++) {
this.children[target + i].parent = this;
}
}
}
moveToNext(count) {
this.next.moveFrom(this, 0, this.childCount - count, count);
}
moveFromNext(count) {
this.moveFrom(this.next, this.childCount, 0, count);
}
basicRemove(index) {
if (!this.isLeaf()) {
// Take node out of the level's linked list
let prev = this.children[index].prev;
let next = this.children[index].next;
if (prev) prev.next = next;
if (next) next.prev = prev;
}
this.wipe(index, index + 1);
}
basicInsert(index, value) {
this.moveFrom(null, index, value);
if (value instanceof Node) {
// Insert node in the level's linked list
if (index > 0) {
value.prev = this.children[index-1];
value.next = value.prev.next;
} else if (this.childCount > 1) {
value.next = this.children[1];
value.prev = value.next.prev;
}
if (value.prev) value.prev.next = value;
if (value.next) value.next.prev = value;
}
}
pairWithSmallest() {
return this.prev && (!this.next || this.next.childCount > this.prev.childCount)
? [this.prev, this] : [this, this.next];
}
toString() {
return "[" + this.children.map(v => v??"-").join() + "]";
}
}
class Tree {
constructor(nodeCapacity=32) {
this.nodeCapacity = nodeCapacity;
this.root = new Node(1);
this.first = this.last = this.root; // Head of doubly linked list at bottom level
}
locate(offset) {
let node = this.root;
// Normalise argument
offset = offset < 0 ? Math.max(0, node.treeSize + offset) : Math.min(offset, node.treeSize);
// Shortcuts
if (offset < this.first.childCount) return [this.first, offset]; // *
if (offset >= node.treeSize - this.last.childCount) {
return [this.last, offset - node.treeSize + this.last.childCount]; // *
}
while (!node.isLeaf()) {
let index = 0;
let child = node.children[index];
while (offset > child.treeSize || offset === child.treeSize && child.next) {
offset -= child.treeSize;
child = node.children[++index];
}
node = child;
}
return [node, offset];
}
getItemAt(offset) {
let [node, index] = this.locate(offset);
if (index < node.childCount) return node.children[index];
}
setItemAt(offset, value) {
let [node, index] = this.locate(offset);
if (index < node.childCount) node.children[index] = value;
}
removeItemAt(offset) {
let [node, index] = this.locate(offset);
if (index >= node.childCount) return;
let value = node.children[index]; // * get deleted item (to return it)
while (true) {
console.assert(node.isLeaf() || node.children[index].treeSize === 0);
node.basicRemove(index);
// Exit when node's fill ratio is fine
if (!node.parent || node.childCount * 2 > this.nodeCapacity) return value; // *
// Node has potentially too few children, we should either merge or redistribute
let [left, right] = node.pairWithSmallest();
if (!left || !right) { // A node with no siblings? Must become the root!
this.root = node;
node.parent = null;
return value; // *
}
let sumCount = left.childCount + right.childCount;
let childCount = sumCount >> 1;
// Check whether to merge or to redistribute
if (sumCount > this.nodeCapacity) { // redistribute
// Move some data from the bigger to the smaller node
let shift = childCount - node.childCount;
if (!shift) { // Boundary case: when a redistribution would bring no improvement
console.assert(node.childCount * 2 === this.nodeCapacity && sumCount === this.nodeCapacity + 1);
return value; // *
}
if (node === left) { // move some children from right to left
left.moveFromNext(shift);
} else { // move some children from left to right
left.moveToNext(shift);
}
return value; // *
}
// Merge:
// Move all data from the right to the left
left.moveFromNext(right.childCount);
if (right === this.last) this.last = left;
// Prepare to delete right node
node = right.parent;
index = right.index();
}
}
insertItemAt(offset, value) {
let [node, index] = this.locate(offset);
while (node.childCount === this.nodeCapacity) { // No room here
if (index === 0 && node.prev && node.prev.childCount < this.nodeCapacity) {
return node.prev.basicInsert(node.prev.childCount, value);
}
// Check whether we can redistribute (to avoid a split)
if (node !== this.root) {
let [left, right] = node.pairWithSmallest();
let joinedIndex = left === node ? index : left.childCount + index;
let sumCount = left.childCount + right.childCount + 1;
if (sumCount <= 2 * this.nodeCapacity) { // redistribute
let childCount = sumCount >> 1;
if (node === right) { // redistribute to the left
let insertInLeft = joinedIndex < childCount;
left.moveFromNext(childCount - left.childCount - +insertInLeft);
} else { // redistribute to the right
let insertInRight = index >= sumCount - childCount;
left.moveToNext(childCount - right.childCount - +insertInRight);
}
if (joinedIndex > left.childCount ||
joinedIndex === left.childCount && left.childCount > right.childCount) {
right.basicInsert(joinedIndex - left.childCount, value);
} else {
left.basicInsert(joinedIndex, value);
}
return;
}
}
// Cannot redistribute: split node
let childCount = node.childCount >> 1;
// Create a new node that will later become the right sibling of this node
let sibling = new Node(childCount);
if (node === this.last) this.last = sibling;
// Move half of node node's data to it
sibling.moveFrom(node, 0, childCount, childCount);
// Insert the value in either the current node or the new one
if (index > node.childCount) {
sibling.basicInsert(index - node.childCount, value);
} else {
node.basicInsert(index, value);
}
// Is this the root?
if (!node.parent) {
// ...then first create a parent, which is the new root
this.root = new Node(2);
this.root.basicInsert(0, node);
}
// Prepare for inserting the sibling node into the tree
index = node.index() + 1;
node = node.parent;
value = sibling;
}
node.basicInsert(index, value);
}
// * added 4 methods
push(value) {
this.insertItemAt(this.root.treeSize, value);
}
pop() {
return this.removeItemAt(-1);
}
unshift(value) {
this.insertItemAt(0, value);
}
shift() {
return this.removeItemAt(0);
}
/* Below this point: these methods are optional */
* [Symbol.iterator]() { // Make tree iterable
let i = 0;
for (let node = this.first; node; node = node.next) {
for (let i = 0; i < node.childCount; i++) yield node.children[i];
}
}
print() {
console.log(this.root && this.root.toString());
}
verify() {
// Raise an error when the tree violates one of the required properties
if (!this.root) return; // An empty tree is fine.
if (this.root.parent) throw "root should not have a parent";
// Perform a breadth first traversal
let q = [this.root];
while (q.length) {
if (q[0].isLeaf() && this.first !== q[0]) throw "this.first is not pointing to first leaf";
let level = [];
let last = null;
for (let parent of q) {
if (!(parent instanceof Node)) throw "parent is not instance of Node";
if (parent.children.length > this.nodeCapacity) throw "node's children array is too large";
if (parent.childCount > 0 && parent.childCount * 2 <= parent.children.length) throw "node's fill ratio is too low";
for (let i = parent.childCount; i < parent.children.length; i++) {
if (parent.children[i] !== null) throw "child beyond childCount should be null but is not";
}
let treeSize = parent.treeSize;
if (parent.isLeaf()) {
for (let value of parent.children.slice(0, parent.childCount)) {
if (value === null) throw "leaf has a null as value";
if (value instanceof Node) throw "leaf has a Node as value";
}
if (parent.treeSize !== parent.childCount) throw "leaf has mismatch in treeSize and childCount";
} else {
for (let node of parent.children.slice(0, parent.childCount)) {
if (node === null) throw "internal node has a null as value";
if (!(node instanceof Node)) throw "internal node has a non-Node as value";
if (node.parent !== parent) throw "wrong parent";
if (node.prev !== last) throw "prev link incorrect";
if (last && last.next !== node) throw "next link incorrect";
if (last && last.children.length + node.children.length <= this.nodeCapacity) {
throw "two consecutive siblings have a total number of children that is too small";
}
if (node.childCount * 2 < this.nodeCapacity) {
throw "internal node is too small: " + node;
}
level.push(node);
last = node;
treeSize -= node.treeSize;
}
if (treeSize) throw "internal node treeSize sum mismatches";
}
}
if (last && last.next) throw "last node in level has a next reference";
q = level;
}
}
test(count=100, option=3) {
// option:
// 0 = always insert & delete at left side (offset 0)
// 1 = always insert & delete at right side
// 2 = always insert & delete at middle
// 3 = insert & delete at random offsets
// Create array to perform the same operations on it as on the tree
let arr = [];
// Perform a series of insertions
for (let i = 0; i < count; i++) {
// Choose random insertion index
let index = Math.floor(Math.random() * (i+1));
// Perform same insertion in array and tree
if (Math.random() < 0.5) {
arr.push(i);
this.push(i);
} else {
arr.unshift(i);
this.unshift(i);
}
// Verify tree consistency and properties
this.verify();
// Verify the order of values in the array is the same as in the tree
if (arr+"" !== [...this]+"") throw i + ": tree not same as array";
}
// Perform a series of deletions and insertions
for (let i = arr.length - 1; i >= 0; i--) {
// Choose random deletion index
let index = [0, i, i >> 1, Math.floor(Math.random() * (i+1))][option];
// Perform same deletion in array and tree
if (Math.random() < 0.6) {
if (Math.random() < 0.5) {
if (arr.pop(i) !== this.pop(i)) throw "pop returns different value";
} else {
if (arr.shift(i) !== this.shift(i)) throw "shift returns different value";
}
} else {
if (Math.random() < 0.5) {
arr.push(i);
this.push(i);
} else {
arr.unshift(i);
this.unshift(i);
}
}
// Verify tree consistency and properties
this.verify();
// Verify the order of values in the array is the same as in the tree
if (arr+"" !== [...this]+"") throw "tree not same as array";
}
return this;
}
}
// Perform 1000 insertions, with either push or unshift,
// then a mix of 1000 insertions/removals, the latter with either pop or shift.
new Tree(8).test(1000);
console.log("all tests completed");Does javascript have objects/containers like stack and queues?
Actually, there is no existing object containers for the likes of stack and queue but there are a handful of techniques on how you efficiently implement them.
refer to these links:
https://chevtek.io/9-javascript-tips-you-may-not-know/
https://yuiazu.net/2019/02/19/stack-and-queue-in-javascript/
hope this helps :)
Implement queue using 2 stacks
Here is a personal example, I'm sure it could be more optimized, but it allows for queue dequeue and peek functionality in JS.
function processData(input) {
let stackOne = [];
let stackTwo = [];
let parsableInput = input.split('\n');
for(let i = 1; i < parsableInput.length; i++) {
// handle 1 push
if (parsableInput[i][0] === '1') {
enqueue(stackOne, stackTwo, parsableInput[i].slice(2));
}
// handle 2
if (parsableInput[i] === '2') {
dequeue(stackTwo);
}
// handle 3
if (parsableInput[i] === '3') {
console.log(peek(stackTwo));
}
}
}
function enqueue(stackOne, stackTwo, queuedValue) {
while(stackTwo.length !== 0) {
stackOne.push(stackTwo.pop());
}
stackOne.push(queuedValue);
while(stackOne.length !== 0) {
stackTwo.push(stackOne.pop());
}
}
function dequeue(stackTwo) {
return stackTwo.pop();
}
function peek(stackTwo) {
let stringToBeParsed = stackTwo[stackTwo.length - 1];
let parsedString = stringToBeParsed.slice(0, stringToBeParsed.length);
if (parsedString) {
return parsedString;
} else {
console.log('Error: there is nothing to peek at!');
}
}
Using Stack & Queue in functional programming (javascript)
"same input same output"
let stack = []
stack.push(1) // [1]
stack.push(1) // [1,1]
Right. Array.prototype.push is a destructive function – it mutates its input. Your stack/queue would need to be implemented using pure functions – obviously ones that don't mutate the underlying data structure ...
Binding agreement
Before we continue, let's go over the Stack contract
// stack contract
stackIsEmpty(emptyStack) => true
stackIsEmpty(stackPush(x, emptyStack)) => false
stackPop(stackPush(x, emptyStack)) => [x, emptyStack]
Any other use of these functions is undefined behaviour
- You must
stackPushthe first value ontoemptyStack - You must verify that a stack is not empty before calling
stackPopon it
The implementation you see below is just a possible implementation. The point is the implementation of Stack doesn't matter so long as the contract is fulfilled.
"But is it immutable though?"
Yes, of course, but if you must see it to believe it, have a look for yourself. We create a sample stack, s, and then we call stackPop on it twice. The result is the same for each call because we implemented an immutable data structure.
// stack data abstractionconst emptyStack = {}const stackPush = (x, xs) => f => f(x,xs)const stackPop = s => s((x,xs) => [x,xs])const stackIsEmpty = s => s === emptyStack
// stackPush does not mutate emptyStacklet s = stackPush(1, emptyStack)console.log(stackIsEmpty(emptyStack)) // true
// stackPop does not mutate slet [test1, stack1] = stackPop(s)console.log(test1, stack1) // 1 {}
// stackPop returning the same value for the same input, slet [test2, stack2] = stackPop(s)console.log(test2, stack2) // 1 {}Related Topics
How to Detect Escape Key Press with Pure Js or Jquery
JavaScript Validation for Empty Input Field
How to Prevent Default Event Handling in an Onclick Method
Add St, Nd, Rd and Th (Ordinal) Suffix to a Number
Using JavaScript to Change Website Language
Session Only Cookies with JavaScript
Appending Form Input Value to Action Url as Path
Window.Getselection() Gives Me the Selected Text, But I Want the HTML
Multiple Select Limit Number of Selection
Prevent Text Selection After Double Click
Why Would Multiple Simultaneous Ajax Calls to the Same ASP.NET MVC Action Cause the Browser to Block
Group Objects by Property in JavaScript
How to Save JSON to Local Text File
Change Form Values After Submit Button Pressed
Drawing Rotated Text on a HTML5 Canvas