El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

En aquest tema, explorarem les estructures de dades Queue i Deque en Java. Aquestes estructures són fonamentals per a la gestió de coles i doble coles, respectivament, i són molt útils en diverses aplicacions de programació.

Introducció a Queue

Una Queue (cola) és una estructura de dades que segueix el principi FIFO (First In, First Out), és a dir, el primer element que entra és el primer que surt. Les operacions principals en una Queue són:

enqueue: Afegir un element al final de la cua.
dequeue: Treure l'element del principi de la cua.

1.1. Implementació de Queue amb LinkedList

En Java, la interfície Queue és part del paquet java.util i pot ser implementada utilitzant diverses classes, com ara LinkedList o PriorityQueue. A continuació, veurem un exemple d'implementació amb LinkedList.

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // Afegir elements a la cua
        queue.add(1);
        queue.add(2);
        queue.add(3);

        // Mostrar la cua
        System.out.println("Cua: " + queue);

        // Treure elements de la cua
        int removedElement = queue.remove();
        System.out.println("Element tret: " + removedElement);
        System.out.println("Cua després de treure un element: " + queue);

        // Consultar el primer element de la cua
        int head = queue.peek();
        System.out.println("Primer element de la cua: " + head);
    }
}

1.2. Mètodes Principals de Queue

Mètode	Descripció
`add(e)`	Afegeix l'element `e` al final de la cua.
`remove()`	Treu i retorna l'element del principi de la cua.
`peek()`	Retorna l'element del principi de la cua sense treure'l.
`isEmpty()`	Retorna `true` si la cua està buida, `false` en cas contrari.
`size()`	Retorna el nombre d'elements a la cua.

Introducció a Deque

Una Deque (Double Ended Queue) és una estructura de dades que permet afegir i treure elements tant pel principi com pel final. Això la fa més flexible que una Queue tradicional.

2.1. Implementació de Deque amb LinkedList

En Java, la interfície Deque és part del paquet java.util i pot ser implementada utilitzant classes com LinkedList o ArrayDeque. A continuació, veurem un exemple d'implementació amb LinkedList.

import java.util.Deque;
import java.util.LinkedList;

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();

        // Afegir elements al principi i al final de la deque
        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);

        // Mostrar la deque
        System.out.println("Deque: " + deque);

        // Treure elements del principi i del final de la deque
        int removedFirst = deque.removeFirst();
        int removedLast = deque.removeLast();
        System.out.println("Element tret del principi: " + removedFirst);
        System.out.println("Element tret del final: " + removedLast);
        System.out.println("Deque després de treure elements: " + deque);

        // Consultar el primer i l'últim element de la deque
        int first = deque.peekFirst();
        int last = deque.peekLast();
        System.out.println("Primer element de la deque: " + first);
        System.out.println("Últim element de la deque: " + last);
    }
}

2.2. Mètodes Principals de Deque

Mètode	Descripció
`addFirst(e)`	Afegeix l'element `e` al principi de la deque.
`addLast(e)`	Afegeix l'element `e` al final de la deque.
`removeFirst()`	Treu i retorna l'element del principi de la deque.
`removeLast()`	Treu i retorna l'element del final de la deque.
`peekFirst()`	Retorna l'element del principi de la deque sense treure'l.
`peekLast()`	Retorna l'element del final de la deque sense treure'l.
`isEmpty()`	Retorna `true` si la deque està buida, `false` en cas contrari.
`size()`	Retorna el nombre d'elements a la deque.

Exercicis Pràctics

Exercici 1: Implementar una cua de caràcters

Implementa una cua que emmagatzemi caràcters i realitza les següents operacions:

Afegeix els caràcters 'A', 'B' i 'C' a la cua.
Treu un caràcter de la cua i mostra'l.
Mostra el caràcter que està al principi de la cua sense treure'l.

Solució

import java.util.LinkedList;
import java.util.Queue;

public class CharQueue {
    public static void main(String[] args) {
        Queue<Character> queue = new LinkedList<>();

        // Afegir caràcters a la cua
        queue.add('A');
        queue.add('B');
        queue.add('C');

        // Treure un caràcter de la cua
        char removedChar = queue.remove();
        System.out.println("Caràcter tret: " + removedChar);

        // Mostrar el caràcter al principi de la cua
        char headChar = queue.peek();
        System.out.println("Caràcter al principi de la cua: " + headChar);
    }
}

Exercici 2: Implementar una deque de nombres enters

Implementa una deque que emmagatzemi nombres enters i realitza les següents operacions:

Afegeix els nombres 10 i 20 al final de la deque.
Afegeix el nombre 5 al principi de la deque.
Treu un nombre del principi i un del final de la deque i mostra'ls.
Mostra el nombre que està al principi i al final de la deque sense treure'ls.

Solució

import java.util.Deque;
import java.util.LinkedList;

public class IntDeque {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();

        // Afegir nombres a la deque
        deque.addLast(10);
        deque.addLast(20);
        deque.addFirst(5);

        // Treure nombres del principi i del final de la deque
        int removedFirst = deque.removeFirst();
        int removedLast = deque.removeLast();
        System.out.println("Nombre tret del principi: " + removedFirst);
        System.out.println("Nombre tret del final: " + removedLast);

        // Mostrar el nombre al principi i al final de la deque
        int first = deque.peekFirst();
        int last = deque.peekLast();
        System.out.println("Nombre al principi de la deque: " + first);
        System.out.println("Nombre al final de la deque: " + last);
    }
}

Resum

En aquest tema, hem après sobre les estructures de dades Queue i Deque en Java. Hem vist com implementar-les utilitzant LinkedList i hem explorat els mètodes principals que ofereixen. També hem realitzat exercicis pràctics per reforçar els conceptes apresos. Aquestes estructures són molt útils en diverses aplicacions de programació i és important comprendre com utilitzar-les de manera eficient.

Queue i Deque

Introducció a Queue

1.1. Implementació de Queue amb LinkedList

1.2. Mètodes Principals de Queue

Introducció a Deque

2.1. Implementació de Deque amb LinkedList

2.2. Mètodes Principals de Deque

Exercicis Pràctics

Exercici 1: Implementar una cua de caràcters

Solució

Exercici 2: Implementar una deque de nombres enters

Solució

Resum

Curs de Programació en Java

Mòdul 1: Introducció a Java

Mòdul 2: Flux de Control

Mòdul 3: Programació Orientada a Objectes

Mòdul 4: Programació Orientada a Objectes Avançada

Mòdul 5: Estructures de Dades i Col·leccions

Mòdul 6: Gestió d'Excepcions

Mòdul 7: Entrada/Sortida de Fitxers

Mòdul 8: Multithreading i Concurrència

Mòdul 9: Xarxes

Mòdul 10: Temes Avançats

Mòdul 11: Frameworks i Llibreries de Java

Mòdul 12: Construcció d'Aplicacions del Món Real