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
Pilha
(Stack)
Programação II – Prof. Mateus Raeder
Pilhas
• Os elementos são inseridos e removidos sempre na
extremidade final, chamada de topo da pilha
• Contém um ponteiro (variável) que marca o topo
da pilha
• Implementa a norma LIFO (Last-In, First-Out)
– Último a entrar, primeiro a sair
• Pilha vazia: topo = -1
Programação II – Prof. Mateus Raeder
Pilhas
• Suponhamos uma pilha de números
inteiros P que, em certo momento,
possui os seguintes 7 elementos:
1 6 9 -3 0 3 5
• Declarando um array de inteiros de
nome P com MAX=10 elementos
(P[0..MAX-1]), teremos a seguinte
pilha:
5
3
0
-3
9
6
1
Programação II – Prof. Mateus Raeder
Operações sobre pilhas
- inserir número 2
- inserir número 8
- inserir número 4
- remover elemento
14
8
2
top
top
top
- inserir número 1
- remover elemento
- remover elemento
Programação II – Prof. Mateus Raeder
Exercício: Pilhas
• Dada a pilha ao lado, realize as
operações abaixo
(cumulativamente) e desenhe a
pilha resultante em cada passo:
–
–
–
–
–
–
Inserir 7
Retirar o primeiro elemento
Inserir -4
Inserir 6
Retirar o primeiro elemento
Retirar o primeiro elemento
3
Programação II – Prof. Mateus Raeder
Operações sobre pilhas
• public boolean isEmpty( )
– verifica se a pilha está vazia
• public boolean isFull( )
– verifica se a pilha está cheia
• public boolean push( int element )
– insere o nó no topo da pilha
Programação II – Prof. Mateus Raeder
Operações sobre pilhas
• public int pop( )
– retorna e remove o nó do topo da pilha
• public int 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
Pilhas
• Supondo a existência da classe Stack, desenhe a
pilha criada através do código abaixo (a saída do
programa):
public static void main(String args[]){
Stack p = new Stack(5);
p.push(4);
p.push(7);
p.push(14);
p.pop();
p.push(3);
p.pop();
p.pop();
p.print();
}
Programação II – Prof. Mateus Raeder
Pilha
public class Stack {
private int s[];
private int top = -1;
public Stack (int size){
s = new int[size];
}
... //demais métodos
}
Programação II – Prof. Mateus Raeder
Pilha
• Verificar se está vazia ou se está cheia
– Vazia:
/* Retorna:
- true se a lista está vazia
- false caso contrário */
public boolean isEmpty(){
if(top == -1)
return true;
return false;
}
Programação II – Prof. Mateus Raeder
Pilha
• Verificar se está vazia ou se está cheia
– Cheia:
/* Retorna:
- true se a lista está vazia
- false caso contrário */
public boolean isFull(){
if(top == s.length - 1)
return true;
return false;
}
Programação II – Prof. Mateus Raeder
Pilha
• Inserir e remover elementos
– Inserir (push)
public boolean push(int element){
if(isFull())
return false;
top++;
s[top] = element;
return true;
}
Programação II – Prof. Mateus Raeder
Pilha
• Inserir e remover elementos
– Remover (pop)
public int pop(){
if(isEmpty()){
System.out.println(“ERRO”);
return 0;
}
int element = s[top];
top--;
return element;
}
Programação II – Prof. Mateus Raeder
Pilha
• Retornar o elemento do topo, sem remover
public int getTop(){
if(isEmpty()){
System.out.println(“ERRO”);
return 0;
}
return s[top];
}
Programação II – Prof. Mateus Raeder
Pilha
• Imprimir os elementos da pilha
public void print(){
for(int i=top; i>=0; i--)
System.out.println(s[i]);
}
Programação II – Prof. Mateus Raeder
Pilha
public static void main(String args[]) {
Stack s = new Stack(6);
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
s.push(6);
int removed = s.pop();
removed = s.pop();
s.print();
}
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];
}
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 boolean enqueue (int element){
if(isFull())
return false;
if(last == queue.length-1 || last == -1){
last = 0;
queue[last] = element;
if(first == -1)
first = 0;
}
else{
last++;
queue[last] = element;
return true;
}
}
Programação II – Prof. Mateus Raeder
Fila circular
public int dequeue() {
if (isEmpty()){
System.out.println(“ERRO”);
return 0;
}
int element = queue[first];
if (first == last)
first = last = -1;
else if (first == queue.length - 1)
first = 0;
else
first++;
return element;
}
Programação II – Prof. Mateus Raeder
Fila circular
public int getFirst(){
if (isEmpty()){
System.out.println(“ERRO”);
return 0;
}
return queue[first];
}
Programação II – Prof. Mateus Raeder
Fila circular
public static void main(String args[]) {
CircularQueue f = new CircularQueue(5);
f.enqueue(1);
f.enqueue(2);
f.enqueue(3);
f.enqueue(4);
f.dequeue();
f.dequeue();
f.enqueue(5);
f.enqueue(6);
f.enqueue(7);
f.enqueue(8);
f.print();
}
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
Deques
public class Deque extends Queue{
public Deque (int size){
super(size);
}
public int getLast(){
if(isEmpty()){
System.out.println(“ERRO”);
return 0;
}
return q[last];
}
...//demais métodos
Programação II – Prof. Mateus Raeder
Deques
public boolean enqueueFront (int el){
if (isFull()) {
return false;
}
System.arraycopy(q, first, q, first + 1, last - first + 1);
q[first] = el;
last++;
return true;
}
Programação II – Prof. Mateus Raeder
Deques
public boolean enqueueBack (int el) {
return enqueue(el);
}
public int dequeueFront() {
return dequeue();
}
public int dequeueBack() {
if (isEmpty()){
System.out.println(“ERRO”);
return 0;
}
int element = q[last];
last--;
return element;
}
Programação II – Prof. Mateus Raeder
Deques
public static void main(String args[]) {
Deque d = new Deque(5);
d.enqueueBack(1);
d.enqueueFront(2);
d.enqueueBack(3);
d.print();
System.out.println(
System.out.println(
System.out.println(
System.out.println(
d.dequeueFront() );
d.dequeueBack() );
d.dequeueFront() );
d.dequeueBack() );
}
Programação II – Prof. Mateus Raeder