Overview

Let's talk about stacks. No, not that wad of bills you made last time you were in Vegas, the data structure. To be more precise, a stack is an abstract data type with two main operations. These two operations are often called Push and Pop, to put a value or element into the stack, and taking that value or element out of the stack. Now, Push and Pop don't just add and delete values all over the place willy-nilly, if a value is to be added to the stack it is added to the top of the stack and if a value is to be removed, it is done in a Last-In-First-Out (LIFO) format.

Benefits

While a stack is not the fanciest of ADTs it has certain real-world analogies (e.g. parking in a single-lane driveway, last one in, first one out), as well as similarities to underlying software engineering properties (e.g., undo functionality).

With regards to time complexity, pushing and popping are both O(1).

Implementations

Using the Javascript language, implementation of a stack may seem incredibly trivial. The array already has push and pop methods for pete's sake! Well using an array to implement a stack is cheating, you heard it here first, folks. Let's take a look at some JS code below to show everyone a DIY stack.

In true pseudoclassical function, here we are establishing our constructor!

var Stack = function() {

  this.top = null;
  this.size = 0;

};

Next, we need to create a 'node' for each entry into the stack. Each node is going to take a value argument, and will also contain a property, previous, that will point to the node pushed in after it. We set the initial previous property to zero so that the first Node pushed in will not point to anything.

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

At this point, we will go ahead and establish our two methods, .push() and .pop(). We can see below that each call of .push() will create a new Node object, assign the previous property to an existing node (if there is a pre-existing node, if not it will default to null), re-assign the top property, and increment size. On the .pop() method we can see that invoking this method on an empty stack will simply return null.

Stack.prototype.push = function(value) {  
  var node = new Node(value);
  node.previous = this.top;
  this.top = node;
  this.size++;
};

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

Data Structures , Javascript , Computer Science , Stacks

About the author
comments powered by Disqus