Data structures 101: How to use stacks and queues in Java

Mastering data structures is non-negotiable. Efficient data structures help execute effective programs. Today, many programming roles require great knowledge of data structures. They are also a fundamental part of coding interviews.

Stacks and queues are linear data structures that follow a particular order to add or remove entities. In this article, you will be introduced to stacks and queues. We will highlight their uses, functionalities, and show you how to implement these data structures in Java.

Today, we will cover:

• What is a Stack?
• What is a Queue?
• Pros and Cons of Stack and Queues
• Essential operations
• How to implement a Stack in Java
• How to implement a Queue in Java
• What to learn next & interview questions

Master data structures for coding interviews with hands-on practice

Learn data structures with practical, real-world problems from coding interviews.

Data Structures for Coding Interviews in Java#

What is a Stack?#

In programming, a stack is an abstract, linear data type with a predefined capacity (or boundary). It follows a particular order for adding or removing elements. Linear data structures organize their components in a straight line, so if we add or remove an element, they will grow or shrink respectively.

Let us conceptualize stacks using a stack of plates placed in a box. The first plate placed in the stack (the plate at the bottom of the stack) will be the last one to be removed, and the plate added last would be the first to be removed.

This is called the Last In First Out (LIFO) or First In Last Out (FILO) ordering.

Stacks are used in a variety of ways when we code. We use stacks to implement functions, parsers, expression evaluation, and some algorithms. Stacks are great for processing nested structures, so they are important for understanding recursion.

A simple real-world application of a stack is reversing a string letter by letter. Another good example of a data stack is the undo and redo function on a computer or text editor. Undo removes your most recent change, and redo builds upon already existing changes.

How do Stacks work?#

The implementation of stacks is relatively easy. The functionality depends on the pop and push method, as you can see from the illustration above. The pop method removes or deletes elements from the stack, while the push method adds items to the stack.

When an element is inserted into a stack, it takes the top position and the variable storing this position points to the number below it. The top variable should be updated anytime an element is inserted or removed from it.

Note: What’s important to remember is that insertion and deletion happen on the same end of a Stack.

Later in this article, we will learn how to manually implementing the Stack data structure in Java.

What is a Queue?#

A queue is a lot like a stack. A Queue is also a linear structure that follows a First In First Out (FIFO) order, but they differ in how elements are removed. Queues are open from both ends: one end for inserting data (enqueue), and the other end for removing data (dequeue). A stack is only open from one end.

Simplied: for a stack we remove the most recently added element, but for a queue, we remove the “oldest” element.

When it comes to queues, think of a check out counter at your favorite grocery store. The first person in the checkout line will be attended to first before others, and the last person in line will be attend to last. This is how a queue works. It has two ends, front and rear. Elements enter from the rear and leave from the front.

Types of Queues#

There are three common types of queues you can expect to encounter. So far, we learned about the Linear Queue. The other two queues are:

1. Circular Queue: In a circular queue, the last element is connected to the first element to form a circle. Initially, the front and rear parts of the queue point to the same location, but they move apart as more elements are inserted into the queue. A real-life example of a circular queue is an automated traffic signal system.

2. Priority Queue: In priority queues, elements are sorted based on priority. The most important element appears first, and the least important appears last. Priority queues are used in operating systems for load balancing to determine which programs should be given more priority.

Pros and Cons of Stack and Queues#

Essential Operations for Stacks & Queues#

A typical stack must contain the following methods:

• pop(): this method removes an element from the top of the stack and returns it.
• push(): this method adds an element to the top of the stack.

A queue allows for the following operations:

• enqueue(): this method adds an element to the end/rear of the queue
• dequeue(): this method removes an element from the front of the queue
• top(): returns the first element in the queue
• initialize(): creates an empty queue

From there we can apply all sorts of methods for more functionality and information retrieval:

• top(): returns the element most recently added to the stack
• intStack.peek(): returns the top of the stack without removing an element
• poll(): removes the head of a queue and returns it
• size(): returns the size of the queue as number of elements
• isEmpty(): returns true if the stack/queue is full
• isFull(): returns true if the stack/queue is full

