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.

Solution 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"

Solution 2

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.

Solution 3

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();

Solution 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;
};

Solution 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();

View more solutions

Comments

[baz]

As a circular buffer

[MAK]

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.

[Stefan]

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

[Christoph]

@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...

[Pavlo]

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

[Perkins]

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;

[Joel Peltonen]

@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.

[anpatel]

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

[Centril]

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.

[cneuro]

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?

[Michael Geller]

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.

[Lukas Liesis]

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

[mrdommyg]

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

[binki]

@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.

[Michael Geller]

@mrdommyg 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).

[Shiljo Paulson]

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.

[Rax Weber]

@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.

[Hans]

@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.

[jnnnnn]

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

[not-a-robot]

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

[li_]

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

[Ezeewei]

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

[JaTo]

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

[Philipp Mitterer]

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.

[Chandan Kumar]

How can i run given internal function like push pop?

[Rudi Kershaw]

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.

[Caleb Seadon]

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.

[Yuki-Dreamer]

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

[Caleb Seadon]

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.

[Yuki-Dreamer]

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.

[Javier Giovannini]

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

[kmiklas]

I wish all SO answers were this concise.

[MortezaE]

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

[ggorlen]

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.

[forresthopkinsa]

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

[Chev]

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

[Chev]

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.

[forresthopkinsa]

@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

[Chev]

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