FACULTY OF INFORMATION TECHNOLOGY

Semester 1, 2025/2026
DS – NLU 2
 Some collections are constrained so clients can only use
optimized operations
◦ Stack: retrieves elements in reverse order as added
◦ Queue: retrieves elements in same order as added

push pop, peek

front back
top 3 remove, peek add
1 2 3
2
queue
bottom 1
stack

DS – NLU
4
 Stack: A collection based on the principle of adding elements and
retrieving them in the opposite order.
◦ Last-In, First-Out ("LIFO")
◦ Elements are stored in order of insertion.
 We do not think of them as having indexes.
◦ Client can only add/remove/examine
the last element added (the "top").
push pop, peek

 Basic stack operations:

◦ push: Add an element to the top.
◦ pop: Remove the top element. top 3
◦ peek: Examine the top element. 2
bottom 1
stack
DS – NLU
DS – NLU 6
DS – NLU 7
 Direct applications
◦ Page-visited history in a Web browser
◦ Undo sequence in a text editor
◦ Chain of method calls in the JVM

 Indirect applications
◦ Auxiliary data structure for algorithms
◦ Component of other data structures

DS – NLU 8
9
DS – NLU 10
DS – NLU 11
Which data structures can
be used to implement
Stack?

DS – NLU 12
13
 A simple way of implementing the Stack ADT uses an array

 We add elements from left to right

 A variable keeps track of the index of the top element

DS – NLU 14
 Elements are stored in an array with capacity N for some fixed
N.
 The bottom element of the stack is always stored in cell
data[0],
 The top element of the stack in cell data[t] for index t ( t<=
the current size of the stack).

DS – NLU 15
DS – NLU 16
DS – NLU 17
 Analyzing the Array-Based Stack Implementation

DS – NLU 18
19
 The top of the stack is the head of the linked list.

 Push: create a new node and add it at the top of the stack.

 Pop: delete the node at the top of the stack.

Bottom Top

Sydney Rome Seattle New York

DS – NLU 20
 Methods:

DS – NLU 22
DS – NLU 23
24
 The class supports
one default
constructor Stack()
which is used
to create an empty
stack.

DS – NLU 25
 [Link]<E>

[Link]<E>

+Stack() Creates an empty stack.

+isEmpty(): boolean Returns true if this stack is empty.
+peek(): E Returns the top element in this stack.
+pop(): E Returns and removes the top element in this stack.
+push(o: E) : E Adds a new element to the top of this stack.
+search(o: Object) : int Returns the position of the specified element in this stack.

DS – NLU 26
 E push(E element) :
◦ Pushes an element on the top of the stack.
 E pop():
◦ Removes and returns the top element of the stack.
◦ An ‘EmptyStackException’ exception is thrown if we call pop() when the
invoking stack is empty.
 E peek():
◦ Returns the element on the top of the stack, but does not remove it.
 boolean isEmpty():
◦ It returns true if nothing is on the top of the stack.
◦ Else, returns false.

DS – NLU 27
 int search(element): It determines whether an object exists in
the stack.

◦ If the element is found, it returns the position of the element from the
top of the stack.

◦ Else, it returns -1.

DS – NLU 28
# Output
Stack => [Jack, Queen, King, Ace]

DS – NLU 29
# Output
[Link]() => Ace
Current Stack => [Jack, Queen, King]

[Link]() => King

Current Stack => [Jack, Queen, King]

DS – NLU 30
 You should not loop over a stack in the usual way.
Stack<Integer> s = new Stack<Integer>();
...
for (int i = 0; i < [Link](); i++) {
do something with [Link](i);
}
 Instead, you pull elements out of the stack one at a time.
◦ common idiom: Pop each element until the stack is empty.
// process (and destroy) an entire stack
while (![Link]()) {
do something with [Link]();
}
DS – NLU
 Suppose we're asked to write a method max that accepts a Stack of
integers and returns the largest integer in the stack:

// Precondition: ![Link]()
public static int max(Stack<Integer> s) {
int maxValue = [Link]();
while (![Link]()) {
int next = [Link]();
maxValue = [Link](maxValue, next);
}
return maxValue;
}

◦ The algorithm is correct, but what is wrong with the code?

DS – NLU
 The code destroys the stack in figuring out its answer.
◦ To fix this, you must save and restore the stack's contents:
public static void max(Stack<Integer> s) {
Stack<Integer> backup = new Stack<Integer>();
int maxValue = [Link]();
[Link](maxValue);
while (![Link]()) {
int next = [Link]();
[Link](next);
maxValue = [Link](maxValue, next);
}
while (![Link]()) { // restore
[Link]([Link]());
}
return maxValue;
}
DS – NLU
 How to reverse an array using a stack?

