Content#

• Stacks
• Abstract data types
• Queues
• Priority queues
• Stacks and queues in the Java collections framework

Stacks#

• A stack is an object that contains a list of elements, like an ArrayList.
• However the methods of a stack allow us to add elements only to the top of the list, and to remove only the element that is at the top of the list.

• 4 operations on stack

1
public class StringStack {
2
    private ArrayList<String> list = new ArrayList<String>();
3
    public void push(String s) {
4
        list.add(s);
5
    }
6
    public String pop() {
7
        assert list.size() != 0;
8
        return list.remove(list.size()-1);
9
    }
10
    public String peek() {
11
        assert list.size() != 0;
12
        return list.get(list.size()-1);
13
    }
14
    public boolean isEmpty() {
15
        return list.isEmpty();
16
    }
17
}

Abstraction#

• In computer science Abstraction is the hiding of irrelevant detail.
• The fact that our StringStack uses an ArrayList to store data is irrelevant. We do not need to know that the stack is implemented in this way, and we do not want anyone to write code that is dependent on that particular implementation.

Hiding is better than showing more detail for you to worry about

Stack exercise#

• If s is an initially empty stack
• state the values of the variables a and b after the following code fragment is run:

1
s.push("Red");
2
s.push("Orange");
3
s.push("Blue");
4
s.pop();
5
s.push("Yellow");
6
s.pop();
7
String a = s.pop();
8
s.push("Brown");
9
s.pop();
10
String b = s.pop();

Queues#

• A queue is an ADT which maintains a list of data
• The methods available allow us to add data only to the back of the queue, and to remove data only from the front of the queue.
• A queue is FIFO (First In First Out) structure

• 4 operations on queue

1
public class StringQueue {
2
    private ArrayList<String> list = new ArrayList<String>();
3
    public void add(String s) {
4
        list.add(s);
5
    }
6
    public String remove() {
7
        assert list.size() != 0;
8
        return list.remove(0);
9
    }
10
    public String peek() {
11
        assert list.size() != 0;
12
        return list.get(0);
13
    }
14
    public boolean isEmpty() {
15
        return list.isEmpty();
16
    }
17
}

1
q.add("Diamond");
2
q.add("Tobby");
3
q.remove();
4
q.add("Garnet");
5
q.add("Emeric");
6
q.remove();
7
String a = q.remove();
8
q.add("Sapphire");
9
String b = q.remove();

Priority queues#

• A priority queue implements the same methods as an ordinary queue, but it works in BIFO (Best In First Out) manner.
• Each element in the queue is allocated a priority, and the remove() method always removes the element with the highest priority.

• For example suppose that a priority queue contains Strings, and that when two Strings are compared the one that is lowest in alphabetical order has highest priority.
• The code

1
pq.add("Jam");
2
pq.add("Ham");
3
pq.add("Spam");
4
String best = pq.remove();

Results in best pointing to the String “Ham”.

1
public void add(String s) {
2
    int i = 0;
3
    int size = list.size();
4
    while (i < size && s.compareTo(list.get(i)) > 0) {
5
        i++;
6
    }
7
    list.add(i, s);
8
}

Double-ended queue (DEQUE)#

• A deque (pronounced “deck”) is like a queue, except that elements can be added or removed from either end.

Stacks and queues in the java collections framework#

• The Java collections framework contains an interface Queue, which extends the Collection interface.
• The Queue interface contains the methods that we have already mentioned when describing queues, plus a few others.
• For example in addition to the remove() method, there is an poll() method. The difference between the two is that, if the queue is empty, remove() throws an exception whereas poll() returns a null value.

• Similarly the Queue interface provides add() and offer() methods, the difference being that add() has a void return type and throws an exception if the capacity of the queue is exceeded, whereas offer returns a Boolean value – false if the capacity was exceeded, and true otherwise.
• The Queue interface is implemented by, among others, the LinkedList and ArrayDeque classes

• The Java collections framework does not contain a Stack interface. There is a Stack class, but its use is not advised. It is better to use the ArrayDeque class
• There is a class PriorityQueue that implements the Queue interface and where the remove(), poll(), and peek() methods return the highest-priority element.

1
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque‹E>, Cloneable, Serializable {
2
    transient int size;
3
    transient LinkedList.Node<E> first;
4
    transient LinkedList.Node<E> last;
5
    private static final long serialVersionUID = 876323262645176354L;
6
    public LinkedList() {
7
        this.size = 0;
8
    }
9
    public LinkedList(@NotNull @Flow(sourcelsContainer = true, targetsContainer = true) Collection<? extends E> c) {
10
    this();
11
    this.addAll(c);
12
}

Summary#

• A stack is a LIFO (Last-In, First-Out) structure.
• A queue is a FIFO (First-In, First-Out) structure.
• A priority queue is BIFO (Best-In, First-Out) structure.
• A deque behaves like a queue except that data can be added or removed from either end.
• Abstraction is the deliberate concealment of irrelevant detail.
• An Abstract Data Type is defined by the operations that it allows you to perform on its data. The implementation of these methods, and the means by which data are stored, are deliberately concealed.
• The Java collections framework contains classes and interfaces representing stacks, queues, priority queues, and deques.

Content#

• Basic graph definitions
• Implementation of graph data structures
• Traversals and applications

Graphs: Nodes and Edges#

• Network-like data structures can be represented using graphs.
• A graph consists of a set of nodes (also known as vertices) together with a set of edges (also known as arcs) connecting them
• Some graphs may have loops (a loop is an edge connecting a node to itself)

Graphs: Directed and Undirected#

• Graphs can be directed (e.g. a street map with one way streets)
• or undirected (e.g. street map where all streets can be traversed in any direction)

Graphs: Data Storage#

• As well as the nodes and edge structure, graphs typically have additional data stored.
• This data can be at nodes and/or edges,
• For example: in the Chengdu Subway graph:
  • nodes have names of stations
  • edges are labeled with the line(s) between those stations

Implementing Graphs on a Computer#

• There are two common ways of representing graph data:
  • adjacency matrices
  • adjacency lists

1
boolean[][] edgeMatrix = new boolean[n][n];

1
ArrayList<Integer>[]

1
ArrayList<Interger> adjacencyLists[]= new ArrayList[n];

1
ArrayList<Node> adjacencyLists = new ArrayList<Node>();

1
Class Teacher {
2
    …………
3
    public ArrayList<Teacher> adjacencyLists = new ArrayList<Teacher>();
4
}
5
…………
6
Teacher l,j,ja,jak;
7
l.adjacencyLists.add(j);

Traversals#

• A traversal is a way of systematically going through all the data in a structure, visiting each piece of data precisely once.
• Traversals can be used for various purposes, including searching.
• Two common types of graph traversal:
  • Depth-first traversal
  • Breadth-first traversal

3 traversal methods for binary tree

1
dft(g,n) {
2
    visit(n)
3
    mark n as visited
4
    for each node x adjacent to n {
5
        if x is unvisited then
6
            dft(g,x)
7
    }
8
}

Checklist#

• What you want to be capable of by the end of this week:
  • know basic graph terminology
  • know suitable storage structures for graph data
  • perform both depth-first and breadth-first traversals of graphs
  • describe uses for graphs and traversals