How do you implement a Stack and a Queue in JavaScript?

Question

What is the best way to implement a Stack and a Queue in JavaScript?

I'm looking to do the shunting-yard algorithm and I'm going to need these data-structures.

Sestet

As a circular buffer – Headspring

Related: "Queue with O(1) enqueue and dequeue with JS arrays" codereview.stackexchange.com/questions/255698/… – Sportscast

Answer 1

var stack = [];
stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i);            // displays 5

var queue = [];
queue.push(2);         // queue is now [2]
queue.push(5);         // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i);              // displays 2

taken from "9 JavaScript Tips You May Not Know"

Garrettgarrick

I would advise caution in using queue.shift. IIRC it is not O(1), but O(n) and might be too slow if the queue gets large. – Narthex

I'd say this depends on the javascript implementation. I don't think it's defined in the javascript spec. – Intercalary

@MAK/gs: queues are dense, so most JS implementations should store the values in an actual, dynamically-sized array (what Java calls ArrayList); this means shifting will most likely involve a memmove(); you'd have to check the sources of your JS engine of choice to make sure, though... – Libbylibeccio

@polkovnikov.ph sorry, I didn't quite understand that, could you explain it in a little more extended way? My CS/programming theory is not up to scratch. Maybe write a blog post explaining this? I'm very interested to learn both the information theory and the practical side especially since I thought that jsperf was quite useful. – Groom

Array.join() is now slower than the usual '+' in JS too, this is because Array.join() doesn't receive as many optimization updates whereas '+' does... I would look into all of those tips before using them – Taste

ImmutableJs is great lib for all kind of immutable data, stacks included. And yes, it's O(1) efficiency. facebook.github.io/immutable-js/docs/#/Stack – Fawcette

tiny-queue: A simple FIFO queue implementation to avoid having to do shift() on an array, which is slow. – Mccullers

@Chev and now your link, too, is only available via wayback machine... Nietzsche would be proud – Prittleprattle

@Prittleprattle Not sure what you mean. It's working for me. chevtek.io/9-javascript-tips-you-may-not-know/#stack – Eddins

Oh, because an old comment has an old URL and you can't edit old comments. But the answer itself was edited with the correct URL lol. – Eddins

@Chev Aha, that makes sense. You should consider adding a redirect or something to unknown URLs so they don't just return ERR_CONNECTION_REFUSED :P – Prittleprattle

There actually is. It's an issue with SSL certificates and root domains and blah blah with Ghost Blog. – Eddins

Answer 2

Arrays.

Stack:

var stack = [];

//put value on top of stack
stack.push(1);

//remove value from top of stack
var value = stack.pop();

Queue:

var queue = [];

//put value on end of queue
queue.push(1);

//Take first value from queue
var value = queue.shift();

Apophysis

Array.prototype.pop does not remove the value from the top (first element) of the Array. It removes the value from the bottom (last element) of the Array. – Bendy

@MichaelGeller The top of the stack is the last element of the Array. Array push and pop methods behave just like a stack. – Cladophyll

@Cladophyll Array.prototype.pop removes the last element of the array (see developer.mozilla.org/en/docs/Web/JavaScript/Reference/…). Last in this context means the element with the highest index. An array in JS has nothing to do with a stack. It is not a stack just because it has a pop method. Pop just means "remove the last element and return it". Of course you can mimic the functionality of a stack with an array, but an array still is not a stack by definition. It is still a list (a "list like" object according to MDN). – Bendy

@MichaelGeller The behavior of a stack is "first in, last out". If you implement it using an Array in JavaScript with its push and pop methods, then problem solved. I don't really see your point here. – Remunerative

@MichaelGeller A stack is conceptual. A JS array is (among other things) by definition a stack by virtue of implementing stack semantics. Just because it also implements array semantics doesn't change that. You can use a JS array like a stack out of the box, and in that context what you push and pop is the "top" element. – Emad

I wish all SO answers were this concise. – Grati

This queue implementation is O(N) for taking the first value, which means for N items, the behavior is O(N^2). Bad idea. – Lemberg

For those wondering ho do you do peek ? stack[stack.length-1] returns the last element of the stack without removing it (pop) – Oneness

Answer 3

Javascript has push and pop methods, which operate on ordinary Javascript array objects.

For queues, look here:

http://safalra.com/web-design/javascript/queues/

Queues can be implemented in JavaScript using either the push and shift methods or unshift and pop methods of the array object. Although this is a simple way to implement queues, it is very inefficient for large queues — because of the methods operate on arrays, the shift and unshift methods move every element in the array each time they are called.

Queue.js is a simple and efficient queue implementation for JavaScript whose dequeue function runs in amortized constant time. As a result, for larger queues, it can be significantly faster than using arrays.

Bandoline

With the link which you shared had a functionality of checking the benchmark results & I don't see performance gains when tested with Google Chrome version 59. Queue.js is incosistent with its speed but Chrome was preety consistent with its speed. – Convenient

Also I made a demo with the queue.js, that, the dequeue function does not really remove the item from the queue, so I wonder if its suppose to be how it works? If so, how can you retrieve the new queue after dequeue the previous item? codepen.io/adamchenwei/pen/VxgNrX?editors=0001 – Semple

it looks like the dequeue in queue.js also requires additional memory as it is cloning the array with slice. – Tryma

Furthermore, the underlying array is getting bigger and bigger with every added element. Even though the implementation reduces the array size from time to time, the overall size increases. – Loren

The link in this answer no longer works. – Selfpollination

Answer 4

If you wanted to make your own data structures, you could build your own:

var Stack = function(){
  this.top = null;
  this.size = 0;
};

var Node = function(data){
  this.data = data;
  this.previous = null;
};