How to implement a Stack in Java#

Every programming language comes with basic functionality for stacks. However, in Java, the stack data type is an Adapter class. This means that it is built on top of other data structures. Therefore, it can be implemented using an Array, Vector, Linked List, or any other collection.

Note: Stacks are generally implemented using Arrays because it takes less memory.

Irrespective of the underlying data structure or programming language used, stacks must implement the same basic functionalities. In Java, you can import a pre-built class of stack or manually implement a stack and extend its functionality. To implement the built-in Stack class, we use the java.util package using the following import statement:

import java.util.*;
// or
import java.util.Stack;

Once we import the package, we can create a stack object like this:

Stack mystack = new Stack();

Then, we add elements to the stage. We could, for example, add integers using push().

Stack<Integer> myStack = new Stack<>();
 myStack.push(5);
 myStack.push(6);
 myStack.push(7);

The basic syntax will look like this:

public class Stack <V> {
    private int maxSize;
    private int top;
    private V arr[];

To make a stack manually, we construct a class of Stack and create an instance. This class has the following three data members:

• An array that will hold all the elements
• The size/boundary of this array
• A variable for the top element of the stack

The following code shows how to construct the Stack class:

Before adding the push and pop methods into this code, we need to implement some helper methods. Helper methods keep the code simple and understandable. Here’s the list of helper functions that we will implement in the code below:

• isEmpty()
• isFull()
• top()

Here is the code for stacks with the new helper methods.

If your output returns true for isEmpty() and false for isFull(), it means that these helper functions are working properly! Now, take a look at this extended code with push and pop functions added to the definition of Stack class. We will try to add and remove some elements from this stack.

In the code output, you can see that the elements popped out of the stack in the exact reverse order as they were pushed in. That means our stack works perfectly.

How to Implement a Queue in Java#

The most common queue implementation is using Arrays, but it can also be implemented using Linked Lists or by starting from a Stack. We can import the queue interface with this command:

import java.util.queue;
// or
import java.util.*;

We then create a queue interface with the following statement, which creates a linked list for our queue, and provide values:

Queue<String> str_queue = new LinkedList<> ();
str_queue.add(“one”);
str_queue.add(“two”);
str_queue.add(“three”);

Let’s see a manual example of a Queue class with an integer data type and create an instance. The class would hold 5 data members to hold the following information:

• An array that will contain all the elements
• The maxSize is the size of this array
• The front element of the Queue
• The back element of the Queue
• The currentSize of elements in the Queue

The code given below shows how to construct the Queue class:

Before adding the enqueue and dequeue methods into this class, we need to implement some helper methods. The aforementioned helper method would be used here. Now run the following code and see if the helper function outputs correctly.

For the above code, since the queue is empty, isEmpty() should return true, and isFull() should return false. Now, we will extend this code with the enqueue method to add elements and the dequeue method to remove elements from the queue.

Take a look at the output of the code and take note that the elements are enqueued in the back and dequeued from the front. This means that our queue works perfectly.

What to learn next & interview questions#

You made it to the end of this article. Congratulations! I hope you now have a good foundation of how stacks and queues data structures work. There’s so much more to learn to master queues and stacks in Java. Here are some of the common interview challenges for these data structures:

• Implement a Queue using Stacks
• Generate Binary Numbers from 1 to n using a Queue
• Evaluate Postfix Expressions using Stacks
• Implement two stacks using one array
• Reversing the First k Elements of a Queue
• Create Stack where min() gives minimum in $O(1)$
• and more

To get started on these questions, check out Educative’s course on Data Structures for Coding Interviews in Java. It will give you a detailed explanation of all common Java data structures with solutions to real-world data structure problems. By the end, you’ll be an intermediate Java programmer, ready to conquer coding interviews!

Happy learning!

Continue reading about data structures and Java#

• Java 8 Tutorial: master stream API and beyond
• Java interview prep: 15 Java interview questions
• Top Data Structures and Algorithms every developer must know