代码之家 › 专栏 › 技术社区 › D. Hoven

Java队列链表

implementation queue java

D. Hoven · 技术社区 · 7 年前

在学校我们学习抽象数据结构。我们的任务是在java中实现链表。出于某种原因,我的队列只在队列的每一个元素中退出。也许有人可以告诉我我的错误,因为我已经没有线索了。顺便说一句,我正在使用BlueJ编码,所以不要怀疑程序的启动

出列方法

public Car dequeue()
{
    Car c = new Car(head);

    if(c != null){

            if (head.getLast() == tail) {

                if(tail == null){

                    head = null;                            
                    return c;
                }                    
                else {                        
                    head = tail;                            
                    tail = null;                          
                    return c;                    
                }  
            }                    
            else {                    
                head = head.getLast();                      
                return c;                          
            }
    }        
    return c;
}

汽车物体

public class Car
{
    private String driver;
    private Car last;

    public Car(String pDriver)
    {
        driver = pDriver;
    }

    public Car(Car c)
    {
        this.driver = c.getDriverName();        
        this.last = c.getLast();
    }

    public String getDriverName()
    {
        return driver;
    }

    public Car getLast()
    {
        return last;
    }

    public void setLast(Car pLast)
    {
        last = pLast;
    }
}

1 回复 | 直到 7 年前

davidbuzatto 7 年前

汽车 (它只是一辆车,不是队列节点)

public class Car {

    private String driver;

    public Car( String driver ) {
        this.driver = driver;
    }

    @Override
    public String toString() {
        return "Car (" + driver + ")";
    }

}

(实现仅处理汽车的队列)

public class QueueForCars {

    private class Node {
        Car value;
        Node previous;
    }

    private Node head;
    private Node tail;
    private int size;

    public QueueForCars() {
        tail = null;
        head = null;
        size = 0;
    }

    public void enqueue( Car value ) {

        Node newNode = new Node();
        newNode.value = value;
        newNode.previous = null;

        if ( isEmpty() ) {
            head = newNode;
            tail = newNode;
        } else {
            tail.previous = newNode;
            tail = newNode;
        }

        size++;

    }

    public Car dequeue() {

        if ( !isEmpty() ) {

            Car value = head.value;

            if ( head == tail ) {
                head = null;
                tail = null;
            } else {
                Node temp = head;
                head = head.previous;
                temp.previous = null;
            }

            size--;
            return value;

        } else {
            return null;
        }

    }

    public boolean isEmpty() {
        return head == null;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();

        if ( !isEmpty() ) {

            Node current = head;

            while ( current != null ) {

                if ( size == 1 ) {
                    sb.append( current.value ).append( " <- head/tail\n" );
                } else if ( current == head ) {
                    sb.append( current.value ).append( " <- head\n" );
                } else if ( current == tail ) {
                    sb.append( current.value ).append( " <- tail\n" );
                } else {
                    sb.append( current.value ).append( "\n" );
                }

                current = current.previous;

            }

        } else {
            sb.append( "empty queue!\n" );
        }

        return sb.toString();

    }

}

测验 (测试实现)

public class Test {

    public static void main( String[] args ) {

        QueueForCars queue = new QueueForCars();

        queue.enqueue( new Car( "John" ) );
        System.out.println( queue );
        queue.enqueue( new Car( "Mary" ) );
        System.out.println( queue );
        queue.enqueue( new Car( "Richard" ) );
        System.out.println( queue );
        queue.enqueue( new Car( "David" ) );
        System.out.println( queue );

        System.out.println();

        System.out.println( "Dequeued: " + queue.dequeue() );
        System.out.println( queue );
        System.out.println( "Dequeued: " + queue.dequeue() );
        System.out.println( queue );
        System.out.println( "Dequeued: " + queue.dequeue() );
        System.out.println( queue );
        System.out.println( "Dequeued: " + queue.dequeue() );
        System.out.println( queue );
        System.out.println( "Dequeued: " + queue.dequeue() ); // <- empty queue!
        System.out.println( queue );

    }

}

队列 (队列的通用实现)

public class Queue<Type> {

    private class Node<Type> {
        Type value;
        Node<Type> previous;
    }

    private Node<Type> head;
    private Node<Type> tail;
    private int size;

    public Queue() {
        tail = null;
        head = null;
        size = 0;
    }

    public void enqueue( Type value ) {

        Node<Type> newNode = new Node<>();
        newNode.value = value;
        newNode.previous = null;

        if ( isEmpty() ) {
            head = newNode;
            tail = newNode;
        } else {
            tail.previous = newNode;
            tail = newNode;
        }

        size++;

    }

    public Type dequeue() {

        if ( !isEmpty() ) {

            Type value = head.value;

            if ( head == tail ) {
                head = null;
                tail = null;
            } else {
                Node<Type> temp = head;
                head = head.previous;
                temp.previous = null;
            }

            size--;
            return value;

        } else {
            return null;
        }

    }

    public boolean isEmpty() {
        return head == null;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();

        if ( !isEmpty() ) {

            Node<Type> current = head;

            while ( current != null ) {

                if ( size == 1 ) {
                    sb.append( current.value ).append( " <- head/tail\n" );
                } else if ( current == head ) {
                    sb.append( current.value ).append( " <- head\n" );
                } else if ( current == tail ) {
                    sb.append( current.value ).append( " <- tail\n" );
                } else {
                    sb.append( current.value ).append( "\n" );
                }

                current = current.previous;

            }

        } else {
            sb.append( "empty queue!\n" );
        }

        return sb.toString();

    }

}

水果

public class Fruit {

    private String name;
    private String color;

    public Fruit( String name, String color ) {
        this.name = name;
        this.color = color;
    }

    @Override
    public String toString() {
        return "Fruit (" + name + " is " + color + ")";
    }

}

测验 (测试汽车和水果的通用队列)

public class Test {

    public static void main( String[] args ) {

        Queue<Car> queueForCars = new Queue<>();

        queueForCars.enqueue( new Car( "John" ) );
        System.out.println( queueForCars );
        queueForCars.enqueue( new Car( "Mary" ) );
        System.out.println( queueForCars );
        queueForCars.enqueue( new Car( "Richard" ) );
        System.out.println( queueForCars );
        queueForCars.enqueue( new Car( "David" ) );
        System.out.println( queueForCars );

        System.out.println();

        Queue<Fruit> queueForFruits = new Queue<>();

        queueForFruits.enqueue( new Fruit( "Apple", "red" ) );
        System.out.println( queueForFruits );
        queueForFruits.enqueue( new Fruit( "Banana", "yellow" ) );
        System.out.println( queueForFruits );
        queueForFruits.enqueue( new Fruit( "Lime", "green" ) );
        System.out.println( queueForFruits );

        System.out.println();


    }

}