Stack.prototype.push = function(data) {
  var node = new Node(data);

  node.previous = this.top;
  this.top = node;
  this.size += 1;
  return this.top;
};

Stack.prototype.pop = function() {
  temp = this.top;
  this.top = this.top.previous;
  this.size -= 1;
  return temp;
};

And for queue:

var Queue = function() {
  this.first = null;
  this.size = 0;
};

var Node = function(data) {
  this.data = data;
  this.next = null;
};

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){
    this.first = node;
  } else {
    n = this.first;
    while (n.next) {
      n = n.next;
    }
    n.next = node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  temp = this.first;
  this.first = this.first.next;
  this.size -= 1;
  return temp;
};

Teel

To avoid needing to iterate over the entire thing in order to append to the end, store a reference to the last one via this.last=node; – Overjoy

Never implement any Queue like this unless you have a really good reason for it... while it might seem logically correct, CPUs don't operate according to human abstractions. Iterating over a datastructure that has pointers all over the place will result in cache misses in the CPU, unlike a sequential array which is highly efficient. blog.davidecoppola.com/2014/05/… CPUs HATE pointers with a burning passion - they are probably the #1 cause of cache misses and having to access memory from RAM. – Isomerize

this is a tempting solution, but I don't see created Nodes being deleted when popping/dequeuing ... won't they just sit around hogging memory until the browser crashes? – Limey

@cneuro Unlike C++, JavaScript is a garbage collected language. It has a delete keyword, but that is only useful to mark a property of an object as being non-present—which is different from just assigning undefined to the property. JavaScript also has a new operator, but that is just used to set this to a new empty object when calling a function. In C++ you need to pair every new with a delete, but not in JavaScript because GC. To stop using memory in JavaScript, just stop referencing the object and it will eventually be reclaimed. – Gervais

Isn't it also necessary to check a stack for overflow by setting a max stack size? – Tecu

These are poor implementations. Don't use either one. Stacks should be nothing more than a wrapper on array push/pop, which is already optimal -- allocating custom Nodes is slower and more code. As for queues, yes, native array shift is (usually) O(n), but implementing a queue without a tail means pushes are O(n), totally defeating the purpose of writing your own. Again, just use an array to implement a queue until the O(n) shift starts to hurt, then optimize with a Node implementation with a tail property as shown here. – Basso

Answer 5

Here is my implementation of a stack and a queue using a linked list:

// Linked List
function Node(data) {
  this.data = data;
  this.next = null;
}

// Stack implemented using LinkedList
function Stack() {
  this.top = null;
}

Stack.prototype.push = function(data) {
  var newNode = new Node(data);

  newNode.next = this.top; //Special attention
  this.top = newNode;
}

Stack.prototype.pop = function() {
  if (this.top !== null) {
    var topItem = this.top.data;
    this.top = this.top.next;
    return topItem;
  }
  return null;
}

Stack.prototype.print = function() {
  var curr = this.top;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

// var stack = new Stack();
// stack.push(3);
// stack.push(5);
// stack.push(7);
// stack.print();

// Queue implemented using LinkedList
function Queue() {
  this.head = null;
  this.tail = null;
}

Queue.prototype.enqueue = function(data) {
  var newNode = new Node(data);

  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
}

Queue.prototype.dequeue = function() {
  var newNode;
  if (this.head !== null) {
    newNode = this.head.data;
    this.head = this.head.next;
  }
  return newNode;
}

Queue.prototype.print = function() {
  var curr = this.head;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

var queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();

F

Answer 6

The stack implementation is trivial as explained in the other answers.

However, I didn't find any satisfactory answers in this thread for implementing a queue in javascript, so I made my own.

There are three types of solutions in this thread:

• Arrays - The worst solution, using array.shift() on a large array is very inefficient.
• Linked lists - It's O(1) but using an object for each element is a bit excessive, especially if there are a lot of them and they are small, like storing numbers.
• Delayed shift arrays - It consists of associating an index with the array. When an element is dequeued, the index moves forward. When the index reaches the middle of the array, the array is sliced in two to remove the first half.

Delayed shift arrays are the most satisfactory solution in my mind, but they still store everything in one large contiguous array which can be problematic, and the application will stagger when the array is sliced.

I made an implementation using linked lists of small arrays (1000 elements max each). The arrays behave like delayed shift arrays, except they are never sliced: when every element in the array is removed, the array is simply discarded.

The package is on npm with basic FIFO functionality, I just pushed it recently. The code is split into two parts.

Here is the first part

/** Queue contains a linked list of Subqueue */
class Subqueue <T> {
  public full() {
    return this.array.length >= 1000;
  }

  public get size() {
    return this.array.length - this.index;
  }

  public peek(): T {
    return this.array[this.index];
  }

  public last(): T {
    return this.array[this.array.length-1];
  }

  public dequeue(): T {
    return this.array[this.index++];
  }

  public enqueue(elem: T) {
    this.array.push(elem);
  }

  private index: number = 0;
  private array: T [] = [];

  public next: Subqueue<T> = null;
}

And here is the main Queue class:

class Queue<T> {
  get length() {
    return this._size;
  }

  public push(...elems: T[]) {
    for (let elem of elems) {
      if (this.bottom.full()) {
        this.bottom = this.bottom.next = new Subqueue<T>();
      }
      this.bottom.enqueue(elem);
    }

    this._size += elems.length;
  }

  public shift(): T {
    if (this._size === 0) {
      return undefined;
    }

    const val = this.top.dequeue();
    this._size--;
    if (this._size > 0 && this.top.size === 0 && this.top.full()) {
      // Discard current subqueue and point top to the one after
      this.top = this.top.next;
    }
    return val;
  }

  public peek(): T {
    return this.top.peek();
  }

  public last(): T {
    return this.bottom.last();
  }

  public clear() {
    this.bottom = this.top = new Subqueue();
    this._size = 0;
  }

  private top: Subqueue<T> = new Subqueue();
  private bottom: Subqueue<T> = this.top;
  private _size: number = 0;
}

Type annotations (: X) can easily be removed to obtain ES6 javascript code.

Divulge

Answer 7

Javascript array shift() is slow especially when holding many elements. I know two ways to implement queue with amortized O(1) complexity.

First is by using circular buffer and table doubling. I have implemented this before. You can see my source code here https://github.com/kevyuu/rapid-queue

The second way is by using two stack. This is the code for queue with two stack

function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];

function moveElementToPopContainer() {
    while (pushContainer.length !==0 ) {
        var element = pushContainer.pop();
        popContainer.push(element);
    }
}

that.push = function(element) {
    pushContainer.push(element);
};

that.shift = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    } else {
        return popContainer.pop();
    }
};

