FACULTY OF INFORMATION TECHNOLOGY

Semester 1, 2024/2025
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
DS – NLU 79
 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 80
DS – NLU 81
 A sequence of priority queue methods: The
numbers are keys (priorities), letters are
values (data).

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

DS – NLU 83
DS – NLU 84
 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 85
DS – NLU 86
DS – NLU 87
 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 88
DS – NLU 89
DS – NLU 90
DS – NLU 91
DS – NLU 92
 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 93
 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 94
 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 95
 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