Deque

Key Features and Methods of Java Deque

●​ Creation:
○​ Deque instances can be created using classes like​
ArrayDeque or LinkedList.

●​ Adding Elements:
○​ addFirst(element), offerFirst(element): Add elements to the front of
the deque.
○​ addLast(element), offerLast(element): Add elements to the end of
the deque.
●​ Accessing Elements:
○​ getFirst(), peekFirst(): Access the first element without removing it.
○​ getLast(), peekLast(): Access the last element without removing it.
●​ Removing Elements:
○​ removeFirst(), pollFirst(): Remove and return the first element.
○​ removeLast(), pollLast(): Remove and return the last element.
●​ Other Useful Methods:
○​ isEmpty(): Check if the deque is empty.
○​ size(): Get the number of elements in the deque.
○​ Iteration, conversion to array, and more.
 ●​ In this Java example, an ArrayDeque is used to demonstrate the basic
operations of a deque, such as adding, accessing, and removing elements
from both ends.
●​ The ArrayDeque class is a resizable-array implementation of the Deque
interface, offering a convenient way to use double-ended queues in Java.

List in Java

●​ In Java, the closest equivalent to the C++​

list (a doubly-linked list) is the LinkedList class, which is part of the Java
Collections Framework.
 ●​ LinkedList in Java allows for efficient insertion and deletion of elements
anywhere within the list.

Vector vs Deque vs LinkedList Time Complexity in Java

Operation ArrayList Deque LinkedList

(ArrayDeque)

Back (Last
O(1) O(1) O(1)
Element)

Front (First
O(1) O(1) O(1)
Element)

O(1) at both O(1) at both

Insert O(n)
ends ends
 ●​ LinkedList<Integer> list1: Declare a LinkedList named list1 to store integers.
●​ list1.addLast(element): Adds element to the back of list1.
●​ list1.addFirst(element): Adds element to the front of list1.
●​ list1.get(): Accessing elements by index is allowed in Java's LinkedList.
●​ list1.removeLast(): Remove the last element from list1.
●​ list1.removeFirst(): Remove the first element from list1.
●​ list1.getLast(): Get the last element of list1.
●​ list1.getFirst(): Get the first element of list1.

Stack

A stack, follows Last-In, First-Out (LIFO) principle meaning that the last element
added to the stack is the first one to be removed, is a linear data structure with
fundamental operations including push, pop, and auxiliary functions like top, size,
empty, and swap.

Real Life Use Case

●​ In the analogy of kitchen plates, pushing washes and adds a plate to the
stack, while popping retrieves the top plate for use.
●​ "Empty" checks if plates remain, "top" shows the top plate, and "size"
indicates the stack's plate count.
●​ For exchanging stacks, "swap" is employed.

Java Stack Class

●​ In Java, the stack functionality can be achieved using the​

Stack class from the java.util package.
●​ A​
Stack in Java follows the Last-In, First-Out (LIFO) principle, where the last
element added to the stack is the first one to be removed.
●​ This class provides methods for standard stack operations like push, pop,
peek, and auxiliary functions like empty, search, and more.

Key Features and Methods of Java Stack

●​ Creation:
○​ A Stack can be created as an instance of the​
Stack class.

●​ Adding Elements:
○​ push(element): Pushes an element onto the top of the stack.
●​ Removing Elements:
○​ pop(): Removes and returns the top element of the stack.
●​ Accessing the Top Element:
○​ peek(): Looks at the top element of the stack without removing it.
●​ Checking if Stack is Empty:
○​ empty(): Tests if the stack is empty.
●​ Searching for Elements:
○​ search(element): Returns the 1-based position of the element from the
top of the stack.
●​ Size of the Stack:
○​ While there's no direct size() method, you can use stackName.size()
inherited from Vector class to get the stack size.
Queue
 ●​ In Java, the functionality similar to C++'s STL​
queue is provided by the Queue interface in the java.util package.
●​ A Queue in Java follows the First-In-First-Out (FIFO) principle, where the first
element added to the queue is the first to be removed.
●​ The​
Queue interface is typically implemented by classes like LinkedList,
ArrayDeque, and PriorityQueue.

Key Features and Methods of Java Queue

●​ Creation:
○​ A Queue instance is typically created as a​
LinkedList or ArrayDeque.

●​ Adding Elements:
○​ offer(element): Adds an element to the back of the queue. Preferred
over add(element) as it returns false instead of throwing an exception
for capacity-restricted queues.
○​ add(element): Also adds an element to the queue.
●​ Removing Elements:
○​ poll(): Removes and returns the head of the queue, or returns null if
the queue is empty.
○​ remove(): Similar to poll(), but throws an exception if the queue is
empty.
●​ Accessing Elements:
○​ peek(): Retrieves, but does not remove, the head of the queue,
returning null if the queue is empty.
○​ element(): Similar to peek(), but throws an exception if the queue is
empty.
●​ Other Useful Operations:
○​ size(): Returns the number of elements in the queue.
○​ isEmpty(): Checks if the queue is empty.
 ●​ In this Java example, a​
LinkedList is used to demonstrate basic queue operations like offering
(adding), polling (removing), and peeking (accessing the front element).
●​ Unlike C++'s​
queue, Java's Queue interface does not directly support accessing the back
element, and the implementation class (like LinkedList or ArrayDeque)
determines specific behaviors and performance characteristics.

Priority Queue in Java