that.front = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    }
    return popContainer[popContainer.length - 1];
};

that.length = function() {
    return pushContainer.length + popContainer.length;
};

that.isEmpty = function() {
    return (pushContainer.length + popContainer.length) === 0;
};

return that;}

This is performance comparison using jsPerf

CircularQueue.shift() vs Array.shift()

http://jsperf.com/rapidqueue-shift-vs-array-shift

As you can see it is significantly faster with large dataset

Bursitis

Which one is faster? Your jsperf link is not working. – Lemberg

The two-stacks idea is a nice and simple way to get O(1) performance. But you can do that in a simpler way by using the native array implementation for the two stacks. See my answer. – Partlow

Answer 8

You can use your own customize class based on the concept, here the code snippet which you can use to do the stuff

/*
*   Stack implementation in JavaScript
*/



function Stack() {
  this.top = null;
  this.count = 0;

  this.getCount = function() {
    return this.count;
  }

  this.getTop = function() {
    return this.top;
  }

  this.push = function(data) {
    var node = {
      data: data,
      next: null
    }

    node.next = this.top;
    this.top = node;

    this.count++;
  }

  this.peek = function() {
    if (this.top === null) {
      return null;
    } else {
      return this.top.data;
    }
  }

  this.pop = function() {
    if (this.top === null) {
      return null;
    } else {
      var out = this.top;
      this.top = this.top.next;
      if (this.count > 0) {
        this.count--;
      }

      return out.data;
    }
  }

  this.displayAll = function() {
    if (this.top === null) {
      return null;
    } else {
      var arr = new Array();

      var current = this.top;
      //console.log(current);
      for (var i = 0; i < this.count; i++) {
        arr[i] = current.data;
        current = current.next;
      }

      return arr;
    }
  }
}

and to check this use your console and try these line one by one.

>> var st = new Stack();

>> st.push("BP");

>> st.push("NK");

>> st.getTop();

>> st.getCount();

>> st.displayAll();

>> st.pop();

>> st.displayAll();

>> st.getTop();

>> st.peek();

Sentimentalism

Downvote for a naming convention: method that starts with a capital assumed to be a constructor. – Obannon

Answer 9

There are quite a few ways in which you can implement Stacks and Queues in Javascript. Most of the answers above are quite shallow implementations and I would try to implement something more readable (using new syntax features of es6) and robust.

Here's the stack implementation:

class Stack {
  constructor(...items){
    this._items = []

    if(items.length>0)
      items.forEach(item => this._items.push(item) )

  }

  push(...items){
    //push item to the stack
     items.forEach(item => this._items.push(item) )
     return this._items;

  }

  pop(count=0){
    //pull out the topmost item (last item) from stack
    if(count===0)
      return this._items.pop()
     else
       return this._items.splice( -count, count )
  }

  peek(){
    // see what's the last item in stack
    return this._items[this._items.length-1]
  }

  size(){
    //no. of items in stack
    return this._items.length
  }

  isEmpty(){
    // return whether the stack is empty or not
    return this._items.length==0
  }

  toArray(){
    return this._items;
  }
}

And this is how you can use the stack :

let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3

If you would like to see the detailed description about this implementation and how it can be further improved, you can read here : http://jschap.com/data-structures-in-javascript-stack/

Here's the code for queue implementation in es6 :

class Queue{
 constructor(...items){
   //initialize the items in queue
   this._items = []
   // enqueuing the items passed to the constructor
   this.enqueue(...items)
 }

  enqueue(...items){
    //push items into the queue
    items.forEach( item => this._items.push(item) )
    return this._items;
  }

  dequeue(count=1){
    //pull out the first item from the queue
    this._items.splice(0,count);
    return this._items;
  }

  peek(){
    //peek at the first item from the queue
    return this._items[0]
  }

  size(){
    //get the length of queue
    return this._items.length
  }

  isEmpty(){
    //find whether the queue is empty or no
    return this._items.length===0
  }
}

Here's how you can use this implementation:

let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3

To go through the complete tutorial of how these data structures have been implemented and how can these further be improved, you may want to go through the 'Playing with data structures in javascript' series at jschap.com . Here's the links for queues - http://jschap.com/playing-data-structures-javascript-queues/

Sororate

Answer 10

I like to think that the cleanest way to implement stack and queues should be to use a container that allows addition and deletion from both ends and then limit its capabilities for one end which can be done through a simple array in Javascript.

// STATEMENTS USED IN STACK CONTAINER WHILE ENCAPSULATING

// Allow push and pop from the same end
array.push(element);
array.pop();

// STATEMENTS USED IN QUEUE CONTAINER WHILE ENCAPSULATING

