Programação II
Prof. Mateus Raeder
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Listas especiais
• O armazenamento sequencial (estático) é útil
quando as estruturas sofrem poucas remoções ou
inserções, ou quando estas não acarretam grandes
movimentações de nós
– Não é exatamente o caso de listas que permitem inserção
em qualquer posição
– O armazenamento sequencial é mais utilizado para
implementas tipos especiais de listas:
• Filas (Queue em inglês)
• Pilhas (Stack em inglês)
• Deques (Deque em inglês)
Programação II – Prof. Mateus Raeder
Fila
(Queue)
Programação II – Prof. Mateus Raeder
Filas
• Elementos são inseridos no final da fila e retirados
do início da fila
• Geralmente a implementação contém 2 ponteiros
(variáveis):
– first: para o início da fila
– last: para o fim da fila
• FIFO (First-In, First-Out)
– Primeiro a entrar, primeiro a sair
• Fila vazia: quando last for igual a first-1
Programação II – Prof. Mateus Raeder
Filas
• Suponhamos uma fila de números inteiros F que,
em certo momento, possui os seguintes 7
elementos:
1 6 9 -3 0 3 5
• Declarando um array de inteiros de nome F com
MAX=10 elementos (F[0..MAX-1]), teremos a
seguinte fila:
1
6
9
-3
0
3
5
Programação II – Prof. Mateus Raeder
Exercício: Filas
2
8
4
1
• Dada a fila acima, realize as operações abaixo
(cumulativamente) e desenhe a pilha resultante
em cada passo:
–
–
–
–
–
Inserir 10
Retirar o primeiro elemento
Retirar o primeiro elemento
Inserir 2
Retirar o primeiro elemento
Programação II – Prof. Mateus Raeder
Operações sobre filas
• public boolean isEmpty( )
– verifica se a fila está vazia
• public boolean isFull( )
– verifica se a fila está cheia
• public boolean enqueue( int element )
– insere o elemento no final da fila
Programação II – Prof. Mateus Raeder
Operações sobre filas
• public int dequeue( )
– remove e retorna o primeiro elemento da fila
• public int 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
Filas
• Supondo a existência da classe Queue, desenhe a
fila criada através do código abaixo (a saída do
programa):
public static void main(String args[]){
Queue f = new Queue(5);
f.enqueue(4);
f.enqueue(7);
f.enqueue(14);
f.dequeue();
f.enqueue(3);
f.dequeue();
f.dequeue();
f.print();
}
Programação II – Prof. Mateus Raeder
Filas
public class Queue {
protected int first = 0, last = -1;
protected int q[];
public Queue(int size) {
q = new int[size];
}
... //demais métodos
}
Programação II – Prof. Mateus Raeder
Filas
• Verificar se está vazia ou se está cheia
– Vazia:
public boolean isEmpty() {
if (last == (first-1))
return true;
return false;
}
Programação II – Prof. Mateus Raeder
Filas
• Verificar se está vazia ou se está cheia
– Cheia:
public boolean isFull() {
if (last == (q.length-1))
return true;
return false;
}
Programação II – Prof. Mateus Raeder
Filas
• Inserção e remoção de elementos
– Inserção (enqueue):
public boolean enqueue (int element) {
if (isFull())
return false;
last++;
q[last] = element;
return true;
}
Programação II – Prof. Mateus Raeder
Filas
• Inserção e remoção de elementos
– Remoção (dequeue):
public int dequeue() {
if (isEmpty()){
System.out.println(“ERRO”);
return 0;
}
int element = q[first];
first++;
return element;
}
Programação II – Prof. Mateus Raeder
Filas
• Retornar o primeiro elemento sem remover
public int getFirst(){
if (isEmpty()) {
System.out.println(“ERRO”);
return 0;
}
return q[first];
}
Programação II – Prof. Mateus Raeder
Filas
• Imprimir os elementos da fila
public void print() {
for (int i = first; i <= last; i++)
System.out.print(q[i] + ", ");
System.out.println();
}
Programação II – Prof. Mateus Raeder
Fila Circular
(Circular Queue)
Programação II – Prof. Mateus Raeder
Fila circular
• Observamos que uma fila pode ser considerada
como cheia mesmo não contendo nenhum
elemento
• Isto acontece pela maneira com a qual lidamos
com os índices de início e de final da fila
• Uma solução é trabalhar com filas circulares
Programação II – Prof. Mateus Raeder
Fila circular
public class CircularQueue {
private int[] queue;
private int first = -1, last = -1;
public CircularQueue (int length) {
queue = new int[length];
}
...//demais métodos
Programação II – Prof. Mateus Raeder
Fila circular
public boolean isFull() {
if ((first == 0 && last == queue.length – 1) || (first == last + 1))
return true;
else
return false;
}
...//demais métodos
Programação II – Prof. Mateus Raeder
Fila circular
...//demais métodos
public boolean isEmpty() {
if (first == -1)
return true;
else
return false;
}
...//demais métodos
Programação II – Prof. Mateus Raeder
Fila circular
public void enqueue (int element) throws OverflowException{
if(isFull())
throw new OverflowException();
//caso a fila esteja vazia ou o last esteja
//na última posição (neste caso a fila torna-se
//circular), inserimos na primeira posição
if(last == queue.length-1 || last == -1){
last = 0;
queue[last] = element;
//se a fila está vazia, vamos inserir o primeiro nó
if(first == -1)
first = 0;
}
else{
last++;
queue[last] = element;
}
}
Programação II – Prof. Mateus Raeder
Fila circular
public int dequeue() throws UnderflowException{
if (isEmpty())
throw new UnderflowException();
int element = queue[first];
//se a fila tem somente 1 elemento
if (first == last)
first = last = -1;
//se a fila está circular e deve-se
//remover a última posição do array
else if (first == queue.length - 1)
first = 0;
else
first++;
return element;
}
Programação II – Prof. Mateus Raeder
Fila circular
public int getFirst() throws UnderflowException{
if (isEmpty())
throw new UnderflowException();
return queue[first];
}
Programação II – Prof. Mateus Raeder
Fila circular
public static void main(String args[]) {
CircularQueue f = new CircularQueue(5);
try {
f.enqueue(1);
f.enqueue(2);
f.enqueue(3);
f.enqueue(4);
} catch (OverflowException e) {
System.out.println(e.toString());
}
try {
f.dequeue();
f.dequeue();
} catch (UnderflowException e) {
System.out.println(e.toString());
}
try {
f.enqueue(5);
f.enqueue(6);
f.enqueue(7);
f.enqueue(8);
} catch (OverflowException e) {
System.out.println(e.toString());
}
Programação II – Prof. Mateus Raeder
}
Exercícios: fila circular
• Implemente métodos para exibir o conteúdo de
uma fila circular de 2 maneiras:
– No método main, faça o código necessário para que,
enquanto a fila não estiver vazia, esvazie a fila, exibindo os
elementos retirados
– Crie um método print() na classe CircularQueue que exiba
o conteúdo da fila na ordem em que foram inseridos!
0,5 na prova do Grau A
Programação II – Prof. Mateus Raeder
Resposta (método print)
public void print (){
if(!isEmpty()){
if(first < last){
for(int i=first; i<=last; i++)
System.out.print(queue[i]+”, ”);
}
else{
for(int i=first; i<queue.length; i++)
System.out.print(queue[i]+”, ”);
for(int i=0; i<=last; i++)
System.out.print(queue[i]+”, ”);
}
System.out.println();
}
}
Programação II – Prof. Mateus Raeder
Deque
(Deque – Double Ended Queue)
Programação II – Prof. Mateus Raeder
Deque
• O deque é um tipo de fila em que as inserções e
remoções podem ser realizadas em ambas as
extremidades, que chamaremos de frente (front) e
final (back)
Programação II – Prof. Mateus Raeder
Operações sobre deques
• public boolean isEmpty()
– verifica se o deque está vazio
• public boolean isFull( )
– verifica se o deque está cheio
• public boolean enqueueFront( int element )
– insere o elemento na cabeça do deque
• public boolean enqueueBack( int element )
– insere o elemento no final do deque
Programação II – Prof. Mateus Raeder
Operações sobre deques
• public int dequeueFront()
– remove e retorna o primeiro elemento do deque
• public int dequeueBack()
– remove e retorna o último elemento do deque
• public int getFirst()
– retorna o primeiro elemento do deque, sem removê-lo
• public int getLast()
– retorna o último elemento do deque, sem removê-lo
• public void print()
– exibe o conteúdo do deque
Programação II – Prof. Mateus Raeder