●​ In Java, a priority queue is a container for elements that are arranged in a
specific priority order.
●​ By default, the highest-priority element is at the front of the queue.
●​ Priority queues are often implemented as binary heaps, which offer efficient
operations to maintain the highest-priority element at the top.
●​ ​
PriorityQueue<Integer> maxHeap: Declare a max-heap priority queue
named maxHeap for storing integers. It's initialized as a max-heap by using
Collections.reverseOrder() as the comparator.
●​ maxHeap.add(): Push elements into the max-heap priority queue.
●​ maxHeap.peek(): Print the top element (with the highest priority) without
removing it.
●​ maxHeap.poll(): Remove the top element from the max-heap priority queue.
●​ maxHeap.size(): Print the size of the max-heap priority queue.
●​ maxHeap.isEmpty(): Check if the max-heap priority queue is empty.
●​ maxHeap2.addAll(maxHeap): Swap the content of the first max-heap priority
queue with the second one by adding all elements from maxHeap to
maxHeap2.
 ●​ PriorityQueue<Integer> minHeap: Declare a min-heap priority queue named
minHeap for storing integers.
●​ minHeap.add(): Push elements into the min-heap priority queue.
●​ minHeap.peek(): Print the top element (with the lowest priority) without
removing it.
●​ minHeap.poll(): Remove the top element from the min-heap priority queue.
●​ minHeap.size(): Print the size of the min-heap priority queue.
●​ minHeap.isEmpty(): Check if the min-heap priority queue is empty.
●​ minHeap2.addAll(minHeap): Swap the content of the first min-heap priority
queue with the second one by adding all elements from minHeap to
minHeap2.

Set in Java

A Set is a container in Java that stores unique elements in a sorted order and does
not allow duplicate values.

Set can be implemented using:

●​ LinkedHashSet
●​ TreeSet

Properties

●​ Ordered: Yes, maintains the order of elements as they were inserted.

●​ Unique: Yes, only allows unique elements without duplicates.

LinkedHashSet in Java

●​ It is a variant of the HashSet that combines hash table and linked list
structures to maintain a doubly-linked list across its elements.
●​ This hybrid structure allows LinkedHashSet to order its elements based on the
sequence of their insertion, thus preserving the insertion order.
●​ It inherits from the HashSet and implements the Set interface.

Basic Operations
●​ Adding Elements: Inserts elements into the set without duplicating values.
If an attempt is made to add a duplicate, it is ignored.
●​ Removing Elements: Deletes a specified element from the set.
●​ Iteration: Provides an iterator that follows the insertion order of the
elements.
●​ Checking for Elements: Checks whether a specific element exists in the
set.
●​ Size and Cleanup: Returns the number of elements and clears all
elements from the set.
TreeSet in Java

●​ It is an implementation of the Set interface that uses a tree for storage.

●​ Elements in a TreeSet are sorted according to their natural ordering, or by a
Comparator provided at set creation, ensuring that the set is always in
ascending order.
●​ This makes TreeSet an excellent choice for storing ordered collections that
must also be free of duplicates.

Properties

●​ Sorted: Yes, elements are sorted automatically either by natural ordering or

by a specified Comparator.
●​ Unique: Yes, like other sets, it allows only unique elements and no
duplicates.

Basic Operations

●​ Adding Elements: Adds new elements to the set in sorted order. If a

duplicate is added, it is not inserted.
●​ Removing Elements: Removes a specified element from the set.
●​ Iteration: Provides an iterator to traverse the set in ascending order of the
elements.
●​ Checking for Elements: Verifies the presence of an element in the set.
●​ Size and Cleanup: Gives the number of elements in the set and clears all
elements.
Multi-Set in Java
●​ A Multi-Set in Java, also known as a Bag, is a container that allows you to
store multiple values of the same type in a sorted order.
●​ Unlike a Set, it can contain duplicate elements.

Properties

●​ Sorted: Yes, the elements are stored in sorted order.

●​ Unique: No, it allows duplicate elements.
 ●​ Multiset<E>: A custom class to create a Multi-Set using a TreeMap that
tracks element counts.
●​ multiset.add(): Insert elements into the multiset using the add method.
●​ multiset.remove(): Erase elements from the multiset using the remove
method.
●​ Iterator: No direct iterator; use elementSet() to get a set of unique elements
for iteration.
●​ multiset.count(): Count the occurrences of a specific element in the multiset.
●​ multiset.size(): Returns the size.

Unordered Set in Java

 ●​ An Unordered Set in Java is represented by the​
HashSet class from the Java Collections Framework.
●​ It is a container that stores a collection of unique elements without maintaining
a specific order among the elements.

Properties

●​ Sorted: No, the elements are stored in a random order.

●​ Unique: It allows only unique elements.
●​ HashSet<Integer> mySet: Declare a HashSet for storing integers.
●​ mySet.add(): Insert elements into the mySet using the add method.
●​ mySet.remove(): Remove elements from the mySet using the remove
method.
 ●​ mySet.contains(): Use the contains method to check if a specific value exists
in the mySet.
●​ Iteration: You can iterate through the elements of the mySet using a for-each
loop or an iterator. The order of iteration is random.

Complexity Analysis

Operation Set Multi-Set Unordered Set

O(1), worst case -

insert() O(log n) O(log n)
O(n)

O(1), worst case -

erase() O(log n) O(log n)
O(n)

O(1), worst case -

find() O(log n) O(log n)
O(n)

O(1), worst case -

count() O(log n) O(log n)
O(n)

In Java, the HashSet provides constant-time average complexity for basic

operations, but worst-case complexity for certain operations can be O(n) when
dealing with hash collisions.