Interview Prep: Data Structures:Stacks

Are you like me and getting reading for a technical interview? As one technical interviewer said to me, “Technical interviews are getting harder. Used to be years ago we just asked you to reverse a string. Now you have to be good at data structures and algorithms.*

I’ve previously written a two part article one common data structure: linked lists

Here are the links:

Linked Lists Part 1
Linked Lists Part 2

Today we’ll look at the next data structure that flows from linked lists and common arrays: the stack.

What is a Stack?

The easiest way to think of a stack is to visualize a stack of pancakes on a plate. When the chef wants to add another pancake to the stack, that new pancake can only be added to the top of the stack. Later, when the chef is ready to serve those pancakes, they can only take the pancakes from the top of the stack.

In other words, whatever goes on the pancake stack first, will go off last. The pancake stack operates under
a system of FILO (First in, last out).

Let’s make a couple of other observations about our pancake stack before we start coding.

1. The only pancake you can actually “see” or peek at is the topmost pancake in the stack.

2. The only way we can access our pancake stack is via the topmost pancake again! We can remove that topmost pancake which will reveal the one below it, then remove that newly revealed pancake and get the one below it and so one until we reach our sticky plate.

3. The pancakes in our stack will know which order they go in since each pancake will “point” to the one below it.

4. The two other things we can do is know how many pancakes are in the stack and state whether there are any pancakes left on the plate, i.e. (isEmpty?).

Getting to the Code

Similar to how we set up the Linked Lists, we’ll need two classes for our stack:

1) a class named “Node” that will create the nodes of information that will go into our stack. The nodes are our pancakes!

2) We’ll also need a “Stack” class where we’ll write our methods we’ll need to manipulate our stacks.

Here’s our skeleton so far:

// class “node” to create the nodes, or “pancakes” that
// will go into our stack:

class StackNode {
  constructor( data, next){
     this.data = data
     this.next = next
  }
}

// Here’s our class where we’ll keep the methods we need
// to manipulate our stack.
// To start each new stack, we’ll begin with a “blank slate”
//  so we’ll set both the “top” (top pancake) and the length
//  of the stack to “null”.

class LinkedStack {
  constructor() {
    this.top = null
    this.size = null
  }
  // methods for our stack will go here
}

Let’s start adding threw easy methods to get us going. We want a method to find out if the stack is empty (isEmpty), get the current length of the stack (getLength) and peek at the top pancake (peek).

for isEmpty all we have to do is see if there is a “top”. We can do this by returning the boolean value to the expression this.top === null

for getLength, we’ll just return the size property which we already initiated in the constructor.

For peek, our constructor provided us with a "top" property, so we just have to return the data in that property to be able to peek.

Let's look at our code now after having added the isEmpty(),getLength() and peek() methods:

class StackNode {
  constructor( data, next){
     this.data = data
     this.next = next
  }
}

class LinkedStack {
  constructor() {
    this.top = null
    this.size = null
  }

  isEmpty(){
    return this.top === null
  }

  getLength() {
     return this.size
  }

  peek() {
    return this.top.data
  }

}

Ok, that much is done! Now let’s look at this picture to figure out what two methods will form the meat and potatoes of our stack implementation. Let’s look at the picture below:

Starting at the left of the picture above, we see an empty stack. To add a node, we need a “push” method. To remove a node, we’ll need a “pop” method (Does this remind you of regular arrays in JavaScript?)

Let’s do one method at a time:

push()

To code out the “push” method, here’s what we’ll need to do:

1. The method will take a value as a parameter. This value is the data for the new node that is about to be pushed on the stack

2. Inside the body of the method, we’ll create a new node with the help of our “stack” class and pass that new node our parameter.

3. Now we want to set our new node’s “next” property to the current top node. In other words, we want our new node to point to the current top.

4. We’ll reset the top of the stack to our new node.

5. Add one to our size property to account for the additional node we just pushed on the stack.
   

push(value) {    //pass in the value for the new node
  let node = new StackNode(value)    // create a new node
 node.next = this.top   // Our new node will point to the  
                                   //  current top node
 this.top = node          // our new node is now set as the top  
                                   //node     
 this.size ++               // increment size by one                           
}    

On to our next method: pop()

pop()

For pop, we want to remove the top node. Here’s how we'll accomplish that:

1. First let save the top node to a variable because we’ll want to return what we popped at the end of the function.

2. Take the current top and set it to the node below it.

3. Decrement size by one to account for the node we just popped.

4. Return the data that was held in the node we popped.

Here's the code for pop():

pop(){
  let poppedNode = this.top   // save the 
                          //node we’ll pop to          
                          // a variable

 this.top = this.top.next    // set the top 
                           //node to be the 
                           // one below it

 return poppedNode.data    // return the data
                        // that was contained
                        // in the poppedNode. 
}

Now let’s put the methods we must wrote back in our LinkedStack class:

class StackNode {
  constructor( data, next){
     this.data = data
     this.next = next
  }
}

class LinkedStack {
  constructor() {
    this.top = null
    this.size = null
  }

  isEmpty(){
    return this.top === null
  }


  getLength() {
     return this.size
  }






  push(value) {    

    let node = new StackNode(value)   
    node.next = this.top                               
    this.top = node                                           
    this.size ++                                         
 }    

  pop(){
    let poppedNode = this.top                                                   
    this.top = this.top.next                                                         
    return poppedNode.data                                            
  }

}

And there you have your basis stack data structure implementation. Next time, let’s have a look at a common algorithm asked in relation to stacks.

In the meantime,

Keep coding out your dreams!

Namaste,

Donny

*One interviewer gave me a standard to achieve: be able to do the problems of medium-difficulty on Leet Code. The problems of high-difficulty are rarely asked. He also noted that, if LeetCode is too hard, you could start with Hacker Rank which tends to be a bit easier than LeetCode.