3 - Set, Stack, Queue

1. Set, Stack, Queue

2. Set

Set is a collection that does not allow duplicate elements.
1
5
3
1
5
1
3
1
3

3. HashSet

A HashSet in Java is a collection that does not allow duplicate elements and does not maintain
any specific order of elements. It is implemented using a hash table, providing fast operations with
an average time complexity of O(1) for add, remove, and lookup operations.
Creating an HashSet:
HashSet<Type> set = new HashSet<>();
Here, Type refers to the data type (e.g., Integer, String, Double, etc.).

4. Key Points of HashSet:

No Duplicates – Each element in a HashSet must be unique.
Unordered Collection – Elements are stored in an arbitrary
order (not sorted).
Allows Null Values – Can contain at most one null element.
Fast Performance – Provides constant-time complexity (O(1))
for basic operations.

5. Input and Output in a HashSet

Scanner input = new Scanner(System.in);
HashSet<String> wordset = new HashSet<>();
int n = input.nextInt();
for(int i=0; i<n; i++){
String word = input.next();
wordset.add(word);
}
System.out.println(wordset);
Input:
5
hello
hi
hello
hi
hi
Output:
[hi, hello]

6. HashSet Methods

HashSet<String> set= new HashSet<>();
Method
Description
Example
add(E e)
Adds an element to the set. Returns false if it
already exists.
set.add("Apple");
addAll(collection)
Adds all elements from another collection.
set.addAll(list);
remove(Object o)
Removes the specified element.
set.remove("Banana");
clear()
Removes all elements.
set.clear();
size()
Returns the number of elements in the set
set.size();

7. Examples

HashSet<Integer> set = new HashSet<>();
set.add(10);
set.add(51);
set.add(3);
set.add(5);
set.add(3);
set.add(1);
set.add(5);
set.remove(1);
System.out.println(set);
set.clear();

8. HashSet Methods

HashSet<String> set= new HashSet<>();
Method
Description
Example
contains(Object o)
Checks if an element exists in the set.
set.contains("Apple");
isEmpty()
Checks if the set is empty.
set.isEmpty();
toArray()
Converts the set to an array.
Object[] arr = set.toArray();
retainAll(collection)
Keeps only the elements that are also in the given
collection.
set.retainAll(otherset);
removeAll(collection)
Removes all elements present in another
collection.
set.removeAll(otherset);

9.

A.removeAll(B)
A.retainAll(B)
AUB = A.addAll(B)

10. Examples

HashSet<Integer> setA = new HashSet<>();
HashSet<Integer> setB = new HashSet<>();
setA.add(2);
setA.add(5);
setA.add(3);
setB.add(1);
setB.add(3);
setB.add(2);
// setA.retainAll(setB); - intersection
// setA.removeAll(setB);- only SetA
setA.addAll(setB);
System.out.println(setA);

11. Create HashSet from an ArrayList

ArrayList<Integer> list = new ArrayList<>();
list.add(12);
list.add(45);
list.add(12);
list.add(5);
HashSet<Integer> set = new HashSet<>(list);
System.out.println(set);
Output:
[5, 12, 45]

12. Create an ArrayList from HashSet

HashSet<Integer> set = new HashSet<>();
set.add(12);
set.add(45);
set.add(12);
set.add(1);
set.add(5);
ArrayList<Integer> list = new ArrayList<>(set);
Collections.sort(list);
System.out.println(list);
Output:
[1, 5, 12, 45]

13. Stack vs Queue

14. Stack vs Queue

● A Stack is a Last In, First Out (LIFO) structure where elements are added and
removed from the same end (the top).
A Queue is a First In, First Out (FIFO) structure where elements are added at the end
and removed from the front.

15. ArrayDeque

ArrayDeque is part of Java's java.util package, and it is a resizable array
implementation of the Deque interface, which stands for Double Ended Queue. It
allows elements to be added and removed from both ends (head and tail) of the queue
efficiently.

16. Key features of ArrayDeque

Resizable Array: The internal array grows automatically as needed.
Fast Operations: Provides O(1) time complexity for add and remove operations at
both ends.
Does not allow null elements.
Implements the Deque interface, which means it can function as both a Queue and a
Stack.

17. Creating an ArrayDeque

ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addLast(10);
deque.addFirst(5);
deque.addLast(20);
System.out.println(deque);
Output:
[5, 10, 20]

18. ArrayDeque Methods

