Implementing Stack and Queue in JavaScript for the Shunting-Yard Algorithm

Product Support
, ,
#1

How do you implement a Stack and a Queue in JavaScript? What is the best way to create these data structures, considering I’m looking to use them for the shunting-yard algorithm? Specifically, how can I effectively implement a javascript queue alongside the stack?

#2

Starting with the basics: you can easily implement a stack and a javascript queue in JavaScript using arrays. This is both intuitive and practical for most uses. Here’s how you’d set it up:

Stack: You can leverage the push and pop methods, which allow for last-in-first-out (LIFO) functionality. Here’s a quick example:

class Stack {
  constructor() {
    this.items = [];
  }
  push(element) {
    this.items.push(element);
  }
  pop() {
    if (this.isEmpty()) return null;
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  size() {
    return this.items.length;
  }
}

Queue: For a javascript queue, you can use push to add elements at the end and shift to remove them from the front, providing first-in-first-out (FIFO) functionality.

class Queue {
  constructor() {
    this.items = [];
  }
  enqueue(element) {
    this.items.push(element);
  }
  dequeue() {
    if (this.isEmpty()) return null;
    return this.items.shift();
  }
  front() {
    return this.items[0];
  }
  isEmpty() {
    return this.items.length === 0;
  }
  size() {
    return this.items.length;
  }
}

Arrays keep things simple and fast enough for most cases, but they may struggle with efficiency on large datasets due to frequent shifts in the queue.

#3

I’ve worked with stacks and queues in high-frequency applications, and when performance matters, I’d suggest using linked lists for both structures instead of arrays. This approach optimizes operations like insertion and deletion, which is especially useful in algorithms like the shunting-yard.

Here’s how to implement a Stack using a linked list:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class Stack {
  constructor() {
    this.top = null;
  }
  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
  }
  pop() {
    if (this.isEmpty()) return null;
    const value = this.top.value;
    this.top = this.top.next;
    return value;
  }
  isEmpty() {
    return this.top === null;
  }
}

For a Queue, linked lists are particularly beneficial because enqueuing and dequeuing don’t require shifting the entire array, which makes them more memory-efficient for large queues:

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
  }
  enqueue(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.front = this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }
  dequeue() {
    if (this.isEmpty()) return null;
    const value = this.front.value;
    this.front = this.front.next;
    if (this.front === null) this.rear = null; // Queue is empty now
    return value;
  }
  isEmpty() {
    return this.front === null;
  }
}

This linked-list approach is a great choice when implementing a javascript queue or stack in a performance-sensitive context.

#4

For those who want a quick and straightforward approach, JavaScript’s built-in structures like Array offer a practical solution. I’ve worked with these, especially when applying data structures for algorithms like shunting-yard, and they’re perfectly capable for small to medium-scale use cases.

To keep it simple, here’s an example of using JavaScript’s array functions to mimic stack and javascript queue operations:


const stack = [];

const queue = [];

// Stack operations

stack.push('item1');

stack.push('item2');

const poppedItem = stack.pop();

// Queue operations

queue.push('item1'); // enqueue

const dequeuedItem = queue.shift(); // dequeue

While this approach is effective, there’s a trade-off in performance if your queue grows large, since shift requires re-indexing the array. If that becomes a bottleneck, consider switching to a linked-list-based queue to handle larger data more efficiently.

Using these built-in methods provides an easy way to implement a javascript queue and stack without additional classes or linked lists.