How can you implement a Stack and a Queue in JavaScript?
What is the most effective way to create these data structures? I need them for the shunting-yard algorithm, specifically focusing on the JavaScript queue.
You can use JavaScript arrays to implement both Stack and Queue due to their built-in methods.
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
return this.items.shift(); // Removes the first element
}
peek() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
}
A more complex but efficient way to implement Stack and Queue is by using linked lists.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
Stack Implementation:
class Stack {
constructor() {
this.top = null;
}
push(data) {
const newNode = new Node(data);
newNode.next = this.top;
this.top = newNode;
}
pop() {
if (this.isEmpty()) return null;
const poppedNode = this.top;
this.top = this.top.next;
return poppedNode.data;
}
peek() {
return this.top ? this.top.data : null;
}
isEmpty() {
return this.top === null;
}
}
Queue Implementation:
class Queue {
constructor() {
this.front = null;
this.rear = null;
}
enqueue(data) {
const newNode = new Node(data);
if (this.isEmpty()) {
this.front = this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
}
dequeue() {
if (this.isEmpty()) return null;
const dequeuedNode = this.front;
this.front = this.front.next;
if (!this.front) this.rear = null; // If the queue is now empty
return dequeuedNode.data;
}
peek() {
return this.front ? this.front.data : null;
}
isEmpty() {
return this.front === null;
}
}
If you prefer not to implement your own data structures, you can use JavaScript’s built-in data structures like Array for simple use cases.
const stack = [];
stack.push(1); // Push
stack.push(2);
const topElement = stack.pop(); // Pop
Using Array for Queue:
const queue = [];
queue.push(1); // Enqueue
queue.push(2);
const firstElement = queue.shift(); // Dequeue