Почему dequeue не работает должным образом для моего кода? - PullRequest
Новая
       5

Почему dequeue не работает должным образом для моего кода?

0 голосов
/ 16 января 2019

Я сделал код для очереди, используя два стека. Но часть кода в dequeue ведет себя странно, она правильно удаляет первый элемент в тесте, а второй и третий элементы имеют неправильный порядок.

Это код dequeue, я использую: 

public T dequeue() throws NoSuchElementException {

while(!s1.isEmpty()){
  T tmp = s1.pop();
  s2.push(tmp);
}

Stack<T> temp = new Stack<>();
temp = s1;
s1 = s2;
s2 = temp;

    return s1.pop();
}

Это код тестового примера, который дает обратный порядок для 51 и 86. 

@Test
public void testTwoElement() {
    Queue<Integer> q = new Queue<>();
    q.enqueue(42);
    q.enqueue(51);
    q.enqueue(86);
    assertEquals(3, q.size());
    assertEquals(new Integer(42), q.dequeue());
    assertEquals(new Integer(51), q.dequeue());
    assertEquals(new Integer(86), q.dequeue());
    assertEquals(0,q.size());
    assertEquals(true,q.isEmpty());
}

Я не могу понять причину, почему это происходит так. Буду признателен, если кто-нибудь скажет мне, что не так с кодом.

Ответы [ 2 ]

0 голосов
/ 16 января 2019

Причина в том, что вы повторно заказываете s1 при вызове dequeue во второй раз.

Это объясняется ниже,

Исходное состояние:

s1: 86 -> 51 -> 42

Первая очередь:

s1: 86 -> 51 -> 42

s2:

очистите s1 и добавьте элементы в s2:

s1:

s2: 42 -> 51 -> 86

Теперь поменяйте местами s1 и s2:

s1: 42 -> 51 -> 86

s2:

Теперь выведите s1 и верните 42:

s1: 51 -> 86

Вторая очередь:

s1: 51 -> 86

s2:

пустой s1 и добавление элементов в s2:

s1:

s2: 86 -> 51

Теперь поменяйте местами s1 и s2:

s1: 86 -> 51

s2:

Теперь вставьте s1 и верните 86:

s1: 51

Правильный способ решить эту проблему - не менять s1 на s2 и ждать завершения всех элементов в s2а затем заселить s2 с s1.Я не добавляю реализацию, как это уже сделано в другом ответе mangusta.

0 голосов
/ 16 января 2019

Обмен s1 и s2 здесь не требуется. Удалите измененные строки кода и замените return s1.pop(); на return s2.pop();
Я предполагаю, что вы всегда помещаете элемент в очередь в s1.
Кроме того, вам нужно перемещать элементы с s1 на s2 только тогда, когда s2 не имеет ничего всплывающего. 

public T dequeue() throws NoSuchElementException {

if(s2.isEmpty())
{
  while(!s1.isEmpty()){
    T tmp = s1.pop();
    s2.push(tmp);
  }
}


    return s2.pop();
}
...