Блог

Моя очередь использует стек, поэтому у меня есть два стека.. s1 который принимает добавление, затем все его элементы перемещаются в s2 s2 мою очередь.

(массивы не используются ..)

вот моя реализация, но когда я ее тестирую, мой модульный тест удаления завершается неудачей.

 public class Queue
{
    private Stack s1;
    private Stack s2;

    private int size;


    public Queue()
    {
        //arbitrary sized.
        s1 = new Stack();
        s2 = new Stack();

        size = 0;
    }

    public void insert(Object o)
    {
        //add object into s1.
        s1.push(o);

        size  ;
    }

    //delete from queue
       public Object remove()
       {
          int n = 0; ... arbitrary size n. //size not specified
          for(int i = 1; i <= n ; i  )
         {
           //push all elements in s1 into s2 
           s2.insert(s1.pop());
         }                 

          //decrease the size
          size--;

         return s2.pop; 
       }
    public Object peekFront()
    {
        s2.push(s1.pop());


        return s2.peek();
    }


}
  

ТЕСТ

 import org.junit.Assert;
import static org.junit.Assert.*;
import org.junit.Test;


public class QueueTest 
{
   protected Queue q;

   public QueueTest()
   {
      q = new Queue();
   }

   atTest
   public void testRemove()
       {
         assertTrue(q.isEmpty()); -- passes

         q.insert(10);
         q.insert(11);
         q.insert(12);
         q.insert(23);

         //remove
         assertEquals(10, q.remove()); --- fails

       }


   public void testPeekFront()
   {
     q.insert(80);
     q.insert(90);
     q.insert(57);

     assertEquals(20,q.peekFront());

   }
}
  

Пожалуйста, не могли бы вы указать мне правильное направление, почему мой public Object remove не работает правильно…

Например, когда я пытаюсь удалить 23? Мой тест проходит, но когда я проверяю 10, что на самом деле должно быть, тогда он завершается неудачей.

Вот полный код ….. как для класса, так и для теста…

Я думаю, вы можете указывать статическое значение для n. Поскольку значение n будет динамически меняться, пожалуйста, убедитесь, что вы задаете n=s1.size() [или любую пользовательскую функцию для вычисления размера]. Пожалуйста, предоставьте полный код.

Предполагаемые исправления:
1. Вы удаляете все элементы из s1 во время удаления. Сделать его (s1) пустым стеком. Поэтому вам нужно заполнить его обратно, вставив значения из s2 в саму функцию удаления. Как упоминал Фабиан в следующем ответе, используйте вспомогательный метод для переноса элементов из 1 стека в другой.
2.In метод remove(), сохраните s1.pop() во временную переменную и удалите все элементы в s2. верните временную переменную. Другие мудрые s2 будут продолжать расти.
3. установите n = s1.size();
4. верните s1.pop();

Чтобы метод работал, вы не можете просто жестко задать размер. Кроме того, вы должны переместить элементы обратно в исходный стек перед следующей вставкой, иначе порядок станет неправильным. Я рекомендую переносить объекты в вспомогательный метод, чтобы избежать дублирования кода:

 private static void transfer(Stack source, Stack target) {
     while (!source.isEmpty()) {
         target.push(source.pop());
     }
}
  

Я рекомендую перемещать элементы лениво, чтобы избежать ненужных операций для повторяющихся insert или повторяющихся remove операций:

 public void insert(Object o) {
    // lazily transfer values back
    transfer(s2, s1);

    //add object into s1.
    s1.push(o);

    size  ;
}

//delete from queue
public Object remove() {
    if (s1.isEmpty() amp;amp; s2.isEmpty()) {
         return null; // alternative: throw exception
    }
    transfer(s1, s2);
    //decrease the size
    size--;
    return s2.pop();
}

public Object peekFront() {
    if (s1.isEmpty() amp;amp; s2.isEmpty()) {
        return null; // alternative: throw exception
    }

    transfer(s1, s2);

    return s2.peek();
}
  

В качестве альтернативы вы могли бы просто перенести значения обратно s1 в remove метод, что немного упростило бы реализацию дополнительных операций, однако это также сделало бы некоторые последовательности операций менее эффективными. (Вам также все еще нужно исправить peekFront() ):

 //delete from queue
public Object remove() {
    if (s1.isEmpty() amp;amp; s2.isEmpty()) {
         return null; // alternative: throw exception
    }
    transfer(s1, s2);

    //decrease the size
    size--;

    Object result = s2.pop();

    transfer(s2, s1);
    return resu<
}