Stack Data Structure

In this tutorial, you will learn everything about the abstract data type "Stack":

• How does a stack work?
• What are the applications of stacks?
• How to use the Java class "Stack"?
• How to implement your own stack in Java?

What is a Stack?

A stack is a collection of elements in which the elements can be inserted into and removed from only one side (typically the top in graphical representations).

The best way to think of a stack is as a stack of plates:

We can only place new plates on top of the stack, and we can only remove them from the top.

Since this means that the last plate added is the first to be removed, we refer to this as the last-in-first-out (LIFO) principle.

LIFO Principle for Stack

For the abstract data type "stack", this could look something like the following:

The image shows a stack that contains several strings. The next element to be placed on the stack is "grape". Then, we would also have to take "grape" out first.

A stack data structure typically provides the following operations:

• "Push": Adding an element to the stack.
• "Pop": Removing an element from the top of the stack.
• "Peek" or "Top": Looking at the top element of the stack without removing it.
• A check if the stack is empty.

Applications for Stacks

For example, you can think of the web page history within a browser tab as a stack: Each time you click a link, the previous URL is placed on a stack. When you press the back button, the top URL of the stack is retrieved and displayed again.

Similarly, when a method is called in a computer program, the return address is placed on the so-called "call stack". After the method has been executed, the program can jump back to the call position. You may have encountered a StackOverflowError caused by too deep nesting.

Compilers and parsers also use stacks, e.g., when processing XML and JSON documents or evaluating mathematical expressions.

Time Complexity of Stack Operations

You can find an introduction to the topic of time complexity in the article "Big O Notation and Time Complexity – Easily Explained".

UsUsually, we implement a stack with an array or a linked list. In both variants, the cost of inserting or removing an element is constant and does not depend on the number of elements present in the stack.

The time complexity is, therefore: O(1).

Stacks can also be implemented with queues – however, that's more for training purposes. The time complexity is higher then. You can read more about this in the corresponding part of the tutorial.

If you have any questions, please ask them via the comment function. Would you like to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.