Understanding JavaScript Call Stack and Stack Data Structure
JavaScript is a single-threaded language, meaning it uses a single call stack to manage the execution context of functions.
Whenever a function is called, the JavaScript engine creates a global execution context and pushes it onto the call stack. When a new function is invoked, a function-specific execution context is added on top of the global one.
The call stack follows the Last In, First Out (LIFO) order, meaning the most recent function added will be the first to be removed once it completes execution.
Here's a simple example of a stack data structure implemented in JavaScript. You can execute this code in any JavaScript environment and observe the console output:
class Stack {
constructor() {
this.count = 0;
this.storage = {};
}
size() {
return this.count;
}
push(item) {
this.storage[this.count] = item;
this.count++;
}
peek() {
return this.isEmpty() ? undefined : this.storage[this.count - 1];
}
pop() {
if (this.isEmpty()) return undefined;
this.count--;
const result = this.storage[this.count];
delete this.storage[this.count];
return result;
}
isEmpty() {
return this.count === 0;
}
}
const stack = new Stack();
console.log(stack.size()); // 0
stack.push(1);
stack.push(2);
console.log(stack.peek()); // 2
console.log(stack.pop()); // 2
console.log(stack.size()); // 1
//Feel free to try it out and check the results!
> Breakdown of the time complexities:
Push (Adding an item): O(1)
The push operation simply adds an item to the top of the stack, and this happens in constant time, since it involves a direct assignment and increment of a counter.
Pop (Removing the top item): O(1)
Similarly, the pop operation just removes the item from the top of the stack, deletes the reference, and decrements the counter, all of which occur in constant time.
Peek (Retrieving the top item): O(1)
The peek operation only accesses the top item without modifying the stack, so it's also constant time.
Size (Retrieving the stack size): O(1)
Since the size of the stack is stored in a variable and updated with each push or pop, retrieving the size is a constant time operation.
Thus, all the primary operations on a stack—push, pop, peek, and size—have a time complexity of O(1), making the stack a very efficient data structure for managing collections of items where only the top item is of interest.
Any comments or suggestions are welcome
Top comments (0)