9) Data Structures & Algorithms Lesson

Stacks in Java

8 min to complete · By Ryan Desmond

Contents

  1. Introduction
  2. How Does a Stack Work
    1. Primary Stack Methods
  3. Summary: What is a Stack in Java
    1. Big O Notation of a Stack
    2. Primary Stack Methods

A Stack is a common data structure that implements "Last In First Out" (LIFO) behavior. This can also be reversed to state a Stack as "First-In-Last-Out" (FILO) because it means the same thing.

Much like a stack of plates on your counter, the plate at the bottom (the one you put down first) will be the last one you will retrieve from the stack. 

A stack of white dinner plates.

Java provides a Stack class for you to use, but it's also quite simple to create your own custom Stack class.

Components of a Stack

As with several other data structures, beneath the covers of a Stack, there is another underlying data structure. Most commonly, this is either a simple Array or, even better, a LinkedList.

The Stack class simply adds functionality on top of the underlying Array or LinkedList. This functionality controls how you add, find, and remove elements from the stack so that it enforces the FILO functionality. If you remember from previous lessons, abstract data structures are defined by their behavior, not their structure.

Big O Complexity for a Stack

Adding and removing from Stack is constant time - aka $`O(1)`$. This is because you're always adding to or removing from the very top of the stack. To search and gain access to an element in a Stack the complexity is $`O(n)`$. That said, beyond an options contains() method there is no real reason to need to search or access an element in a Stack. The very nature of the Stack is to only allow adding and removing elements from the top of the Stack. Just like the stack of dinner plates on your counter. You add plates and remove plates from the top of the Stack.

Also, you may have noticed that this is the same complexity as the LinkedList! A Stack and a LinkedList are similar in many ways. So much so that a LinkedList is often used as the underlying data structure for a Stack.

How Does a Stack Work

A stack simply enforces a particular set of behaviors. For instance, if the underlying data structure is an Array, you simply enforce the idea that a user can ONLY insert elements onto the top of the stack and users can ONLY remove elements from the top of the stack. You would do this by using, for instance, using a variable that points to a particular index in your array. The variable, currentTop, for instance, would point at the index of the most recently inserted element. Then, for a pop() you would simply return and remove the element in the array at currentTop. If you wanted to push() to the Stack you could add that element to the array at the index of currentTop + 1. Then you would want to increment currentTop.

Colorful illustration of a light bulb

**Quick Tip: You can shorten the previous two steps of 1) currentTop + 1 then 2) currentTop++ in the example above to ++currentTop. This will increment currentTop by 1 and then perform whatever operation follows. For instance array[++currentTop] = "newValue"; This will increment currentTop first, then use that incremented value as the index for where to insert "newValue".

A Stack is a limited-access data structure. Meaning that you limit access to the underlying data. You can only add and remove from the top of the Stack. Therefore, it is NOT random access. You cannot get a plate out of the middle of the stack. You can ONLY add and remove from the top.

graphic showing the first in, last out behavior of a Stack data structure

Primary Stack Methods

The three common methods when working with a Stack are:

  1. push() to add elements to the Stack 
  2. pop() to remove elements from the Stack
  3. peek() view the element at the top of the Stack without removing
  4. empty() empty the Stack
  5. search() search the Stack
Colorful illustration of a light bulb

If you'd like to continue learning about Stacks, check out the lesson in the Data Structures & Algorithm course:

Summary: What is a Stack in Java

  • A Stack is a common, built-in data structure provided by Java
  • Stacks implement the First in, Last Out (FILO) behavior
  • FILO is synonymous with Last In, First OUT (LIFO) behavior
  • Stacks are usually built on top of either an Array or a LinkedList - a LinkedList is more efficient
  • Stacks are limited access - not random access. You can only add and remove data from the top of the Stack

Big O Notation of a Stack

  • Best Case (Insert & Remove): O(1)
  • Worst Case (Access & Search): O(n)

Primary Stack Methods

  • push()
  • pop()
  • peek()
  • empty()
  • `search()``
Previous Next → Code Playground: Stacks