Comment faire un examen de file d'attente non destructif en Java

Question

J'aide mon fils avec un cours de programmation au collège, et j'imagine que j'ai besoin de la classe aussi. Il a terminé la mission, mais je ne crois pas qu'il le fait de la meilleure façon. Malheureusement, je ne peux pas le faire fonctionner de mon mieux. C'est nettement mieux, parce que ça ne marche pas encore.

Il lui est demandé d'implémenter certaines méthodes pour une classe qui étend une autre classe. On lui a dit qu'il doit utiliser la définition de classe suivante, et il ne peut rien changer dans ListQueue.

public class MyListQueue <AnyType extends Comparable<AnyType>> extends ListQueue<AnyType> 

Heres ce qui est dans ListQueue

// Queue interface 
// 
// ******************PUBLIC OPERATIONS********************* 
// void enqueue(x)  --> Insert x 
// AnyType getFront() --> Return least recently inserted item 
// AnyType dequeue()  --> Return and remove least recent item 
// boolean isEmpty()  --> Return true if empty; else false 
// void makeEmpty()  --> Remove all items 
// ******************ERRORS******************************** 
// getFront or dequeue on empty queue 

/** 
* Protocol for queues. 
*/ 

OK Je me sens très bien à parcourir une liste liée à Pascal ou C (montrant mon âge), mais ont jamais travaillé dans un langage OOP avant.

Lorsque je tente quelque chose comme ça

dummyQueue = this.front.next; 

Je reçois l'erreur suivante. * avant dispose d'un accès privé à ListQueue *

je suis d'accord avec, mais autre que dequeueing un élément, comment puis-je parcourir la liste, ou autrement obtenir l'accès à l'avant, en arrière, suivant et précédent qui sont tous en ListQueue.

Une formation serait appréciée.

Merci, David

Answer 1

Si je vous comprends bien, vous faites quelque chose comme ceci:

MyListQueue<String> dummyQueue = new MyListQueue<String>(); 
dummyQueue = this.front.next; 

Si oui, l'un des principaux principes de la POO est l'encapsulation, à savoir la dissimulation des données. L'idée est que les utilisateurs en dehors de la classe n'ont pas accès à l'état interne de la classe. Si vous souhaitez déterminer la taille de la file d'attente et que vous ne pouvez modifier ni l'interface ni l'implémentation, vous pouvez créer une file d'attente delegate qui remplace file d'attente et dequeue pour incrémenter et décrémenter un compteur. .

Answer 2

Si vous décidez d'avoir une file d'attente, vous ne voulez généralement que mettre en file d'attente et déquiler les éléments. Vous voulez savoir si la file d'attente est vide et que vous voulez regarder l'élément avant si vous en avez besoin ou le laisser à quelqu'un d'autre. Une file d'attente est une sorte de tampon qui évite le blocage, si l'expéditeur est plus rapide que le destinataire. Avec une file d'attente, le destinataire peut décider quand pour lire l'entrée suivante. Une file d'attente peut implémenter un tri (basé sur la priorité) et décider quel élément est l'élément avant.

Si vous avez besoin d'autres opérations telles que le déplacement de la liste, une file d'attente peut ne pas être le meilleur choix. Regardez les autres types de collection, peut-être sur ArrayList.

Certaines choses peuvent être faites cependant, vous pouvez sous-classer ListQueue et remplacer certaines méthodes.Donc, si vous voulez une méthode size() additonal, cela pourrait être une solution:

public class MyListQueue <T extends Comparable<T>> extends ListQueue<T> { 

    private size = 0; 

    public void enqueue(T element) { 
    size++; 
    super.enqueue(element); 
    } 

    public T dequeue() { 
    if (isEmpty()) { 
     return null; // that's a guess... 
    } 
    size--; 
    super.dequeue(element); 
    } 

    public int size() { 
    return size; 
    } 
} 

Je l'ai remplacé AnyType avec T qui est plus fréquente.

Answer 3

Vous avez demandé, "En dehors de la mise en file d'attente d'un élément, comment puis-je parcourir la liste, ou sinon avoir accès à l'avant, arrière, suivant et précédent qui sont tous dans ListQueue."

Dans le sens le plus pur, vous ne devriez pas pouvoir.

Une file d'attente idéalisée promet quelques choses:

• Pousser articles dans le dos
• Pop articles de l'avant
• (Peut-être) Vérifiez élément avant, sinon vide
• (éventuellement) A définition espace prédicat pour pop et inspectent, déterminer si la file d'attente est vide

Je suppose pour le moment que la file d'attente n'est pas destiné à être utilisé avec des lecteurs simultanés (accès à l'avant en même temps) ou avec des lecteurs et des écrivains concurrents (accéder simultanément à l'arrière et à l'avant). Compte tenu de cette définition, il n'y a aucune raison de vouloir regarder "à l'intérieur" de la file d'attente. Vous mettez les choses d'un côté et prenez les choses de l'autre côté. Si vous prenez en compte de la taille de la file d'attente, vous pouvez avoir besoin d'un prédicat d'espace de définition supplémentaire pour l'opération push pour déterminer si la file d'attente est pleine. "Être plein" n'a de sens que si la file d'attente est limitée. "Etre vide" n'est pertinent que si le thread appelant pop ou inspecte ne souhaite pas bloquer. Au-delà de cela, il y a l'idée pragmatique d'une file d'attente. Nous pouvons supposer qu'il s'agit d'une séquence d'éléments qui, sauf en ce qui concerne les problèmes de simultanéité, a une taille observable non négative et peut même autoriser la visite de chaque élément de la séquence. Certaines files d'attente vont même jusqu'à permettre le retrait ou le réarrangement d'éléments à des positions autres que le début de la séquence. À ce stade, cependant, nous ne discutons plus vraiment d'une file d'attente. Nous discutons de la séquence qui sous-tend la file d'attente. Si nous avons besoin de ce type d'accès, nous n'avons pas besoin de file d'attente. Nous avons besoin d'une séquence dont nous voulons offrir une file d'attente, comme voir à d'autres parties du programme. C'est pourquoi les files d'attente ne sont généralement pas des types concrets dans les bibliothèques de structure de données. En C++, le type std::queue est un décorateur autour d'un autre type de conteneur. En Java, java.util.Queue est une interface. Scala adopte une approche différente: la classe scala.collection.mutable.Queue est une extension de type MutableList. C'est similaire à l'approche mandatée dans la tâche de votre fils, mais il n'est pas clair que votre ListQueue ait jamais voulu permettre aux outsiders (y compris les sous-classes) de profiter de sa "nature de liste" - pénétrant dans la file d'attente pour utiliser la séquence.

Avez-vous besoin d'être en mesure de visiter autre chose que la tête de votre file d'attente? Ne pas le faire limite vos choix quant aux types de files d'attente que vos fonctions de consommation peuvent prendre en charge. Il semble que nous apprenons les mauvaises leçons avec cette tâche.