Stacks

 Imagine you’ve just unloaded the dishwasher, and you’ve created a stack of plates. What can you do? You can see what the top plate is, you can add plates to the top, you can count how many plates there are, and you can remove the top plate to get access to plates underneath it.

Java has a data structure that behaves exactly like the stack of plates—the Stack. A stack has several operations like we’ve already seen with other data structures: you can add and you can remove, but, just like we saw with queues, how you do that (where you have access) has special meaning.

As I alluded to last time, looking at queues, some data structures preserve special ordering: the FIFO queue of people at the checkout counter, or the LIFO stack of plates in the cupboard. You can’t see the bottom plate, nor can you add, remove, or check out some random plate in the middle—everything you do must be done to the top visible plate. It's for this reason that a stack is LIFO-- the last thing to be added is the first to come off.

A queue, recall, lets you access only the oldest thing. A stack, by contrast, allows you to access only the newest thing. Think about it - again, with the stack of plates. (Go get a literal stack of plates or maybe books, and put numbers on sticky notes on each plate or book; I promise it’ll help.) When you add to a stack, you can only do so to the top. When you take away from a stack, you can only do so from the top. When you look at a value in a stack, you can only see the top element’s value, not the values of anything under it. 

Stacks call the “add” operation “push,” and the “remove” operation “pop.”  There are certainly problems in which asking if there is anything left in the stack (Think about why? perhaps… because a loop has been running?), so you can do so by calling isEmpty(), which, naturally, returns a Boolean: true if it’s empty, and false otherwise. (This can make working with this call quite annoying, since the resulting Boolean answers “is there nothing?” when the more natural question is probably “is there anything here?”, which is exactly the opposite)

import java.util.Stack;

 

public class StackExample {

    public static void main(String[] args) {

        // Create a stack

        Stack<Integer> stack = new Stack<>();

 

        // Push elements onto the stack

        stack.push(1);

        stack.push(2);

        stack.push(3);

 

        System.out.println("Stack: " + stack);

 

        // Peek at the top element (without removing)

        System.out.println("Top element (peek): " + stack.peek());

 

        // Pop the top element (remove and return)

        int poppedItem = stack.pop();

        System.out.println("Popped element: " + poppedItem);

 

        System.out.println("Stack after pop: " + stack);

    }

}

By now, I’m sure you’ve been working with imports for a while, so seeing that you have to pick it up from java.util should be nothing new. Get in the habit, at least in the beginning of typing out that import yourself, if only so you commit to memory that Stack lives in util. Once you’ve really got stacks down, you can save a second or two by not typing it yourself, writing the rest of your code, and letting the IDE realize for you that you need to put in the import (which the IDE will either do automatically, or which you’ll approve by the click of a button).

Stacks, again, use generics, including the wrapper classes for the primitive types. They’ll be covered in the next post! Stay tuned!