// Allow push and pop from different ends
array.push(element);
array.shift();

Household

Answer 11

Or else you can use two arrays to implement queue data structure.

var temp_stack = new Array();
var stack = new Array();

temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);

If I pop the elements now then the output will be 3,2,1. But we want FIFO structure so you can do the following.

stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());

stack.pop(); //Pop out 1
stack.pop(); //Pop out 2
stack.pop(); //Pop out 3

Surety

This is only works if you never push after the first time you pop – Euhemerism

Answer 12

/*------------------------------------------------------------------ 
 Defining Stack Operations using Closures in Javascript, privacy and
 state of stack operations are maintained

 @author:Arijt Basu
 Log: Sun Dec 27, 2015, 3:25PM
 ------------------------------------------------------------------- 
 */
var stackControl = true;
var stack = (function(array) {
        array = [];
        //--Define the max size of the stack
        var MAX_SIZE = 5;

        function isEmpty() {
            if (array.length < 1) console.log("Stack is empty");
        };
        isEmpty();

        return {

            push: function(ele) {
                if (array.length < MAX_SIZE) {
                    array.push(ele)
                    return array;
                } else {
                    console.log("Stack Overflow")
                }
            },
            pop: function() {
                if (array.length > 1) {
                    array.pop();
                    return array;
                } else {
                    console.log("Stack Underflow");
                }
            }

        }
    })()
    // var list = 5;
    // console.log(stack(list))
if (stackControl) {
    console.log(stack.pop());
    console.log(stack.push(3));
    console.log(stack.push(2));
    console.log(stack.pop());
    console.log(stack.push(1));
    console.log(stack.pop());
    console.log(stack.push(38));
    console.log(stack.push(22));
    console.log(stack.pop());
    console.log(stack.pop());
    console.log(stack.push(6));
    console.log(stack.pop());
}
//End of STACK Logic

/* Defining Queue operations*/

var queue = (function(array) {
    array = [];
    var reversearray;
    //--Define the max size of the stack
    var MAX_SIZE = 5;

    function isEmpty() {
        if (array.length < 1) console.log("Queue is empty");
    };
    isEmpty();

    return {
        insert: function(ele) {
            if (array.length < MAX_SIZE) {
                array.push(ele)
                reversearray = array.reverse();
                return reversearray;
            } else {
                console.log("Queue Overflow")
            }
        },
        delete: function() {
            if (array.length > 1) {
                //reversearray = array.reverse();
                array.pop();
                return array;
            } else {
                console.log("Queue Underflow");
            }
        }
    }



})()

console.log(queue.insert(5))
console.log(queue.insert(3))
console.log(queue.delete(3))

Amaya

Answer 13

As many have said: native array push and pop are fine as stack operations, but using shift as the queue extraction operation means that the elements remaining in the array need to move, which is potentially slow. The idea of using two stacks to make a queue in kevinyu's answer is a nice idea to fix it, and of course that can be done with native-array-stacks as well. (Note: There was actually already an answer by Yuki-Dreamer that does this, albeit less compactly than my version.)

Here's a compact implementation using some ES5/ES6 features that makes a queue object which behaves as closely as possible to the native-push/shift variant, except that it takes amortized O(1) time per operation:

const queue = () => {
    const a = [], b = [];
    return {
        push: (...elts) => a.push(...elts),
        shift: () => {
            if (b.length === 0) {
                while (a.length > 0) { b.push(a.pop()) }
            }
            return b.pop();
        },
        get length() { return a.length + b.length }
    }
}

Now you can do:

const q = queue();
q.push(8);
q.push(9);
q.push(10);
console.log(q.length);          // outputs 3
console.log(q.shift());         // outputs 8
q.push(11);
console.log(q.shift());         // outputs 9
console.log(q.shift());         // outputs 10
console.log(q.shift());         // outputs 11
console.log(q.shift());         // outputs undefined

The queue implementation uses a getter syntax for length, to make it look like a property, and rest parameter syntax for push to allow pushing more than one thing at a time. If you don't want that, you can replace line 4 with push: elt => a.push(elt),. (Note, however, that you can not replace it with push: a.push, like I tried first myself with really weird results: that's because it results in the native push method being called with this set to the queue object.)

OPTIMIZATION: Here's a tiny speed-improvement of the code. Replace the while line with the following two lines to save one push+pop at every transfer from a to b:

                while (a.length > 1) { b.push(a.pop()) }
                return a.pop();

Partlow

Answer 14

Here is a fairly simple queue implementation with two aims:

• Unlike array.shift(), you know this dequeue method takes constant time (O(1)).
• To improve speed, this approach uses many fewer allocations than the linked-list approach.

The stack implementation shares the second aim only.

// Queue
function Queue() {
        this.q = new Array(5);
        this.first = 0;
        this.size = 0;
}
Queue.prototype.enqueue = function(a) {
        var other;
        if (this.size == this.q.length) {
                other = new Array(this.size*2);
                for (var i = 0; i < this.size; i++) {
                        other[i] = this.q[(this.first+i)%this.size];
                }
                this.first = 0;
                this.q = other;
        }
        this.q[(this.first+this.size)%this.q.length] = a;
        this.size++;
};
Queue.prototype.dequeue = function() {
        if (this.size == 0) return undefined;
        this.size--;
        var ret = this.q[this.first];
        this.first = (this.first+1)%this.q.length;
        return ret;
};
Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; };
Queue.prototype.isEmpty = function() { return this.size == 0; };

