Очереди в Java. Что не так с моей реализацией, и что я могу использовать? - PullRequest
Новая
       19

Очереди в Java. Что не так с моей реализацией, и что я могу использовать?

1 голос
/ 29 ноября 2011

Я пытаюсь выполнить поиск в ширину, чтобы решить головоломку со сдвигом квадратов (та, в которой вы перемещаете квадраты в пустое пространство до тех пор, пока она не будет решена). Мой алгоритм в ширину использует очередь. К сожалению, кажется, что это работает только для случаев ВВЕРХ и ВНИЗ, а не для ВЛЕВО или ВПРАВО: 

                if (up)
            {
                int[][] current = copy(v.state);
                current[x][y] = current[x - 1][y];
                current[x - 1][y] = 0;

                State w = new State(current);
                w.distance = v.distance + 1;
                w.path = v;
                System.out.println(q.insert(w));
            }

            if (down)
            {
                int[][] current = copy(v.state);
                current[x][y] = current[x + 1][y];
                current[x + 1][y] = 0;

                State w = new State(current);
                w.distance = v.distance + 1;
                w.path = v;
                System.out.println(q.insert(w));
            }

            if (left)
            {
                int[][] current = copy(v.state);
                current[x][y] = current[x][y - 1];
                current[x][y - 1] = 0;

                State w = new State(current);
                w.distance = v.distance + 1;
                w.path = v;
                System.out.println(q.insert(w));
            }

            if (right)
            {
                int[][] current = copy(v.state);
                current[x][y] = current[x][y + 1];
                current[x][y + 1] = 0;

                State w = new State(current);
                w.distance = v.distance + 1;
                w.path = v;
                System.out.println(q.insert(w));
            }

Я думаю, что это проблема с моей очередью, реализация которой приведена ниже. Что-то не так с моей очередью, или это другая проблема? Есть ли в Java API класс очереди, который я мог бы использовать? 

public class ArrayQueue {
State[] items;
int maxSize;
int front;
int rear;
int numItems;

public ArrayQueue(int max)
{
    items = new State[max];
    maxSize = max;
    front = 0;
    rear = -1;
    numItems = 0;
}

public boolean insert(State item)
{
    if (isFull()) return false;
    rear = (rear + 1) % items.length;
    items[rear] = item;
    return true;
}

public State remove()
{
    if (isEmpty()) return null;
    State removed = items[front];
    front = (front + 1) % items.length;
    return removed;
}

public boolean isFull()
{
    if ((front + 1) % maxSize == rear)
        return true;
    else
        return false;
}

public boolean isEmpty()
{
    if ((rear + 1) % maxSize == front)
            return true;
    else
        return false;
}
}

Вот метод копирования: 

public static int[][] copy(int[][] input)       //This method is necessary because we are trying to clone a multi-dimensional array.
{                                               //Just using clone() will copy the outer arrays but they will be arrays of references to the original inner arrays.
int[][] output = new int[input.length][];
for (int i = 0; i < input.length; i++)
    output[i] = input[i].clone();
return output;
}

Ответы [ 2 ]

2 голосов
/ 29 ноября 2011

JDK предоставляет интерфейс Queue и ряд реализаций, которые можно найти в разделе «Все известные классы реализации» документации Queue .

Для ваших целей, LinkedList должно быть достаточно хорошим.

0 голосов
/ 29 ноября 2011

Полагаю, проблема в «спереди» и «сзади». Они должны указывать на одну и ту же позицию 0 в начале, поэтому, когда они равны, очередь пуста. «Сзади» будет указывать на позицию для записи (запись, а затем смещение вперед) и «вперед» на позицию для чтения (чтение и затем смещение). «Задний», кажется, движется вперед быстрее, пока очередь заполняется. Когда он пойдет до конца, он вернется к попрошайничеству. Поэтому вам нужно выполнить (тыл + 1)% max == спереди, чтобы проверить, можете ли вы безопасно вставить новый элемент.

Также рассмотрите возможность использования некоторых стандартных реализаций, как предложил г-н Сиддики.

...