Data Structures in Java: List, Stack, Queue and Set - Quiz

A data structure is a way to organize a group of elements together with rules for accessing them: by index, only the most recently added element, only the oldest one, or without duplicates.

The basic data structures fall into four kinds: the list (access by index, duplicates allowed), the stack (LIFO), the queue (FIFO) and the set (no duplicates). The map (dictionary) for key–value pairs stands apart. In Java they are described by the List, Deque, Queue, Set and Map interfaces of the Collections Framework.

A stack follows LIFO (Last-In-First-Out): elements are added (push) and removed (pop) at the same end, and only the most recently added element is accessible. Think of a stack of plates. Stacks are used for undo, bracket matching and depth-first traversal; the JVM call stack works the same way.

A queue follows FIFO (First-In-First-Out): elements are added at the tail and removed from the head, so they leave in the order they arrived. Think of a checkout line. Queues are used for print jobs, request processing and breadth-first traversal.

Both allow duplicates and give no access to elements in the middle. In Java a stack is a Deque and a queue is a Queue; both can be implemented with ArrayDeque.

A list is an ordered sequence in which every element has an index (starting at 0) and equal elements may repeat. You can access any element by index and insert or remove elements anywhere. In Java: the List interface with ArrayList and LinkedList.

A set is a group of elements with no duplicates and no indexes. Its main operation is a fast check whether an element is present; adding an existing element changes nothing and add() returns false. In Java: the Set interface — HashSet guarantees no order, LinkedHashSet keeps insertion order, TreeSet keeps elements sorted.

A map (dictionary, associative array) stores key–value pairs. Keys are unique, like the elements of a set, while values may repeat. A value is found by its key rather than by an index — like a phone number looked up by name in a phone book.

In Java a map is described by the Map interface with the HashMap, LinkedHashMap and TreeMap implementations.

A double-ended queue (deque, the Deque interface) lets you add and remove elements at both ends. If you work with one end only (push()/pop()), you get a stack; if you add at the tail and remove from the head (offer()/poll()), you get a queue.

That is why ArrayDeque replaces both the legacy Stack class and a plain queue: Deque<Integer> stack = new ArrayDeque<>();

An array's size is fixed when it is created, while a list grows and shrinks as elements are added and removed. An array can hold primitives (int[]), whereas a list holds only objects (List<Integer>).

Inside an ArrayList there is a plain array that is replaced with a larger one when it fills up.