ArrayDeque<Integer> deque = new ArrayDeque<>();
Method
Description
Example
addFirst(E e)
Adds an element to the front of the deque.
deque.addFirst(1);
addLast(E e)
Adds an element to the end of the deque.
deque.addLast(10);
size()
Returns the number of elements in the deque.
deque.size();
isEmpty()
Checks if the deque is empty.
deque.isEmpty();

19. ArrayDeque Methods

ArrayDeque<Integer> deque = new ArrayDeque<>();
Method
Description
Example
removeFirst()
Removes and returns the first element.
deque.removeFirst();
removeLast()
Removes and returns the last element.
deque.removeLast()
getFirst()
Returns the first element without removing it.
deque.getFirst();
getLast()
Returns the last element without removing it.
deque.getLast();

20. Stack

ArrayDeque<Integer> stack = new
ArrayDeque<>();
stack.addLast(6);
stack.addLast(34);
stack.addLast(23);
while(!stack.isEmpty()){
int value = stack.removeLast();
System.out.println(value);
}
Output:
23
34
6

21. Queue

ArrayDeque<Integer> queue = new
ArrayDeque<>();
queue.addLast(6);
queue.addLast(34);
queue.addLast(23);
while(!queue.isEmpty()){
int value = queue.removeFirst();
System.out.println(value);
}
Output:
6
34
23

22. ArrayDeque Methods

ArrayDeque<Integer> deque = new ArrayDeque<>();
Method
Description
Example
peek()
Retrieves, but does not remove, the head of the queue represented by
this deque, or returns null if this deque is empty.
deque.peek();
peekFirst()
Retrieves, but does not remove, the first element of this deque, or
returns null if this deque is empty.
deque.peekFirst()
peekLast()
Retrieves, but does not remove, the last element of this deque, or
returns null if this deque is empty.
deque.peekLast();
poll()
Retrieves and removes the head of the queue represented by this
deque (in other words, the first element of this deque), or returns null if
this deque is empty.
deque.poll();
When to use:
•Use peek() if you want a safe check without exceptions.
•Use getFirst() if you expect the deque to be non-empty and want an error if it’s empty.
peek(): Apple
getFirst(): Apple
peek() on empty: null
getFirst() on empty threw exception:

23. Practice

1.
2.
3.
4.
5.
6.
7.
8.
9.
Unique Integers
Read a list of integers (e.g., 1 2 2 3 4 4 4 5) and print the unique values using a
HashSet.
Check Membership
Given a HashSet<String> of allowed user names, write a method isAllowed(String) that
returns true if the name exists, else false.
Set Size & Emptiness
Create a HashSet<Integer>, add a few numbers, print size(). Then clear() it and
print isEmpty().
Remove Elements
Start with a HashSet<String> containing 5 names. Remove one name using remove().
Print whether removal succeeded and the resulting set.
Bulk Add (addAll)
Create two HashSet<Integer>s. Add all elements of set2 into set1 using addAll().
Print the result.
Bulk Remove (removeAll)
Given setA and setB, remove from A all elements that also appear in B. Print the
modified A.
Retain Common (retainAll)
Given setX and setY, keep only the elements in X that are also in Y. Print X.
Contains All (containsAll)
Check if setA contains all elements of setB and print a friendly message.
Deduplicate Words
Given a sentence, split into words (by spaces), insert into a HashSet<String> to
deduplicate, then print the unique words.

24. Practice

11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
Basic Offer/Peek/Poll
Use ArrayDeque<Integer> as a queue: offer some numbers, peek, poll them all while
printing.
Stack Behavior
Use push() and pop() to simulate a stack of strings. Push 3 items, then pop all
while printing.
Add First/Last
Add integers to the front (addFirst) and back (addLast), then iterate and print to
show order.
Offer First/Last Return Value
Use offerFirst/offerLast and print their boolean return values. Then print the
deque.
Peek Variants
Demonstrate peek(), peekFirst(), and peekLast() on a deque with elements, then on an
empty one (note the null behavior).
Poll Variants
Demonstrate poll(), pollFirst(), pollLast() on a populated deque until empty. Print
polled sequence.
Remove First/Last Occurrence
With a deque containing duplicates (e.g., ["a","b","c","b","a"]), call
removeFirstOccurrence("b"), then removeLastOccurrence("a"). Print deque after each.
IsEmpty & Size
Add, remove, and after each operation print size() and isEmpty().
Clear Deque
Fill a deque, call clear(), then show that peek() returns null and isEmpty() is
true.
Palindrome Check (Deque)