Introduction to data structures and algorithms in javascript: Stacks and Queues

This is a continuation of a series introducing data structures in javascript. In the last couple of
posts, the javascript Array was introduced and it is recommended to have an understanding of the
javascript Array before reading this article.

Stack

A stack is a linear data structure and abstract data type in which operations are performed via the
last in, first out (LIFO) methodology. Similar to other programming languages there are two main
methods in javascript used to populate and retrieve data in the stack. These methods are ‘push’
and ‘pop’. The ‘push’ method is used to add an element to the top of stack and the ‘pop’ method is
used to remove the top element from the stack.

In javascript, the Array object is used for a stack implementation. Javascript has a push() and a
pop() method for the Array object which makes the implementation rather simple.

	var stack = new Array();
	stack.push("one");
	stack.push("two");
	stack.push("three");

	document.writeln(stack.pop() + " - stack length:" + stack.length); // prints "three - stack length: 2"
	document.writeln(stack.pop() + " - stack length:" + stack.length); // prints "two - stack length: 1" 
	document.writeln(stack.pop() + " - stack length:" + stack.length); // prints "one - stack length: 0" 

One key point to understand is that when pushing an element to the stack it is adding it to the end
of the Array. This may be counter intuitive since it is commonly referred to as the “top of the stack”.

Another point to understand is that when you use the pop method it removes the last element from the
Array as indicated in the code sample when it prints the Array length.

Queue

A queue is also a linear data structure and abstract data type with one key difference from a stack
being that it uses a first in, first out (FIFO) methodology. Another name for a queue is a buffer.
Typical usage of a queue would be for instances where you have more data to manipulate than you can
handle in a single period of time.

In javascript, the Array object is also used for a queue implementation. The unshift() method is
used to add elements to the beginning of an Array; ensuring that when you use pop() you get the first
element that was added to the Array.

	var queue = [];
	queue.unshift("one");
	queue.unshift("two");
	queue.unshift("three");

	document.writeln(queue.pop() + " - queue length:" + queue.length); // prints "one - queue length: 2"
	document.writeln(queue.pop() + " - queue length:" + queue.length); // prints "two - queue length: 1" 
	document.writeln(queue.pop() + " - queue length:" + queue.length); // prints "three - queue length: 0" 
Advertisements
Tags:

One Comment to “Introduction to data structures and algorithms in javascript: Stacks and Queues”

  1. I would like to see a Union-Find in JavaScript please

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: