Home



2019/06 - DS&A #3: Stacks

Hey folks,

Next in this series is the might STACK data structure... And the metaphor we'll be using this time shall be a book stack! A stack is exactly what it sounds like: A 'stack' of 'things'.

In real life we stack objects up (books for example) so that we can keep rooms tidy and save space. In computer science, a stack is used to guarantee that data is stored in a particular way so that we know what data will be returned based on the order that the contents of the stack were added in. That order for the Stack is last-in-first-out, meaning that the lasr piece of data added will be the first data removed when removal occurs. We could have logic in our stack implementation that mirrors how we stack books in real life (In order for it to actually be useful). For example, we could only allow books that weigh less than the book that was last added to be added. We do this in real life too to avoid having our stack of books fall over due to being top-heavy.

Metaphor aside, there are several specific actions that Stacks should be able to perform that you can also do in real life:

 

So with that said, let's dive into some code (The data storage actually uses the official Java API Linked List, hence why you're going to see some new methods that I didn't cover in the Linked List post):

Standard setup:

package com.dsaa.stack;

import java.util.LinkedList;

public class Stack<T> {
    
    //Last-In-First-Out
    private LinkedList<T> listOfNodes;
    private int count = 0;
    
    public Stack() {
        listOfNodes  = new LinkedList<T>();
    }   

 

We're just adding a node to the front of our Linked list here. It's important to add to the front for a stack, and nowhere else, because added a book to the bottom of a big stack of books is difficult and you look silly when trying to do so:

    public void push(T node) {
        listOfNodes.addFirst(node);
        count++;
    }

 

We look at the front of our Linked List, which will always be the most recently added book that's still in the list, because we only ever add books to the front of the list:

    public T peek() {
        if(!listOfNodes.isEmpty()) {
            return listOfNodes.getFirst();
        }
        else {
            return null;
        }
    }

 

Pop just removes the book from the front of the list, which it'll always do (Keeping the whole stack in order!):

    public T pop() {
        count--;
        return listOfNodes.removeFirst();
    }

 

Lastly, clear just resets the whole stack. You could rename this to karateKick() if you wanted. But you might want to make it thrown a new MessyRoomException if you decide to do so.    

public void clear() {
        listOfNodes.clear();
        count = 0;
    }
    

 

Honestly, this method should be written much higher up in the class, but I'm on a train with dodgy internet right now so can't fix the repo:

    public int count() {
        return count;
    }

}

 

So that's it for Stacks. They're pretty straightforward and there's not much to them. Most data structures are like this until you get to balancing AVL trees...

But we'll save that for another post, good luck!