Реализация очереди с использованием двух стеков

В углу кода мы берем реальную задачу программирования интервью и решаем ее в коде. Хотя эти вопросы могут быть заданы как упражнение для доски, вы, как разработчик, узнаете гораздо больше, фактически написав код решения и научившись использовать API, коллекции и алгоритмы в обсуждении.

Вы можете скачать это упражнение с CJIQ Github по адресу https://github.com/corejavainterviewquestions/queuefromtwostacks . Каждый этап является коммитом; Откат к первоначальной проверке и код на ветке. Затем вы можете сравнить свой ответ с моим. Результаты разработаны с использованием TDD.

Создание очереди из двух стеков — один из тех вопросов, который, кажется, задерживался годами и до сих пор задается. Это полезно знать на случай, если его спросят, но, что более важно, это хорошая возможность больше узнать о стеках, очередях и расчете Big O.

Задача проста. Реплицируйте функциональность очереди, используя два стека.

Очередь — это структура данных «первым пришел — первым обслужен» (FIFO). Если вы добавите элементы A, B и C в таком порядке, а затем трижды выскочит, вы получите A, B и C. И наоборот, стек — это структура «последний пришел первым — вышел» (LIFO); В этом же примере вы получите C, B, а затем A.

Вы можете прочитать больше об этих структурах данных в  предыдущем посте об интервью и структурах данных.

В очереди есть 2 метода, которые нас интересуют: добавить и удалить. Стек имеет толчок и поп.
Давайте начнем с нашего первого провального теста.

 @Test
 public void addingOneItemAndRemovingFromQueueWillReturnThatItem() throws Exception {
     Queue queue = new Queue();
     queue.add(“Item 1”);
 
     assertThat(queue.remove(), is(“Item 1”));
 }

 Stack stackOne = new Stack();
 public void add(String item) {
     stackOne.push(item);
 }
 public String remove() {
     return stackOne.pop();
 }

 @Test
 public void
 addingMultipleItemsThenRemovingOneWillReturnFirstItem() throws Exception {
     Queue queue = new Queue();
     queue.add(“Item 1”);
     queue.add(“Item 2”);
     queue.add(“Item 3”);
     assertThat(queue.remove(), is(“Item 1”));
 }

 public String remove() {
     String result = null;
     while(!stackOne.isEmpty())
         result = stackOne.pop();
     return result;
 }

@Test
 public void
 addingThreeItemsThenRemovingTwoWillReturnItemOneThenTwo() throws Exception {
     Queue queue = new Queue();
     queue.add(“Item 1”);
     queue.add(“Item 2”);
     queue.add(“Item 3”);
     assertThat(queue.remove(), is(“Item 1”));
     assertThat(queue.remove(), is(“Item 2”));
 }

public String remove() {
     while(!stackOne.isEmpty()) {
         stackTwo.push(stackOne.pop());
     }
     String result = stackTwo.pop();
     while(!stackTwo.isEmpty()) {
         stackOne.push(stackTwo.pop());
     }
     return result;
 }

 public String remove() {
     swapStacks(stackOne, stackTwo);
     String result = stackTwo.pop();
     swapStacks(stackTwo, stackOne);
     return result;
 }
 private void swapStacks(Stack stackOne, Stack stackTwo) {
     while(!stackOne.isEmpty())
         stackTwo.push(stackOne.pop());
 }

@Test(expected = NoSuchElementException.class)
 public void throwsErrorIfRemoveCalledOnEmptyQueue(){
     Queue queue = new Queue();
     queue.remove();
 }

public String remove() {
     if(stackOne.isEmpty())
         throw new NoSuchElementException(“The Queue Is Empty”);
     swapStacks(stackOne, stackTwo);
     String result = stackTwo.pop();
     swapStacks(stackTwo, stackOne);
     return result;
 }

 @Test
 public void multipleAddsAndRemovesInCorrectOrder() throws Exception {
     Queue queue = new Queue();
     queue.add(“Item 1”);
     queue.add(“Item 2”);
     assertThat(queue.remove(), is(“Item 1”));
     queue.add(“Item 3”);
     assertThat(queue.remove(), is(“Item 2”));
     queue.add(“Item 4”);
     queue.add(“Item 5”);
     queue.add(“Item 6”);
     assertThat(queue.remove(), is(“Item 3”));
     assertThat(queue.remove(), is(“Item 4”));
 }

public String remove() {
     if(stackOne.isEmpty() && stackTwo.isEmpty())
         throw new NoSuchElementException(“The Queue Is Empty”);
     if(stackTwo.isEmpty())
     while(!stackOne.isEmpty())
         stackTwo.push(stackOne.pop());
     return stackTwo.pop();
 }