// Stack
function Stack() {
        this.s = new Array(5);
        this.size = 0;
}
Stack.prototype.push = function(a) {
        var other;
    if (this.size == this.s.length) {
            other = new Array(this.s.length*2);
            for (var i = 0; i < this.s.length; i++) other[i] = this.s[i];
            this.s = other;
    }
    this.s[this.size++] = a;
};
Stack.prototype.pop = function() {
        if (this.size == 0) return undefined;
        return this.s[--this.size];
};
Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };

Sodamide

Answer 15

A little late answer but i think this answer should be here. Here is an implementation of Queue with O(1) enqueue and O(1) dequeue using the sparse Array powers.

Sparse Arrays in JS are mostly disregarded but they are in fact a gem and we should put their power in use at some critical tasks.

So here is a skeleton Queue implementation which extends the Array type and does it's things in O(1) all the way.

class Queue extends Array {
  constructor(){
    super()
    Object.defineProperty(this,"head",{ value   : 0
                                      , writable: true
                                      });
  }
  enqueue(x) {
    this.push(x);
    return this;
  }
  dequeue() {
    var first;
    return this.head < this.length ? ( first = this[this.head]
                                     , delete this[this.head++]
                                     , first
                                     )
                                   : void 0; // perfect undefined
  }
  peek() {
    return this[this.head];
  }
}

var q = new Queue();
console.log(q.dequeue());      // doesn't break
console.log(q.enqueue(10));    // add 10
console.log(q.enqueue("DIO")); // add "DIO" (Last In Line cCc R.J.DIO reis cCc)
console.log(q);                // display q
console.log(q.dequeue());      // lets get the first one in the line
console.log(q.dequeue());      // lets get DIO out from the line

.as-console-wrapper {
  max-height: 100% !important;
}

So do we have a potential memory leak here? No i don't think so. JS sparse arrays are non contiguous. Accordingly deleted items shouln't be a part of the array's memory footprint. Let the GC do it's job for you. It's free of charge.

One potential problem is that, the length property grows indefinitely as you keep enqueueing items to the queue. However still one may implement an auto refreshing (condensing) mechanism to kick in once the length reaches to a certain value.

Edit:

The above code if just fine but the delete operator, while still being O(1), is a slow one. Besides the modern JS engines are so optimized that for like < ~25000 items .shift() works O(1) anyways. So we need something better.

In this particular case, as the engines develop we must harness their new powers. The code below uses a linked list and i believe it is the fastest and safest modern JS Queue structure as of 2021.

class Queue {
  #head;
  #last;
  constructor(){
    this.#head;
    this.#last;
  };
  enqueue(value){
    var link = {value, next: void 0};
    this.#last = this.#head ? this.#last.next = link
                            : this.#head      = link;
  }
  dequeue(){
    var first;
    return this.#head && ( first = this.#head.value
                         , this.#head = this.#head.next
                         , first
                         );
  }
  peek(){
    return this.#head && this.#head.value;
  }
};

This is an extremely fast Queue structure and uses Private Class Fields to hide critical variables from prying eyes.

Holmgren

Answer 16

If you understand stacks with push() and pop() functions, then queue is just to make one of these operations in the oposite sense. Oposite of push() is unshift() and oposite of pop() es shift(). Then:

//classic stack
var stack = [];
stack.push("first"); // push inserts at the end
stack.push("second");
stack.push("last");
stack.pop(); //pop takes the "last" element

//One way to implement queue is to insert elements in the oposite sense than a stack
var queue = [];
queue.unshift("first"); //unshift inserts at the beginning
queue.unshift("second");
queue.unshift("last");
queue.pop(); //"first"

//other way to do queues is to take the elements in the oposite sense than stack
var queue = [];
queue.push("first"); //push, as in the stack inserts at the end
queue.push("second");
queue.push("last");
queue.shift(); //but shift takes the "first" element

Goingson

A word of warning for those writing performance critical software. The .shift() method is not a proper queue implementation. It is O(n) rather than O(1), and will be slow for large queues. – Chinchy

Thanks @RudiKershaw, you're right. If there is need to implement a O(1) queue it can be built with a linked list. – Goingson

Answer 17

If you're looking for ES6 OOP implementation of Stack and Queue data-structure with some basic operations (based on linked lists) then it may look like this:

Queue.js

import LinkedList from '../linked-list/LinkedList';

export default class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }

  isEmpty() {
    return !this.linkedList.tail;
  }

  peek() {
    if (!this.linkedList.head) {
      return null;
    }

    return this.linkedList.head.value;
  }

  enqueue(value) {
    this.linkedList.append(value);
  }

  dequeue() {
    const removedHead = this.linkedList.deleteHead();
    return removedHead ? removedHead.value : null;
  }

  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

Stack.js

import LinkedList from '../linked-list/LinkedList';

export default class Stack {
  constructor() {
    this.linkedList = new LinkedList();
  }

  /**
   * @return {boolean}
   */
  isEmpty() {
    return !this.linkedList.tail;
  }

  /**
   * @return {*}
   */
  peek() {
    if (!this.linkedList.tail) {
      return null;
    }

    return this.linkedList.tail.value;
  }

  /**
   * @param {*} value
   */
  push(value) {
    this.linkedList.append(value);
  }

  /**
   * @return {*}
   */
  pop() {
    const removedTail = this.linkedList.deleteTail();
    return removedTail ? removedTail.value : null;
  }

  /**
   * @return {*[]}
   */
  toArray() {
    return this.linkedList
      .toArray()
      .map(linkedListNode => linkedListNode.value)
      .reverse();
  }