DS – NLU 34
DS – NLU 35
 Matching Parentheses:
◦ Parentheses: “(” and “)”
◦ Braces: “{” and “}”
◦ Brackets: “[” and “]”
 Each opening symbol must match its corresponding closing
symbol.
 For example, a left bracket, “[” must match a corresponding
right bracket, “]”

DS – NLU 36
 Evaluating Expressions

DS – NLU 37
Phase 1: Scanning the expression
The program scans the expression from left to right to extract operands, operators, and
the parentheses.
1.1. If the extracted item is an operand, push it to operandStack.
1.2. If the extracted item is a + or - operator, process all the operators at the top of
operatorStack and push the extracted operator to operatorStack.
1.3. If the extracted item is a * or / operator, process the * or / operators at the top of
operatorStack and push the extracted operator to operatorStack.
1.4. If the extracted item is a ( symbol, push it to operatorStack.
1.5. If the extracted item is a ) symbol, repeatedly process the operators from the top of
operatorStack until seeing the ( symbol on the stack.

Phase 2: Clearing the stack

Repeatedly process the operators from the top of operatorStack until operatorStack is
empty.

DS – NLU 38
DS – NLU 39
 Matching Tags in a Markup Language (Illustrating (a) an HTML
document and (b) its rendering)

DS – NLU 40
 <body>: document body
 <h1>: section header
 <center>: center justify
 <p>: paragraph
 <ol>: numbered (ordered) list
 <li>: list item

DS – NLU 41
 "undo" mechanism in text editors;
◦ this operation is accomplished by keeping all text changes in a stack.

DS – NLU 42
 Deapth-First Traversal of the given tree:
 S→A→D→H→E→G→B→C→F S

5 2 4

A B C

9 4 6 2
6 1
D E G F

DS – NLU 43
44
 Queue: Retrieves elements in the order they were added.
◦ First-In, First-Out ("FIFO")
◦ Elements are stored in order of
insertion but don't have indexes.
◦ Client can only add to the end of the
queue, and can only examine/remove
the front of the queue. front back
remove, peek add
1 2 3
 Basic queue operations:
◦ add (enqueue): Add an element to the back. queue

◦ remove (dequeue): Remove the front element.

◦ peek: Examine the front element.
DS – NLU
 Direct applications
◦ Waiting lists, bureaucracy
◦ Access to shared resources (e.g., printer)
◦ Multiprogramming

 Indirect applications
◦ Auxiliary data structure for algorithms
◦ Component of other data structures

DS – NLU 46
DS – NLU 47
DS – NLU 48
49
DS – NLU 50
DS – NLU 51
Which data structures can
be used to implement
Queue?

DS – NLU 52
53
 Elements are stored in an array with capacity N for some fixed
N.

 The first element is at index 0, the second element at index 1,

and so on

DS – NLU 54
DS – NLU 55
DS – NLU 56
 Analyzing the Efficiency of an Array-Based Queue

DS – NLU 57
58
DS – NLU 59
 Each method of LinkedQueue adaptation also runs in O(1)
worst-case time.

DS – NLU 60
 Circularly linked list class that supports all behaviors of a
singly linked list, and an additional rotate( ) method that
efficiently moves the first element to the end of the list

DS – NLU 61
 A group of children sit in a circle passing an object, called
“potato”, around the circle.

 The potato begins with a starting child in the circle, and the
children continue passing the potato until a leader rings a
bell, at which point the child holding the potato must leave
the game after handing the potato to the next child in the
circle.

 After the selected child leaves, the other children close up the
circle.

DS – NLU 62
 This process then continues until there is only child
remaining, who is declared the winner.

 If the leader always uses the strategy of ringing the bell after
the potato has been passed k times, for some fixed k,
determining the winner for a given list of children is known as
the josephus problem

DS – NLU 63
 M=2, N=5
Initial state: Round 1 Round 2

0 0 0 0 X
4 1 4 1 4 1 4 1

3 2 3 2 X 3 2 X 3 2 X

Person removed so far: 2, 0,

DS – NLU
 M=2, N=5
Round 3 Round 2
X X X
0 0 X
0 0
4 1 X4 1 X
4 1 4 1 X
X
3 2 3 2 X 3 2 X 3 2
X X

Person removed so far: 2, 0, 4, 1 Winner is 3

DS – NLU
DS – NLU 66
67
DS – NLU 68
 If a queue is empty:
◦ remove( ) and element( ) methods throw a NoSuchElementException,
◦ poll( ) and peek( ) return null

DS – NLU 69
 Queue interface in Java collections has two implementation:

DS – NLU 70
 boolean add(E e):
◦ adds the specified element at the end of Queue.
◦ Returns true if the the element is added successfully;
◦ Or false if the element is not added that basically happens when the
Queue is at its max capacity and cannot take any more elements.
 E element():
◦ returns the head (the first element) of the Queue.
 boolean offer(object):
◦ same as add() method.

DS – NLU 71
 E remove():
◦ removes the head(first element) of the Queue and returns its value.
 E poll():
◦ almost same as remove() method. The only difference between poll()
and remove() is that poll() method returns null if the Queue is empty.
 E peek():
◦ almost same as element() method.
◦ The only difference between peek() and element() is that peek() method
returns null if the Queue is empty.

DS – NLU 72
DS – NLU 73
 As with stacks, must pull contents out of queue to view them.

// process (and destroy) an entire queue

while (![Link]()) {
do something with [Link]();
}

◦ another idiom: Examining each element exactly once.

int size = [Link]();

for (int i = 0; i < size; i++) {
do something with [Link]();
(including possibly re-adding it to the queue)
}
 Why do we need the size variable?

DS – NLU
 We often mix stacks and queues to achieve certain effects.
◦ Example: Reverse the order of the elements of a queue.
Queue<Integer> q = new LinkedList<Integer>();
[Link](1);
[Link](2);
[Link](3); // [1, 2, 3]
Stack<Integer> s = new Stack<Integer>();
while (![Link]()) { // Q -> S
[Link]([Link]());
}
while (![Link]()) { // S -> Q
[Link]([Link]());
}
[Link](q); // [3, 2, 1]

DS – NLU
 Write a method stutter that accepts a queue of integers as a
parameter and replaces every element of the queue with two
copies of that element.
◦ front [1, 2, 3] back
becomes
front [1, 1, 2, 2, 3, 3] back
 Write a method mirror that accepts a queue of strings as a
parameter and appends the queue's contents to itself in
reverse order.
◦ front [a, b, c] back
becomes
front [a, b, c, c, b, a] back

DS – NLU
 Breadth-First Traversal of the given tree:
 S→A→B→C→D→E→G→F→H S

5 2 4

A B C

9 4 6 2
6 1
D E G F

DS – NLU 77
78
 [Link] interface is a subtype of [Link]
interface:
◦ supports insertion and removal of elements at both ends
◦ a deque can be used as a stack or a queue

DS – NLU 79
 Summary of Deque methods

DS – NLU 80
 Comparison of Queue and Deque methods

DS – NLU 81
 Comparison of Stack and Deque methods

DS – NLU 82
 The important points:
◦ Unlike Queue, we can add or remove elements from
both sides.

◦ Null elements are not allowed in the ArrayDeque.

◦ ArrayDeque is not thread-safe, in the absence of

external synchronization.

◦ ArrayDeque has no capacity restrictions.

◦ ArrayDeque is faster than LinkedList and Stack.

DS – NLU 83
 Constructors:
◦ ArrayDeque()

 This constructor is used to create an empty array deque with an initial capacity
sufficient to hold 16 elements.

◦ ArrayDeque(Collection<? extends E> c)

 This constructor is used to create a deque containing the elements of the specified
collection.

◦ ArrayDeque(int numElements)

 This constructor is used to create an empty array deque with an initial capacity
sufficient to hold the specified number of elements.

DS – NLU 84
 ArrayQueue Usage:

DS – NLU 85
86
DS – NLU 87
 Recall that a FIFO queue removes elements in the order in which
they were added.

 A PriorityQueue removes items in sorted order from lowest to

highest value, independent of the order in which they were added

 Priority queues can be implemented by using arrays, linked list and

heap.

 A priority queue stores a collection of entries. Each entry is a pair

(key, value)

DS – NLU 88
DS – NLU 89
 Method insert(k,v): create an entry with the key k and value v in the
priority queue.
 Method min(): return (but does not remove) a priority queue entry
(k,v)
 Method removeMin(): removes and returns an entry (k,v) having
minimal key from the priority queue, returns null if the priority
queue is empty.
 Method size(): returns the number of entries in the priority queue.
 Method isEmpty(): returns a Boolean indicating whether the priority
queue is empty.a
DS – NLU 90
 A sequence of priority queue methods: The numbers are keys
(priorities), letters are values (data).

DS – NLU 91
 See Chapter 9: Data Structures and Algorithms in Java 6th
Edition

DS – NLU 92
DS – NLU 93
 Priority queue:
◦ retrieves elements in sorted order after they were inserted in arbitrary
order.

◦ does not sort all its elements.

 A priority queue can either hold elements of a class that

implements the Comparable interface or a Comparator object
supplying in the constructor (like TreeSet)

 A typical use for a priority queue is job scheduling

DS – NLU 94
DS – NLU 95
DS – NLU 96
 PriorityQueue(): Creates a PriorityQueue with the default initial capacity (11) that
orders its elements according to their natural ordering.
 PriorityQueue(Collection<E> c): Creates a PriorityQueue containing the
elements in the specified collection.
 PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified
initial capacity that orders its elements according to their natural ordering.
 PriorityQueue(int initialCapacity, Comparator<E> comparator): Creates a
PriorityQueue with the specified initial capacity that orders its elements
according to the specified comparator.
 PriorityQueue(PriorityQueue<E> c): Creates a PriorityQueue containing the
elements in the specified priority queue.
 PriorityQueue(SortedSet<E> c): Creates a PriorityQueue containing the elements
in the specified sorted set.

DS – NLU 97
 boolean add(E e): Inserts the specified element into this priority queue.

 void clear(): Removes all of the elements from this priority queue.

 Comparator<? super E> comparator(): Returns the comparator used to

order the elements in this queue, or null if this queue is sorted according
to the natural ordering of its elements.

 boolean contains(Object o): Returns true if this queue contains the

specified element.

 Iterator<E> iterator(): Returns an iterator over the elements in this

queue.

 Boolean offer(E e): Inserts the specified element into this priority queue.

DS – NLU 98
 E peek(): Retrieves, but does not remove, the head of this queue, or
returns null if this queue is empty.
 E poll(): Retrieves and removes the head of this queue, or returns
null if this queue is empty.
 boolean remove(Object o): Removes a single instance of the
specified element from this queue, if it is present.
 int size(): Returns the number of elements in this collection.
 Spliterator<E> spliterator(): Creates a late-binding and fail-fast
Spliterator over the elements in this queue.
 Object[] toArray(): Returns an array containing all of the elements
in this queue.
 <T> T[] toArray(T[] a): Returns an array containing all of the
elements in this queue; the runtime type of the returned array is
that of the specified array.

DS – NLU 99
DS – NLU 100
DS – NLU 101
DS – NLU 102
 An unbounded priority queue based on a priority heap.
 PriorityQueue doesn’t permit null.
 We can’t create PriorityQueue of Objects that are non-comparable
 The head of the queue is the least element with respect to the specified
ordering.
◦ If multiple elements are tied for least value, the head is one of those elements —
ties are broken arbitrarily.
 The queue retrieval operations poll, remove, peek, and element access
the element at the head of the queue.
 It inherits methods from AbstractQueue, AbstractCollection, Collection
and Object class.

DS – NLU 103
 Heaps: a specific tree based data structure in which all the
nodes of tree are in a specific order.

 Let X be a parent node of Y, then the value of X follows some

specific order with respect to value of Y and the same order
will be followed across the tree.

 The maximum number of children of a node in the heap

depends on the type of heap

DS – NLU 104
 Heap has at most 2 children of a node:

 Each node has greater value than any of its children.

 Suppose there are N Jobs in a queue to be done, and each job has
its own priority.

 The job with maximum priority will get completed first than
others.
DS – NLU 105
 Collection Ordering Benefits Weaknesses
array by index fast; simple little functionality;
cannot resize
ArrayList by insertion, by random access; fast slow to modify in
index to modify at end middle/front
LinkedList by insertion, by fast to modify at poor random access
index both ends
TreeSet sorted order sorted; O(log N) must be comparable
HashSet unpredictable very fast; O(1) unordered
LinkedHashSet order of insertion very fast; O(1) uses extra memory
TreeMap sorted order sorted; O(log N) must be comparable
HashMap unpredictable very fast; O(1) unordered
LinkedHashMap order of insertion very fast; O(1) uses extra memory
PriorityQueue natural/comparable fast ordered access must be comparable

 It is important to be able to choose a collection properly based on the

capabilities needed and constraints of the problem to solve.
DS – NLU
FACULTY OF INFORMATION TECHNOLOGY