You actually already know what a Stack and a Queue are – you just don’t know it. Or, maybe you do! As my good friend, Sandeep would say:

A Stack is a Pringles box

A Queue is a lineup.

Let’s break both of these up into two sections.

The Stack

A stack is a data structure that operates on a ‘First In, Last Out’ basis. You can think of it as an array (or more accurately, an ArrayList if you come from Java) with only two methods: pushOn() and popOff()

The only element that is ever visible on a Stack is the top element (again, think of the Pringles box). Once a new element is pushed on, the previous top element is pushed down while the new element becomes visible. Likewise, when the top element is popped off, the element below it becomes visible. Let’s look at this visually, and then in code:

| element 5 |
| element 4 |
| element 3 |
| element 2 |
| element 1 |
 -----------

Only the 5th element is visible here. The rest are hidden below in a `Stack` formation! The idea here is that you’re restricted by only being able to add and remove to the top of the Stack only. The bottom remains out of your control. Let’s build one with the required methods!

To do this, we’re going to use our old LinkedList class, that we called `Link`.

public class Stack {

    // first item in the stack
    Link top;
    

    void pushOn(int item){
        // create the new item to push on
        Link newItem = new Link(item);
   
        // set the new item's next Link
        // to be equal to the current top Link
        newItem.next = top;

        // set the top item as the new item
        top = newItem;
    }

    Object pop(){

        // if the top exists
        if(top != null){
            // set the item to equal top.data
            int item = top.data;
            // set the top item to be
            // the item directly after it
            // (i.e. top.next)
            top = top.next;
            //return the item
            return item;
        }
        
        // return null if the top is null
        return null;

    }

    int peek(){

        // return the top item's data
        return top.data;
    }

    void printStack(Stack stack){

        while(!stack.isEmpty()){
            System.out.println(stack.peek());
            stack.top = stack.top.next;
        }

    }
}

 

And that’s it! We built a Stack.

The Queue

As Sandeep said earlier, a Queue is just a lineup. Instead of the top item being the one that is visible, a Queue makes the bottom one accessible instead. It’s a ‘First In, First Out’ system – just line a line in the grocery store. Let’s visualize this:

 

——————————————–

Item 5 > Item 4 > Item 3 > Item 2 > Item 1 (this item was the first to be pushed on)

——————————————–

As you can see, item one was the first one pushed onto the Queue, and is also the first one to be accessible as well. Queue’s support pushOn as well as popOff, just like Stacks!

Let’s build one:

public class Queue {

    // the first item is the visible one
    Link first, last;

    void pushOn(int item){

        // check if the Queue is empty
        if(first == null){
           
            // if so, set the last item to the new one
            last = new Link(item);
            
            // set the first equal to the last since
            // there is only one and we need to be able to see it
            first = last;

        } else {

            // if not, set the item after the last one
            // to be our new item
            last.next = new Link(item);

            // and then reassign the last item to be that new one
            last = last.next;
        }

    }

    void popOff(){
        
        // if the first item isn't null - aka the Queue isn't empty
        if(first != null){

            // get the first item 
            Link item = first;
   
            // set the first item to be equal to the second
            first = first.next;
        }

    }

}

That’s all there is to it! Super easy, right? Let’s grab a problem from ‘Cracking the Coding Interview’ and put this knowledge to work.

Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

Let’s dive in. First, we know that we need to iterate through the Stack until it is empty. This gives us the chance to put recursion to work, where our base case is when the unsorted Stack is empty.

Stack sort(Stack unsorted){

    // create a new stack that we will fill
    // with sorted items
    Stack sorted = new Stack();

    // create temp to hold the data
    // while we pop() elements
    int temp = 0;

    // iterate while unsorted isn't empty
    while(!unsorted.isEmpty()){
        
        // start by removing the top
        // element and placing it into temp
        temp = unsorted.pop();

        // iterate while sorted isn't empty AND
        // temp is less that the top sorted element
        while(!sorted.isEmpty() && temp < sorted.peek()){
            unsorted.push(sorted.pop());
        }

        // push the temp onto the sorted stack
        // this is where the first push occurs
        sorted.push(temp);

    }

    // return the sorted stack
    return sorted;

}

Confused a bit? That’s okay, we’ll go over it.

Let’s start with an imaginary Stack:

| 2 |
| 3 |
| 1 |
 ---

 

So, we start with two Stacks – one is unsorted and not empty, while the other is the sorted Stack and IS empty. We start by removing the top element in the unsorted Stack, and pushing it onto the sorted Stack (in this case, we push the 2 onto the sorted stack). Now we have two stacks that look like this:

| 3 |    | 2 |
| 1 |     ---
 ---

 

After that, we pop another element off of the unsorted Stack, in this case 3, and check to see if 3 is less than the top element of the sorted Stack. It’s not, therefore, push the 3 onto the sorted Stack. Now our Stacks look like this:

| 1 |    | 3 |
 ---      | 2 |
           ---

 

But now we run into a problem. You see, when we check if 1 < 3, the condition checks out. Therefore, we push the 3 back onto the unsorted Stack, while removing it from the sorted Stack. Remember, the unsorted Stack is empty because we removed the 1 and stored it in temp.  Now our Stacks look like this:

|   |    | 3 |
 ---      | 2 |
           ---
temp = 1

We pus the 3 and the 2 back onto the unsorted Stack, and then push the 1 onto the sorted stack. Afterwards, we push the 2, followed by the 3 back onto the sorted Stack as well and BAM! Our sorted Stack is well, sorted!

| 3 |
| 2 |
| 1 |
 ---
Advertisements