Programação II
Prof. Mateus Raeder
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Criando um objeto
• Objeto é uma instância de uma classe;
• Usamos o operador new para criar um objeto.
Variável que conterá uma
referência a um objeto
ContaCorrente minhaConta;
minhaConta = new ContaCorrente ( );
Criação do objeto
ContaCorrente minhaConta = new ContaCorrente ( );
Programação II – Prof. Mateus Raeder
Garbage Collection
String str = “Primeiro espaço”;
System.out.println (“Usando memória original: “+str);
str = “Outro espaço”;
System.out.println (“Usando outro espaço de memória: “+str);
Primeiro espaço
str
Área de memória
liberada pelo Garbage
Collection
10 100
Outro espaço
System.gc();
10
100
Não obriga a limpar, mas “pede”
para que o Garbage Collection limpe se possível
Programação II – Prof. Mateus Raeder
Exercícios
• Crie uma classe Endereco, que possui uma rua, um
número e uma cidade. No construtor, receba todos
os atributos por parâmetro. Crie métodos para
retornar estes parâmetros (getters).
• Crie uma classe Imovel, que possui um valor e um
Endereco. No construtor, passe por parâmetro o
valor, e diga que o imóvel é na Largo Patrono
Fernando Kroeff, número 2, em Porto Alegre. Crie os
métodos getEndereco e getValor.
Programação II – Prof. Mateus Raeder
Exercícios
• Crie uma classe Pessoa, que possui um nome
(passado por parâmetro no construtor) e um imóvel
de R$650.000,00. Crie um método getNome e um
método getImóvel.
• Crie uma classe Teste. No método main, crie uma
pessoa chamada Anacreonte. Em seguida,
imprima o endereço (por extenso) e o valor do
imóvel que esta pessoa possui.
Programação II – Prof. Mateus Raeder
Respostas
public class Endereco{
private String rua;
private int numero;
private String cidade;
public Endereco(String rua, int numero, String cidade){
this.rua = rua;
this.numero = numero;
this.cidade = cidade;
}
public String getRua(){
return rua;
}
public int getNumero(){
return numero;
}
}
public String getCidade(){
return cidade;
}
Programação II – Prof. Mateus Raeder
Respostas
public class Imovel{
private double valor;
private Endereco endereco;
public Imovel(double valor){
this.valor = valor;
endereco = new Endereco("Largo Patrono Fernando Kroeff", 2,
"Porto Alegre");
}
public double getValor(){
return valor;
}
}
public Endereco getEndereco(){
return endereco;
}
Programação II – Prof. Mateus Raeder
Respostas
public class Pessoa{
private String nome;
private Imovel imovel;
public Pessoa(String nome){
this.nome = nome;
imovel = new Imovel(650.000);
}
public String getNome(){
return nome;
}
}
public Imovel getImovel(){
return imovel;
}
Programação II – Prof. Mateus Raeder
Respostas
public class Teste{
public static void main(String args[]){
Pessoa p = new Pessoa("Anacreonte");
System.out.println("Dados de "+p.getNome()+": \n");
System.out.println("Valor do imóvel: "+p.getImovel().getValor()+"\n");
}
}
System.out.println("ENDEREÇO:");
System.out.println("Rua: "+p.getImovel().getEndereco().getRua());
System.out.println("Número: "+p.getImovel().getEndereco().getNumero());
System.out.println("Cidade: "+p.getImovel().getEndereco().getCidade());
Programação II – Prof. Mateus Raeder
Listas: Tipo de Armazenamento
• O tipo de armazenamento de uma lista linear pode
ser classificado de acordo com a posição relativa
(sempre contígua ou não) na memória de dois nós
consecutivos na lista.
• Lista linear com alocação seqüencial de memória
– Nós em posições contíguas de memória
– Geralmente representado por arrays
– Útil para implementar filas e pilhas (variáveis para controlar
fim e início)
Programação II – Prof. Mateus Raeder
Listas: Tipo de Armazenamento
• Lista linear com alocação encadeada
– Posições de memória são alocadas a medida que são
necessárias
– Nós encontram-se aleatoriamente dispostos na memória e são
interligados por ponteiros, que indicam a próxima posição da
tabela
• Nós precisam de um campo a mais: campo que indica
o endereço do próximo nó.
Programação II – Prof. Mateus Raeder
Listas Simplesmente Encadeadas
• Uma lista simplesmente encadeada é uma
seqüência de objetos alocados dinamicamente,
onde cada objeto faz referência ao seu sucessor
na lista
• Lista encadeada básica:
– possui variável firstNode que referencia para o primeiro
elemento da lista
– cada Objeto refere a seu sucessor
– ultimo elemento contém a referência null (para indicar
que não referencia nenhum outro).
Ineficiente: se queremos inserir um elemento no final da lista, temos
que localizar o último elemento: para tanto é necessário
percorrer todos os elementos da lista.
Programação II – Prof. Mateus Raeder
Lista Encadeada Básica
data
firstNode
Apontador para o
primeiro nó da lista
next
Node
...
null
final de lista
Programação II – Prof. Mateus Raeder
Lista encadeada com referência
ao último elemento da lista
• Como tornar mais eficiente:
– utilizar uma segunda variável, chamada lastNode, que
referencia o último elemento da lista.
– eficiência obtida a custa do espaço adicional
firstNode
Apontador para o
primeiro nó da lista
lastNode
Apontador para o
último nó da lista
...
null
final de lista
Programação II – Prof. Mateus Raeder
Classe Node
public class Node {
private String data;
private Node nextNode;
}
data
public Node( String element ) {
this( element, null );
}
public Node( String element, Node node ) {
data = element;
nextNode = node;
}
public String getData() {
return data;
}
public void setData(String element){
data = element;
}
public Node getNext() {
return nextNode;
}
public void setNext(Node node) {
nextNode = node;
}
nextNode
Node
Programação II – Prof. Mateus Raeder
Operações sobre lista
– public boolean isEmpty()
• verifica se a lista está vazia
– public void insertAtFront( String element )
• insere o elemento na frente da lista
– public void insertAtBack( String element )
• insere o elemento no final da lista
– public String removeFromFront()
• remove e retorna o primeiro elemento da lista
Programação II – Prof. Mateus Raeder
Operações sobre lista
– public String removeFromBack()
• remove e retorna o último elemento da lista
– public String getFirst()
• retorna o primeiro elemento da lista, sem removê-lo
– public String getLast()
• remove e retorna o último elemento da lista, sem removê-lo
– public void print()
• exibe o conteúdo da lista
Programação II – Prof. Mateus Raeder
Class List (1/5)
public class List {
private Node firstNode;
private Node lastNode;
private String name;
public List() {
this("list");
}
public List(String listName) {
name = listName;
firstNode = lastNode = null;
}
public boolean isEmpty() {
return firstNode == null;
}
Programação II – Prof. Mateus Raeder
Class List (2/5)
public String getFirst() throws UnderflowException {
if (isEmpty()) throw new UnderflowException();
return firstNode.getData();
}
public String getLast() throws UnderflowException {
if (isEmpty()) throw new UnderflowException();
return lastNode.getData();
}
Programação II – Prof. Mateus Raeder
Class List (3/5)
public void insertAtFront (String insertItem) {
if (isEmpty()) {
firstNode = lastNode = new Node(insertItem);
}
else {
firstNode = new Node(insertItem, firstNode);
}
}
public void insertAtBack (String insertItem) {
if (isEmpty()) {
firstNode = lastNode = new Node(insertItem);
}
else {
lastNode.setNext(new Node(insertItem));
lastNode = lastNode.getNext();
}
}
Programação II – Prof. Mateus Raeder
Class List (4/5)
public String removeFromFront() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
String removedItem = firstNode.getData();
if (firstNode == lastNode) {
firstNode = lastNode = null;
}
else {
firstNode = firstNode.getNext();
}
return removedItem;
}
Programação II – Prof. Mateus Raeder
Class List (4/5)
public String removeFromBack() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
String removedItem = lastNode.getData();
if (firstNode == lastNode) {
firstNode = lastNode = null;
}
else {
Node current = firstNode;
while (current.getNext() != lastNode) {
current = current.getNext();
}
lastNode = current;
current.setNext(null);
}
return removedItem;
}
Programação II – Prof. Mateus Raeder
Class List (5/5)
public void print() {
if (isEmpty()) {
System.out.println("Empty " + name);
}
else {
System.out.print("The " + name + " is: ");
Node current = firstNode;
while (current != null) {
System.out.print(current.getData().toString() + " ");
current = current.getNext();
}
System.out.println("\n");
}
}
Programação II – Prof. Mateus Raeder
Testando a lista
public class ListTest {
public static void main(String args[]) {
List list = new List();
list.insertAtFront("a");
list.insertAtFront("b");
list.insertAtBack("c");
list.insertAtBack("d");
list.print();
String removedEl;
try {
removedEl = list.removeFromFront();
System.out.println(removedEl.toString() + " removed");
removedEl = list.removeFromFront();
System.out.println(removedEl.toString() + " removed");
removedEl = list.removeFromBack();
System.out.println(removedEl.toString() + " removed");
}
}
removedEl = list.removeFromBack();
System.out.println(removedEl.toString() + " removed");
} catch (UnderflowException e) {
System.out.println(e.toString());
}
Programação II – Prof. Mateus Raeder
Pilha
(Stack)
Programação II – Prof. Mateus Raeder
Pilhas (Stack)
• Operações sobre Pilhas:
– public boolean isEmpty()
• verifica se a pilha está vazia
– public void push( String element )
• insere o nó no topo da pilha
– public String pop()
• retorna e remove o nó do topo da pilha
– public String getTop ()
• retorna o nó do topo da pilha, sem removê-lo
– public void print()
• exibe todos os nós da pilha
Programação II – Prof. Mateus Raeder
Pilha
public class Stack {
private Node top;
public Stack() { }
public boolean isEmpty() {
return (top == null);
}
public String getTop() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
else {
return top.getData();
}
}
Programação II – Prof. Mateus Raeder
Pilha
public void push (String insertItem) {
Node n = new Node(insertItem);
n.setNext(top);
top = n;
}
public String pop() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
Node ret = top;
top = top.getNext();
return ret.getData();
}
Programação II – Prof. Mateus Raeder
Pilha
public void print() {
if (isEmpty()) {
System.out.println("Stack Empty ");
}
else {
Node current = top;
while (current != null) {
System.out.println (current.getData().toString());
current = current.getNext();
}
System.out.println("\n");
}
}
}
Programação II – Prof. Mateus Raeder
Testando a Pilha
public class StackTest {
public static void main(String args[]) {
Stack stack = new Stack();
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
stack.print();
try {
String removedEl = null;
}
}
while (!stack.isEmpty()) {
removedEl = stack.pop();
System.out.println(removedEl.toString() + " popped");
}
} catch (UnderflowException e) {
System.out.println(e.toString());
}
Programação II – Prof. Mateus Raeder
Filas
(Queue)
Programação II – Prof. Mateus Raeder
Operações sobre Filas (Queue)
– public boolean isEmpty()
• verifica se a fila está vazia
– public void enqueue( String element )
• insere o elemento no final da fila
– public String dequeue()
• remove e retorna o primeiro elemento da fila
– public String getFirst()
• retorna o primeiro elemento da fila, sem removê-lo
– public void print()
• exibe o conteúdo da fila
Programação II – Prof. Mateus Raeder
Fila
public class Queue {
private Node firstNode;
private Node lastNode;
public boolean isEmpty() {
return firstNode == null;
}
public String getFirst() throws UnderflowException {
if (isEmpty()) throw new UnderflowException();
return firstNode.getData();
}
Programação II – Prof. Mateus Raeder
Fila
public void print() {
if (isEmpty()) {
System.out.println("Empty Queue");
}
else {
Node current = firstNode;
while (current != null) {
System.out.print(current.getData().toString() + ", ");
current = current.getNext();
}
System.out.println("\n");
}
}
Programação II – Prof. Mateus Raeder
Fila
public void enqueue (String insertItem) {
if (isEmpty()) {
firstNode = lastNode = new Node(insertItem);
}
else {
lastNode.setNext(new Node(insertItem));
lastNode = lastNode.getNext();
}
}
Programação II – Prof. Mateus Raeder
Fila
}
public String dequeue() throws UnderflowException {
if (isEmpty()) {
throw new UnderflowException();
}
String removedItem = firstNode.getData();
if (firstNode == lastNode)
firstNode = lastNode = null;
else
firstNode = firstNode.getNext();
return removedItem;
}
Programação II – Prof. Mateus Raeder
Testa Fila
public class QueueTest {
public static void main( String args[] ) {
Queue queue = new Queue();
}
}
queue.enqueue( "1" );
queue.enqueue( "2" );
queue.enqueue( "3" );
queue.enqueue( "4" );
queue.print();
try {
Object removedEl = null;
while (!queue.isEmpty()) {
removedEl = queue.dequeue();
System.out.println( removedEl.toString() + " dequeued" );
}
}
catch ( UnderflowException e ) {
e.printStackTrace();
}
Programação II – Prof. Mateus Raeder