Java队列链表

Question

在学校，我们正在学习抽象数据结构。我们的任务是将链表实现到 java。出于某种原因，我的队列仅使队列中的第二个元素出队。也许有人可以告诉我我的错误，因为我已经不知道了。顺便说一句，我正在使用 BlueJ 进行编码，所以不要怀疑程序的开始 :D

出列方法

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;
    }
}

Answer 1

看看，它是一个动态队列实现。

车（只是车，不是队列节点）

public class Car {

    private String driver;

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

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

}

QueueForCars（实现只处理汽车的队列）

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 );

    }

}

如果您想要队列的通用实现，即可以处理任何类型数据的队列，您的实现应该类似于：

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();

    }

}

Fruit（另一个class测试通用队列）

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();


    }

}

我的一些代码是多余的，例如，两个队列的构造函数，因为它们为队列成员设置了默认值，但我认为这种方式在学习时更好理解。希望对您有所帮助！

Java队列链表

Java Queue linked list

java

queue

implementation