Collections
(Stack, queue, tree, graph)
References as Links
• References can be used to create a variety of
linked structures, such as a linked list.
Inserting a Node
• A node can be inserted into a linked list with a few
reference changes:
Deleting a Node
• Likewise, a node can be removed from a linked list
by changing the next pointer of the preceding
node:
[Link]= [Link];
Other Dynamic Representations
• It may be convenient to implement a list as a
doubly linked list, with next and previous
references:
Other Dynamic Representations
• Another approach is to use a separate header
node, with a count and references to both the front
and rear of the list:
Outline
Collections and Data Structures
Dynamic Representations
Linear Structures (Queues & Stacks)
Non-Linear Structures (Trees & Graphs)
The Java Collections API
Classic Data Structures
• some common data structures that are helpful in
many situations
• Classic linear data structures include queues and
stacks
• Classic nonlinear data structures include trees and
graphs
Queues
• A queue is an abstract data type to add or remove
a list of objects. A queue has a capacity and a
discipline.
• For example a FIFO discipline: First-In, First-Out
• Analogy: a line of people at a bank teller’s window
Queues
• Classic operations for a queue
– enqueue - add an item to the rear of the queue
– dequeue (or serve) - remove an item from the front of the
queue
– empty - returns true if the queue is empty
• Queues often are helpful in simulations or any
situation in which items get “backed up” while
awaiting processing
Queuing systems
11
Queues
• A queue can be represented by a singly-linked list;
it is most efficient if the references point from the
front toward the end of the queue.
• A queue can be represented by an array, using the
remainder operator (%) to “wrap around” when the
end of the array is reached and space is available
at the front of the array
Stacks
• A stack ADT is also linear, like a list or a queue
• Items are added and removed from only one end of
a stack
• The discipline is LIFO: Last-In, First-Out
• Analogies: a stack of plates or a stack of books
Stacks
• Stacks often are drawn vertically:
[Link]
[Link]
Stacks
• Classic stack operations:
– push - add an item to the top of the stack
– pop - remove an item from the top of the stack
– peek (or top) - retrieves the top item without removing it
– empty - returns true if the stack is empty
• A stack can be represented by a singly-linked list, with the
first node in the list being the top element on the stack
• A stack can also be represented by an array, with the bottom
of the stack at index 0
Stacks
• The [Link] package contains a Stack class
• The Stack operations operate on Object
references
• Suppose a message has been encoded by
reversing the letters of each word
• See [Link]
//********************************************************************
// [Link] Author: Lewis/Loftus
//
// Demonstrates the use of the Stack class.
//********************************************************************
import [Link].*;
public class Decode
{
//-----------------------------------------------------------------
// Decodes a message by reversing each word in a string.
//-----------------------------------------------------------------
public static void main (String[] args)
{
Scanner scan = new Scanner ([Link]);
Stack word = new Stack();
String message;
int index = 0;
[Link] ("Enter the coded message:");
message = [Link]();
[Link] ("The decoded message is:");
continue
continue
while (index < [Link]())
{
// Push word onto stack
while (index < [Link]() && [Link](index) != ' ')
{
[Link] (new Character([Link](index)));
index++;
}
// Print word in reverse
while (![Link]())
[Link] (((Character)[Link]()).charValue());
[Link] (" ");
index++;
}
[Link]();
}
}
Sample Run
Enter the coded message:
continue artxE eseehc esaelp
The decoded message is:
while (index < [Link]()) Extra cheese please
{
// Push word onto stack
while (index < [Link]() && [Link](index) != ' ')
{
[Link] (new Character([Link](index)));
index++;
}
// Print word in reverse
while (![Link]())
[Link] (((Character)[Link]()).charValue());
[Link] (" ");
index++;
}
[Link]();
}
}
Outline
Collections and Data Structures
Dynamic Representations
Linear Structures (Queues & Stacks)
Non-Linear Structures (Trees & Graphs)
The Java Collections API
Trees
• A tree is a non-linear data structure that consists of
a root node and potentially many levels of
additional nodes that form a hierarchy
• Nodes that have no children are called leaf nodes
• Nodes except for the root and leaf nodes are called
internal nodes
• In a general tree, each node can have many child
nodes
A General Tree
internal node
[Link]
Binary Trees
• In a binary tree, each node can have no more than
two child nodes
• Trees are typically represented using references as
dynamic links
• For binary trees, this requires storing only two links
per node to the left and right child
Binary tree example
[Link]
TreeNode example code
private class TreeNode {
Object item;
TreeNode left;
TreeNode right;
TreeNode parent;
TreeNode(Object element, TreeNode lptr, TreeNode rptr, TreeNode p) {
item = element;
left = lptr;
right = rptr;
parent = p;
}
}
Graph
• A graph is another non-linear structure
• Unlike a tree, a graph does not have a root
• Any node in a graph can be connected to any other
node by an edge
• Analogy: the highway system connecting cities on a
map
Directed Graph
Undirected Graph
A graph for webpage links
Traveling salesman
• The travelling salesman starts from a city in the
graph. He tries to find the shortest path that takes
him to each of the cities, without ever visiting the
same city twice.
Digraphs
• In a directed graph or digraph, each edge has a
specific direction.
• Edges with direction sometimes are called arcs
• Analogy: airline flights between airports
Digraphs
Representing Graphs
• Both graphs and digraphs can be represented
using dynamic links or using arrays.
• As always, the representation should facilitate
the intended operations and make them
convenient to implement
Outline
Collections and Data Structures
Dynamic Representations
Linear Structures (Queues & Stacks)
Non-Linear Structures (Trees & Graphs)
The Java Collections API
Collection Classes
• The Java standard library contains several classes
that represent collections, often referred to as the
Java Collections API
• Their underlying implementation is implied in the
class names such as ArrayList and
LinkedList
• Several interfaces are used to define operations on
the collections, such as List, Set, SortedSet,
Map, and SortedMap
Generics
• Java supports generic types, which are useful when defining
collections
• A generic type is a generic class or interface that is
parameterized over types
• A class can be defined to operate on a generic data type
which is specified when the class is instantiated:
LinkedList<Book> myList =
new LinkedList<Book>();
• By specifying the type stored in a collection, only objects of
that type can be added to it
• Furthermore, when an object is removed, its type is already
established
Generic method example
public class Generic1
{
// generic method printArray
public static <E> void printArray( E[] inputArray ) {
for ( E element : inputArray ) {
[Link]( "%s ", element );
}
[Link]();
}
public static void main( String args[] ) {
Integer[] intArray = { 1, 2, 3, 4, 5 };
Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4 };
Character[] charArray = { 'H', 'E', 'L', 'L', 'O' };
[Link]("Array integerArray contains:");
printArray(intArray); // pass an Integer array
[Link]("\nArray doubleArray contains:");
printArray(doubleArray); // pass a Double array
[Link]("\nArray characterArray contains:");
printArray(charArray); // pass a Character array
}
}
Generic class example
public class Generic2 <ElementType> {
private ElementType item;
public void add(ElementType t) {
item = t;
}
public ElementType get() {
return item;
}
public static void main(String[] args) {
Generic2<Integer> integerBox = new Generic2<Integer>();
Generic2<String> stringBox = new Generic2<String>();
[Link](new Integer(10));
[Link](new String("Hello World"));
[Link]("Integer value: " + [Link]());
[Link]("String value : " + [Link]());
}
}
Summary
– the concept of a collection
– separating the interface from the implementation
– dynamic data structures
– linked lists
– queues and stacks
– trees and graphs
– generics