Estou lendo um livro de algoritmos e estrutura de dados em java do “Robert Lafore”, e me surgiu uma duvida em dos métodos veja, o fonte completo:
[code]package fila;
public class Queue2 {
private int maxSize;
private long[] queArray;
private int front;
private int rear;
// ---------------------------------------------------------------
public Queue2(int s) {
maxSize = s + 1; // isso é esquisito
queArray = new long[maxSize];
front = 0;
rear = -1;
}
// ---------------------------------------------------------------
public void insert(long j) {
if (rear == maxSize - 1) { // fila com indice no final do array
rear = -1; // efeito circular.
}
queArray[++rear] = j;
}
// ---------------------------------------------------------------
public long remove(){
long temp = queArray[front++];
if(front == maxSize){
front = 0;
}
return temp;
}
// ---------------------------------------------------------------
public long peek(){
return queArray[front];
}
// ---------------------------------------------------------------
public boolean isEmpty(){
return (rear + 1 == front || front+maxSize-1==rear);
}
public boolean isFull(){
return (rear+2==front)|| (front+maxSize-2==rear);
}
public int size(){
if(rear >= front){
return rear - front+1;
}else{
return (maxSize-front)+(rear+1);
}
}
public static void main(String[] args) {
Queue2 queue = new Queue2(1);
//
// queue.insert(11l);
// queue.insert(12l);
//
// queue.remove();
// queue.remove();
//
// queue.insert(45l);
// queue.insert(46l);
//
// queue.remove();
System.out.println(queue.size());
System.out.println(queue.isFull());
System.out.println(queue.isEmpty());
System.out.println("xxxx");
}
}
[/code]
Bom pessoal, o livro propõe justamente a implementação sem contagem com a variavel numeroItens, ou seja é realmente para implementar desta forma, mais não vejo, como irá entrar
na segunda parte, " front+maxSize-1==rear", eu testei com varias inicializações, e não vejo a necessidade desta segunta parte depois do conectivo "||"
public boolean isEmpty(){
return (rear + 1 == front || front+maxSize-1==rear);
}
Obrigado.
caUda (tail) é o final da fila, e caLda (syrup) é aquilo que vem no pudim, ou aonde você vai viajar ( Poços de CaLdas ).
Portanto, acho que você queria dizer caUda.
Note que a implementação usada usa 2 cursores, um com front apontando para o primeiro elemento da fila, e o outro (rear) apontando para o último elemento da fila. Parece mais intuitivo, não?
Isso na verdade torna a manipulação mais desajeitada que deveria ser (por exemplo, por que é que maxSize = s + 1? Isso é uma das coisas esquisitas), e é por isso que ele tem de usar essa condição adicional que você achou estranha; normalmente o rear deveria apontar para um elemento depois do último da fila (esquisito, não? Mas isso na verdade simplifica as condições).
Não estou com muito tempo para modificar o exemplo do Lafore para mostrar o jeito que normalmente se faz (com o “rear” apontando para um elemento depois). Mas isso tornaria as manipulações mais fáceis.
Bom, na verdade, eu ja implementei o exemplo que ele usa com a variável nItens, que não necessita então desta complicação nos metodos isEmpty, size, e isFull, o que eu queria na verdade, era um caso, em que os indices estivessem de uma forma, que entrasse na segunda condição, desta forma eu debugaria o código, e entenderia, mas eu não estou conseguindo “ver” uma situação em que vai entrar no segundo membro após o ou ou seja, que vai ser “false” para o primeiro membro, e “true” para o segundo!
Poderia por favor me dar um exemplo em que “caUda” e “frente” estariam apontando para determinados indices e a situação abaixo desse true?
abaixo em detales minha dúvida:
Em que índice(um exemplo) em que isso de false
rear + 1 == front// primera parte da expressão (rear + 1 == front || front+maxSize-1==rear);
E isso de true
front+maxSize-1==rear //não consigo simular uma sitação em que isso de True para uma fila vazia!
Já que em um “ou” na expressão quer dizer que em uma situação vazia vai dar false para a primeira condição mas vai satisfazer a segunda…
Espero ter conseguido expressar minha dúvida…
Obrigado
entanglement, eu tinha errado o comentário na ultima pergunta, arrumei, eu queria mesmo uma situação onde entrase no segundo ou quando
chamasse lista vazia! não consigo ver uma situação que a lista esteja vazia e de true a expressão abaixo:
front+maxSize-1==rear
Você já ouviu falar de aritmética modular? Ela é usada nesse caso, na verdade.
O autor provavelmente sabe que a condição correta é:
front - rear == 1 (modulo maxSize).
Mas obviamente implementar isso diretamente no código como:
( front - rear ) % maxSize == 1
é lento porque a operação de cálculo de resto costuma ser lenta.
Então ele pensou um pouco e começou a supor que (front - rear) / maxSize só pode ser 0, +1 ou -1.
Ele então decompôs a condição (front - rear ) % maxSize em :
front - rear == 1
front - rear == 1 + maxSize
front - rear == 1 - maxSize
Acho que ele deve ter pensado mais um pouco e descoberto que você só teria front - rear == 1 ou front - rear == 1 - maxSize (estou sem tempo de testar se é isso mesmo), e é por isso que ele pôs essas 2 condições apenas em vez de ter posto 3.
Bom, vou estudar a tal da aritmetica modular ae… Obrigado, mas eu continuo sem exemplo para pelo menos um caso, em que para valores de maxSize, from e rear
a expressão (front +maxSize - 1 == rear), daria verdadeiro!!!
se pudesse me dar um exemplo que desse == nesses dois membros eu agraderia muito.
obrigado.
entanglement, eu estudei a teoria da matemática modular, congruência, classes de congruência…, porém não consegui entender essa parte da explicação
Ou então como eu entendo essa decomposição, poderia ou me explicar como decompôs isso, ou qual a teoria preciso estudar para entender essa parte, ja debuguei o código e simulei situações mas não consegui ainda entender!
Obrigado