  /**
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

And LinkedList implementation that is used for Stack and Queue in examples above may be found on GitHub here.

Mateya

Answer 18

The regular Array structure in Javascript is a Stack (first in, last out) and can also be used as a Queue (first in, first out) depending on the calls you make.

Check this link to see how to make an Array act like a Queue:

Queues

Holter

Answer 19

No Array(s)

//Javascript stack linked list data structure (no array)

function node(value, noderef) {
    this.value = value;
    this.next = noderef;
}
function stack() {
    this.push = function (value) {
        this.next = this.first;
        this.first = new node(value, this.next);
    }
    this.pop = function () {
        var popvalue = this.first.value;
        this.first = this.first.next;
        return popvalue;
    }
    this.hasnext = function () {
        return this.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

//Javascript stack linked list data structure (no array)
function node(value, noderef) {
    this.value = value;
    this.next = undefined;
}
function queue() {
    this.enqueue = function (value) {
        this.oldlast = this.last;
        this.last = new node(value);
        if (this.isempty())
            this.first = this.last;
        else 
           this.oldlast.next = this.last;
    }
    this.dequeue = function () {
        var queuvalue = this.first.value;
        this.first = this.first.next;
        return queuvalue;
    }
    this.hasnext = function () {
        return this.first.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

Butterscotch

How can i run given internal function like push pop? – Bridgid

Answer 20

Here is the linked list version of a queue that also includes the last node, as suggested by @perkins and as is most appropriate.

// QUEUE Object Definition

var Queue = function() {
  this.first = null;
  this.last = null;
  this.size = 0;
};

var Node = function(data) {
  this.data = data;
  this.next = null;
};

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){ // for empty list first and last are the same
    this.first = node;
    this.last = node;
  } else { // otherwise we stick it on the end
    this.last.next=node;
    this.last=node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  if (!this.first) //check for empty list
    return null;

  temp = this.first; // grab top of list
  if (this.first==this.last) {
    this.last=null;  // when we need to pop the last one
  }
  this.first = this.first.next; // move top of list down
  this.size -= 1;
  return temp;
};

Puttergill

In dequeue, you should return temp.data instead. Because that is what was queued. – Thoroughpaced

Answer 21

Construct a Queue using two Stacks.

O(1) for both enqueue and dequeue operations.

class Queue {
  constructor() {
    this.s1 = []; // in
    this.s2 = []; // out
  }

  enqueue(val) {
    this.s1.push(val);
  }

  dequeue() {
    if (this.s2.length === 0) {
      this._move();
    }

    return this.s2.pop(); // return undefined if empty
  }

  _move() {
    while (this.s1.length) {
      this.s2.push(this.s1.pop());
    }
  }
}

Enshrine

Dequeue is O(n) for this implementation. If you queue 5 items and then dequeue 1, the while loop will need to run through all 5 items pushing them into s2. – Carbide

The O(1) measurement is for every element in average. Because every element will be in/out for stack 1&2 only once. – Enshrine

I was always taught that big O is for the worst case scenario as described here medium.com/omarelgabrys-blog/… . It's an assumption that items will be dequeued at the same rate as they are queued. It depends on the implementation scenario. Without knowing the implementation scenario I don't think you can make this assumption IMHO. – Carbide

Yes, you are right. For this specific operation, the time complexity is O(n). But let's put this into a real-world engineering environment. The reason to use or the value of using Queue is when you have multiple in&out operations for this data structure, like doing BFS, etc. In this case, measuring the average performance makes more sense. If you want to implement a definite O(1) solution, use LinkedList is good choice. – Enshrine

Note that the native array push is also amortized O(1) time: it occasionally needs to double the size of the backing storage, which takes linear time (but the cost can be divided across the total number of operations). So if you don't think this is O(1), push isn't either. – Partlow

Answer 22

Sorry to bump this topic but I scrolled over the many answers and did not see any implementation of an Object based Queue, which can perform enqueue AND dequeue with O(1) AND no wasted memory.

Dmitri Pavlutin has a nice starter code on his blog https://dmitripavlutin.com/javascript-queue/

It only misses a 0 length check, which is trivial to add.

the big and only problem of this solution is the ever growing index wich could hit some Number limit at one point, if the queue runs for a long time and/or at high speed (my intent is to process audio = high speed).

There is no perfect solution for this... the easy way can be resetting the index to 0 whenever the queue is empty.

At Last, I added a refactor method which costly shifts all the indexes back to the beginning, to use in the case the queue is never empty.

The performance is with no doubt better (the number is time in miliseconds for enqueuing 10 000 numbers then dequeuing them) :

class QueueObject {
  constructor () {
    this.data = {}
    this.head = 0
    this.tail = 0
    this.length = 0
  }
  enqueue (value) {
    this.data[this.tail++] = value
    this.length++
  }
  dequeue () {
    let value
    if (this.length > 0) {
      this.length--
      value = this.data[this.head]
      delete this.data[this.head++]
    } else {
      this.head = 0
      this.tail = 0
      value = null
    }
    return value
  }
  refactor () {
    if (this.head > 0) {
      for (let i = this.head; i < this.tail; i++) {
        this.data[i - this.head] = this.data[i]
        delete this.data[i]
      }
      this.tail = this.length
      this.head = 0
    }
  }
}

Drumbeat

"It only misses a 0 length check, which is trivial to add." - the check was added. – Mackoff

Answer 23

  var x = 10; 
  var y = 11; 
  var Queue = new Array();
  Queue.unshift(x);
  Queue.unshift(y);

  console.log(Queue)
  // Output [11, 10]

  Queue.pop()
  console.log(Queue)
  // Output [11]

Yeti

Answer 24

Seems to me that the built in array is fine for a stack. If you want a Queue in TypeScript here is an implementation

/**
 * A Typescript implementation of a queue.
 */
export default class Queue {

  private queue = [];
  private offset = 0;

  constructor(array = []) {
    // Init the queue using the contents of the array
    for (const item of array) {
      this.enqueue(item);
    }
  }

