Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell
Today, we're going to explore two essential data structures: stacks and queues. We'll dive into their concepts, use cases, and implement them in JavaScript using both classical and prototype-based approaches.
Stacks: Last In, First Out (LIFO)
Imagine a stack of pancakes – the last one you put on top is the first one you'll eat. That's exactly how a stack data structure works. It follows the Last In, First Out (LIFO) principle.
Key Operations
-
push(item): Add an item to the top of the stack -
pop(): Remove the top item from the stack -
peek(): Return the top item without removing it -
isEmpty(): Check if the stack is empty
Use Cases
Stacks are particularly useful in scenarios involving:
- Recursive algorithms
- Undo mechanisms in text editors
JavaScript Implementation
Classical OOP
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) {
return "Stack is empty";
}
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;
}
clear() {
this.items = [];
}
}
Prototype-Based
function Stack() {
this.items = [];
}
Stack.prototype.push = function(element) {
this.items.push(element);
};
Stack.prototype.pop = function() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items.pop();
};
Stack.prototype.peek = function() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items[this.items.length - 1];
};
Stack.prototype.isEmpty = function() {
return this.items.length === 0;
};
Stack.prototype.size = function() {
return this.items.length;
};
Stack.prototype.clear = function() {
this.items = [];
};
Queues: First In, First Out (FIFO)
Now, let's shift our focus to queues. Unlike stacks, queues follow the First In, First Out (FIFO) principle. Think of a line at a concert venue – the first person to arrive is the first one to enter.
Key Operations
-
enqueue(item): Add an item to the end of the queue -
dequeue(): Remove the first item from the queue -
peek(): Return the first item without removing it -
isEmpty(): Check if the queue is empty
Use Cases
Queues are commonly used in:
- Breadth-first search algorithms
- Task scheduling
JavaScript Implementation
Classical OOP
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
this.start = null;
this.end = null;
this.size = 0;
}
enqueue(element) {
const newNode = new Node(element);
if (this.isEmpty()) {
this.start = newNode;
this.end = newNode;
} else {
this.end.next = newNode;
this.end = newNode;
}
this.size++;
}
dequeue() {
if (this.isEmpty()) {
return "Queue is empty";
}
const removedData = this.start.data;
this.start = this.start.next;
this.size--;
if (this.isEmpty()) {
this.end = null;
}
return removedData;
}
peek() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.start.data;
}
isEmpty() {
return this.size === 0;
}
getSize() {
return this.size;
}
clear() {
this.start = null;
this.end = null;
this.size = 0;
}
}
Prototype-Based
function Node(data) {
this.data = data;
this.next = null;
}
function Queue() {
this.start = null;
this.end = null;
this.size = 0;
}
Queue.prototype.enqueue = function(element) {
const newNode = new Node(element);
if (this.isEmpty()) {
this.start = newNode;
this.end = newNode;
} else {
this.end.next = newNode;
this.end = newNode;
}
this.size++;
};
Queue.prototype.dequeue = function() {
if (this.isEmpty()) {
return "Queue is empty";
}
const removedData = this.start.data;
this.start = this.start.next;
this.size--;
if (this.isEmpty()) {
this.end = null;
}
return removedData;
};
Queue.prototype.peek = function() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.start.data;
};
Queue.prototype.isEmpty = function() {
return this.size === 0;
};
Queue.prototype.getSize = function() {
return this.size;
};
Queue.prototype.clear = function() {
this.start = null;
this.end = null;
this.size = 0;
};
Performance Analysis
Both stacks and queues offer time complexity for their core operations (push/pop for stacks, enqueue/dequeue for queues) when implemented efficiently. This makes them highly performant for their specific use cases.
They both provide elegant solutions to many common programming problems and form the basis for more complex data structures and algorithms. By understanding and implementing these structures in JavaScript, you're well-equipped to tackle a wide range of Leetcode/Algorithm problems 😎.
Top comments (0)