How do you implement a Stack and a Queue in JavaScript?
Categories:
Implementing Stacks and Queues in JavaScript
Explore the fundamental data structures: Stacks and Queues. Learn their principles and practical implementations in JavaScript for efficient data management.
Stacks and Queues are essential linear data structures that manage elements based on specific access principles. Understanding their implementation is crucial for efficient algorithm design and problem-solving in computer science. This article will guide you through their concepts and provide practical JavaScript implementations.
Understanding Stacks: LIFO Principle
A Stack is a collection of elements that follows the Last In, First Out (LIFO) principle. Imagine a stack of plates; you can only add a new plate to the top, and you can only remove the topmost plate. This means the last element added is always the first one to be removed. Common operations include push (add an element to the top), pop (remove the top element), peek (view the top element without removing it), and isEmpty (check if the stack is empty).
LIFO (Last In, First Out) principle of a Stack
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) {
return "Underflow";
}
return this.items.pop();
}
peek() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
printStack() {
let str = "";
for (let i = 0; i < this.items.length; i++) {
str += this.items[i] + " ";
}
return str.trim();
}
}
// Example Usage:
const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.printStack()); // 10 20 30
console.log(stack.peek()); // 30
console.log(stack.pop()); // 30
console.log(stack.printStack()); // 10 20
console.log(stack.size()); // 2
A basic JavaScript implementation of a Stack using an array.
push and pop operations, avoiding potential array reallocations.Understanding Queues: FIFO Principle
A Queue is another linear data structure that adheres to the First In, First Out (FIFO) principle. Think of people waiting in line at a grocery store; the first person to join the line is the first one to be served. Elements are added to the 'rear' (enqueue) and removed from the 'front' (dequeue). Key operations include enqueue (add an element to the rear), dequeue (remove the front element), front (view the front element without removing it), rear (view the rear element), and isEmpty (check if the queue is empty).
FIFO (First In, First Out) principle of a Queue
class Queue {
constructor() {
this.items = {};
this.head = 0;
this.tail = 0;
}
enqueue(element) {
this.items[this.tail] = element;
this.tail++;
}
dequeue() {
if (this.isEmpty()) {
return "Underflow";
}
const element = this.items[this.head];
delete this.items[this.head];
this.head++;
return element;
}
front() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.items[this.head];
}
rear() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.items[this.tail - 1];
}
isEmpty() {
return this.head === this.tail;
}
size() {
return this.tail - this.head;
}
printQueue() {
let str = "";
for (let i = this.head; i < this.tail; i++) {
str += this.items[i] + " ";
}
return str.trim();
}
}
// Example Usage:
const queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue('A');
queue.enqueue('B');
queue.enqueue('C');
console.log(queue.printQueue()); // A B C
console.log(queue.front()); // A
console.log(queue.dequeue()); // A
console.log(queue.printQueue()); // B C
console.log(queue.size()); // 2
console.log(queue.rear()); // C
A JavaScript implementation of a Queue using an object for efficient dequeue operations.
shift() for dequeue, be aware that shift() can be an O(N) operation in JavaScript as it re-indexes all subsequent elements. The object-based implementation shown above provides O(1) for both enqueue and dequeue.