Stack vs. Queue

In this article, you'll learn:

• What are the differences between stack and queue data structures?
• What do the LIFO principle and FIFO principle mean?
• How do the Java interfaces/classes Stack and Queue differ?

Let's start with the data structures.

Difference between Stack and Queue

A stack is a linear data structure where the elements are inserted and removed according to the LIFO principle ("last-in-first-out"). That means that the element placed on the stack last is the first to be removed – and the element placed on the stack first is removed last.

A queue is a linear data structure in which the elements are inserted and removed according to the FIFO principle ("first-in-first-out"). The first elements to be inserted in the queue are also the first to be removed, and the elements inserted last are removed last.

For more details, such as areas of application and considerations of time complexity, see the main article on the stack data structure and the main article on the queue data structure.

Stack and Queue – Terminology

The insertion and removal operation as well as the sides of the data structures are named differently for stacks and queues:

The "bottom" of the stack is not accessible via the operations.

Difference between Java Stack and Queue

This section describes the differences between the Java class java.util.Stack and the interface java.util.Queue concerning various aspects.

Class vs. Interface

Stack is a class (→ all details about the Stack class), i.e., a concrete implementation of the stack data type in the JDK.

Queue, on the other hand, is an interface (→ all details about the Queue interface). The JDK provides several queue implementations with different characteristics. You can choose a suitable queue implementation according to your application area.

Thread Safety

All Stack methods are synchronized – Stack is, therefore, thread-safe.

However, if we do not need thread safety, synchronization is unnecessary.

And if we need thread safety, the use of pessimistic locking, as synchronized uses it, would only make sense for a high number of access conflicts ("high thread contention"). For moderate access conflicts, optimistic locking would be more appropriate.

For the Queue interface, the JDK offers several implementations:

• non-thread-safe implementations (e.g., ArrayDeque¹)
• thread-safe implementations with pessimistic locking (e.g., LinkedBlockingQueue)
• thread-safe implementations with optimistic locking (e.g., ConcurrentLinkedQueue)

In fact, the JDK developers recommend not to use the Stack class and instead use implementations of the Deque interface, which also defines the stack methods push() and pop().

The JDK also offers numerous implementations for the Deque interface:

• non-thread-safe implementations (e.g., ArrayDeque¹)
• thread-safe implementations with pessimistic locking (e.g., LinkedBlockingDeque)
• thread-safe implementations with optimistic locking (e.g., ConcurrentLinkedDeque)

¹ The Java Deque interface inherits from Queue, therefore, ArrayDeque can be used as both a deque and a queue.

Violation of the Interface Segregation Principle

Both the Stack class and the Deque interface define methods that the respective data structure should not offer. Thus, both violate the interface segregation principle.

Since Stack and Deque ultimately implement the Collection interface, they have methods such as remove(), removeIf(), removeAll(), and ratainAll() that can be used to remove elements from the middle of the data structure.

Stack also has an insertElementAt() method that we can use to insert elements in the middle of the stack.

The articles "Implementing a Stack in Java" and "Implementing a Queue using an Array" show what a Stack and Queue interface should look like.

Summary

This article explained the differences between the stack and queue data structures and the corresponding Java interface and class.

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