  /**
   * @returns {number} the length of the queue.
   */
  public getLength(): number {
    return (this.queue.length - this.offset);
  }

  /**
   * @returns {boolean} true if the queue is empty, and false otherwise.
   */
  public isEmpty(): boolean {
    return (this.queue.length === 0);
  }

  /**
   * Enqueues the specified item.
   *
   * @param item - the item to enqueue
   */
  public enqueue(item) {
    this.queue.push(item);
  }

  /**
   *  Dequeues an item and returns it. If the queue is empty, the value
   * {@code null} is returned.
   *
   * @returns {any}
   */
  public dequeue(): any {
    // if the queue is empty, return immediately
    if (this.queue.length === 0) {
      return null;
    }

    // store the item at the front of the queue
    const item = this.queue[this.offset];

    // increment the offset and remove the free space if necessary
    if (++this.offset * 2 >= this.queue.length) {
      this.queue = this.queue.slice(this.offset);
      this.offset = 0;
    }

    // return the dequeued item
    return item;
  };

  /**
   * Returns the item at the front of the queue (without dequeuing it).
   * If the queue is empty then {@code null} is returned.
   *
   * @returns {any}
   */
  public peek(): any {
    return (this.queue.length > 0 ? this.queue[this.offset] : null);
  }

}

And here is a Jest test for it

it('Queue', () => {
  const queue = new Queue();
  expect(queue.getLength()).toBe(0);
  expect(queue.peek()).toBeNull();
  expect(queue.dequeue()).toBeNull();

  queue.enqueue(1);
  expect(queue.getLength()).toBe(1);
  queue.enqueue(2);
  expect(queue.getLength()).toBe(2);
  queue.enqueue(3);
  expect(queue.getLength()).toBe(3);

  expect(queue.peek()).toBe(1);
  expect(queue.getLength()).toBe(3);
  expect(queue.dequeue()).toBe(1);
  expect(queue.getLength()).toBe(2);

  expect(queue.peek()).toBe(2);
  expect(queue.getLength()).toBe(2);
  expect(queue.dequeue()).toBe(2);
  expect(queue.getLength()).toBe(1);

  expect(queue.peek()).toBe(3);
  expect(queue.getLength()).toBe(1);
  expect(queue.dequeue()).toBe(3);
  expect(queue.getLength()).toBe(0);

  expect(queue.peek()).toBeNull();
  expect(queue.dequeue()).toBeNull();
});

Hope someone finds this useful,

Cheers,

Stu

Bogosian

Answer 25

Single-ended queue

Here is a queue using a map. Since insertion order is guaranteed, you can iterate it like an array. Other than that the idea is very similar to Queue.js.

I've made some simple tests, but haven't tested it extensively. I also added some features that I thought were nice (constructing via an array) or easy to implement (e.g. last() and first()).

The simple version / intuition behind it is below:

class Queue {
    constructor() {
        this.offset = 0
        this.data = new Map()
    }

    enqueue(item) {
        const current = this.offset + this.length()
        this.data.set(current, item)
    }

    dequeue() {
        if (this.length() > 0) {
            this.data.delete(this.offset)
            this.offset += 1
        }
    }

    first() {
        return this.data.get(this.offset)
    }

    last() {
        return this.data.get(this.offset + this.length() - 1)
    }

    length() {
        return this.data.size
    }
}

The issue with the simple version is that memory needs to be remapped when it has indexed over about 9 quadrillion (the value of Number.MAX_SAFE_INTEGER). Moreover, I think it might be nice to have array construction and it is nice to see the values being enqueued and dequeued being returned. One could account for this by writing the following code:

class Queue {
    constructor() {
        this.offset = 0
        this.data = new Map()
        if (arguments.length === 1) this._initializeFromArray(arguments[0])
    }

    enqueue(item) {
        const current = this.offset + this.length()
        this.data.set(current, item)
        let result = this.data.get(current)
        this._remapDataIfMaxMemoryViolation(current, Number.MAX_SAFE_INTEGER)
        return result
    }

    dequeue() {
        let result = undefined
        if (this.length() > 0) {
            result = this.data.get(this.offset)
            this.data.delete(this.offset)
            this.offset += 1
        }
        if (this.length() === 0) this.offset = 0
        return result
    }

    first() {
        return this.data.get(this.offset)
    }

    last() {
        return this.data.get(this.offset + this.length() - 1)
    }

    length() {
        return this.data.size
    }

    _remapDataIfMaxMemoryViolation(current, threshhold) {
        if (current+1 === threshhold) {
            const length = this.length()
            this.offset = 0
            for (const [key, value] of this.data) {
                this.data.set(this.offset, value)
                this.data.delete(key, value)
                this.offset += 1
                if (this.offset === length) break
            }       
        }
    }

    _initializeFromArray(array) {
        for (const value of array) {
            this.data.set(this.offset, value)
            this.offset += 1
        }
    }
}

I did some testing in the Chrome developer console with the following calls on the full version.

l = console.log // I'm lazy with typing
q = new Queue()
l('enqueue', q.enqueue(1))
l('enqueue', q.enqueue(2))
l('enqueue', q.enqueue(3))
l('enqueue', q.enqueue("hello"))
l('enqueue', q.enqueue("monkey"))
l('show 5 elements: ', q.data)
l('length', q.length())
l('first', q.first())
l('last', q.last())
l('dequeue', q.dequeue())
l('dequeue', q.dequeue())
l('show 3 elements', q.data)
q._remapDataIfMaxMemoryViolation(q.length()+q.offset-1, 5)
l('show 3 remapped elements', q.data)

l(queue = new Queue([3,4,5,6,7,8,9]))
l(queue.data)

Theorist

You don't have to remap anything. Queue length will never reach Number.MAX_SAFE_INTEGER value. Thus if index reaches it, set index again to 0 (overflow). – Anaximander

Answer 26

I ran into this thread while implementing a BFS. After wondering why the performance was so poor I did some research. array.shift() typically runs in O(n) which increases my BFS runtime from O(V+E) to O(V^2+E).

Instead of implementing a queue from scratch I used the npm package double-ended-queue which is compatible to the previously used array methods and works like a charm. The deque can be used as stack or queue.

