Estructuras de datos en Java: Pilas, Colas y Listas Enlazadas con ejemplos de código

Interfaz Pila

Operaciones públicas

• void apilar(x): inserta x en la pila.
• void desapilar(): elimina el último elemento insertado.
• Object cima(): devuelve el último elemento insertado.
• Object cimaYDesapilar(): devuelve y elimina el elemento más reciente.
• boolean esVacia(): devuelve true si la pila está vacía, en caso contrario false.
• void vaciar(): elimina todos los elementos.
• int tamaño(): devuelve el tamaño de la pila.

Excepciones: se lanzan en cima, desapilar o cimaYDesapilar cuando la pila está vacía.

Interfaz Cola

Construcción: sin ninguna inicialización.

Operaciones públicas

• void insertar(x): inserta x en la cola.
• Object primero(): devuelve el primer elemento insertado.
• Object quitarPrimero(): devuelve y elimina el primer elemento insertado.
• boolean esVacia(): devuelve true si la cola está vacía, en caso contrario false.
• void vaciar(): elimina todos los elementos.
• int tamaño(): devuelve el tamaño de la cola.

Excepciones: se lanzan en primero o quitarPrimero cuando la cola está vacía.

Clase NodoLista

La clase NodoLista representa un nodo de una lista enlazada:

class NodoLista {
    Object dato;
    NodoLista siguiente;

    public NodoLista(Object elElemento) {
        this(elElemento, null);
    }

    public NodoLista(Object elElemento, NodoLista n) {
        dato = elElemento;
        siguiente = n;
    }
}

Listar directorios

El siguiente código recorre recursivamente un directorio y almacena en un ArrayList todos sus subdirectorios y archivos:

import java.io.*;
import java.util.*;

public class listarSubdirectorios {
    private ArrayList vector = new ArrayList();

    public ArrayList listaDA(File file) {
        vector.clear();
        vector.add(file);
        if (file.isDirectory()) {
            int i;
            String[] children = file.list();
            for (i = 0; i < children.length; i++) {
                visitar(new File(file, children[i]));
            }
        }
        return vector;
    }

    private void visitar(File file) {
        vector.add(file);
        if (file.isDirectory()) {
            String[] children = file.list();
            int i;
            for (i = 0; i < children.length; i++) {
                visitar(new File(file, children[i]));
            }
        }
    }
}

Implementación de una pila con vector: PilaVec

La clase PilaVec implementa la interfaz Pila utilizando un array que se amplía dinámicamente cuando se llena:

import org.mp.practicas.excepciones.*;

public class PilaVec implements Pila {
    private Object[] vector;
    private int cimaDePila;
    private static final int TAMAÑO = 10;

    public PilaVec() {
        vector = new Object[TAMAÑO];
        cimaDePila = -1;
    }

    public boolean esVacia() {
        if (cimaDePila == -1)
            return true;
        else
            return false;
    }

    public void vaciar() {
        cimaDePila = -1;
    }

    public Object cima() throws DesbordamientoInferiorException {
        if (esVacia() == true)
            throw new DesbordamientoInferiorException("pila vacía");
        return vector[cimaDePila];
    }

    public void desapilar() throws DesbordamientoInferiorException {
        if (esVacia() == true)
            throw new DesbordamientoInferiorException("pila vacía");
        cimaDePila--;
    }

    public Object cimaYDesapilar() throws DesbordamientoInferiorException {
        if (esVacia() == true)
            throw new DesbordamientoInferiorException("pila vacía");
        Object fuera = vector[cimaDePila];
        cimaDePila--;
        return fuera;
    }

    public void apilar(Object nuevo) {
        if (vector.length == cimaDePila + 1) {
            asegurarCapacidad();
        }
        cimaDePila++;
        vector[cimaDePila] = nuevo;
    }

    private void asegurarCapacidad() {
        Object[] auxiliar = new Object[vector.length * 2];
        for (int i = 0; i < vector.length; i++) {
            auxiliar[i] = vector[i];
        }
        vector = auxiliar;
    }

    public int tamaño() {
        return cimaDePila + 1;
    }
}