    //import package
    import Deque from 'double-ended-queue';

    //create queue
    let queue = new Deque();
    //append
    queue.push(item);
    //dequeue (get first item inserted)
    let firstItem = queue.shift();

    //pop (get last item inserted)
    let lastItem = queue.pop();

Collaboration

Answer 27

An array is a stack in Javascript. Just use arr.push(x) and y = arr.pop().

Here is the simplest method for implementing a queue in Javascript that has an amortized time of O(1) for both enqueue(x) and y = dequeue(). It uses a mapping from insertion index to element.

function newQueue() {
    return {
        headIdx: 0,
        tailIdx: 0,
        elts: {},
        enqueue: (elt) => queue.elts[queue.tailIdx++] = elt,
        dequeue: () => {
            if (queue.headIdx == queue.tailIdx) {
                throw new Error("Queue is empty");
            }
            return queue.elts[queue.headIdx++];
        },
        size: () => queue.tailIdx - queue.headIdx,
        isEmpty: () => queue.tailIdx == queue.headIdx
    };
}

A queue implemented using a linked list is more efficient than this map-based method, and a queue implemented using a circular buffer is much more efficient than this map-based method, but the implementations of those two data structures is more complicated (especially the circular buffer data structure).

Lemberg

Answer 28

Create a pair of classes that provide the various methods that each of these data structures has (push, pop, peek, etc). Now implement the methods. If you're familiar with the concepts behind stack/queue, this should be pretty straightforward. You can implement the stack with an array, and a queue with a linked list, although there are certainly other ways to go about it. Javascript will make this easy, because it is weakly typed, so you don't even have to worry about generic types, which you'd have to do if you were implementing it in Java or C#.

Fard

Answer 29

Here is my Implementation of Stacks.

function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}

var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());
console.log(s.peek());

Peers

Answer 30

Regards,

In Javascript the implementation of stacks and queues is as follows:

Stack: A stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle.

• Push: Method adds one or more elements to the end of an array and returns the new length of the array.
• Pop: Method removes the last element from an array and returns that element.

Queue: A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in-first-out (FIFO) principle.

• Unshift: Method adds one or more elements to the beginning of an array.

• Shift: The method removes the first element from an array.

let stack = [];
 stack.push(1);//[1]
 stack.push(2);//[1,2]
 stack.push(3);//[1,2,3]
 
console.log('It was inserted 1,2,3 in stack:', ...stack);

stack.pop(); //[1,2]
console.log('Item 3 was removed:', ...stack);

stack.pop(); //[1]
console.log('Item 2 was removed:', ...stack);


let queue = [];
queue.push(1);//[1]
queue.push(2);//[1,2]
queue.push(3);//[1,2,3]

console.log('It was inserted 1,2,3 in queue:', ...queue);

queue.shift();// [2,3]
console.log('Item 1 was removed:', ...queue);

queue.shift();// [3]
console.log('Item 2 was removed:', ...queue);

Malacology

Answer 31

you can use WeakMaps for implementing private property in ES6 class and benefits of String propeties and methods in JavaScript language like below:

const _items = new WeakMap();

class Stack {
  constructor() {
    _items.set(this, []);
  }

push(obj) {
  _items.get(this).push(obj);
}

pop() {
  const L = _items.get(this).length;
  if(L===0)
    throw new Error('Stack is empty');
  return _items.get(this).pop();
}

peek() {
  const items = _items.get(this);
  if(items.length === 0)
    throw new Error ('Stack is empty');
  return items[items.length-1];
}

get count() {
  return _items.get(this).length;
}
}

const stack = new Stack();

//now in console:
//stack.push('a')
//stack.push(1)
//stack.count   => 2
//stack.peek()  => 1
//stack.pop()   => 1
//stack.pop()   => "a"
//stack.count   => 0
//stack.pop()   => Error Stack is empty

Hofuf

Answer 32

Well in case someone else needs it you can use this NPM package https://www.npmjs.com/package/data-structures-typescript, it has a queue and also and stack, it supports both javascript and typescript and it's generic so you can use it with your own type of value ;)

Aerostat

Answer 33

Here is Map-based queue implementation for TypeScript.

export interface Queue<T> {
  readonly length: number;

  enqueue (item: T): T;
  dequeue (): T | undefined;
  peek (): T | undefined;
}

export class HashQueue<T> implements Queue<T> {
  protected items: Map<number, T> = new Map();
  protected headIndex = 0;
  protected tailIndex = 0;

  get length (): number {
    return this.items.size;
  }

  enqueue (item: T): T {
    const itemIndex = this.tailIndex++;
    this.tailIndex >= Number.MAX_SAFE_INTEGER && (this.tailIndex = 0);

    this.items.set(itemIndex, item);

    return item;
  }

  dequeue (): T | undefined {
    if (this.items.size) {
      const itemIndex = this.headIndex++;
      this.headIndex >= Number.MAX_SAFE_INTEGER && (this.headIndex = 0);

      const result = this.items.get(itemIndex);
      this.items.delete(itemIndex);

      return result;
    }
  }

  peek (): T | undefined {
    return this.items.size ? this.items.get(this.headIndex) : undefined;
  }
}

Anaximander