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

Хотя это хорошо известный алгоритм, я решил реализовать его с точки зрения кодирования интервью. Я хочу знать, могу ли я как-нибудь улучшить код. Итак, учитывая временные ограничения, является ли это достаточно хорошим решением, чтобы произвести впечатление на интервьюера?

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;

    MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void enqueue(int item) {
        s1.push(item);
    }

    private void move() {
        if (s1.isEmpty()) {
            throw new NoSuchElementException();
        } else {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }

    }

    public int peek() {
        if (s2.isEmpty()) {
            move();
        }
        return s2.peek();
    }

    public int dequeue() {
        if (s2.isEmpty()) {
            move();
        }
        return s2.pop();
    }
}

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        MyQueue q = new MyQueue();
        for (int i = 0; i < N; i++) {
            int op = s.nextInt();
            switch (op) {
                case 1:
                    int item = s.nextInt();
                    q.enqueue(item);
                    break;
                case 2:
                    q.dequeue();
                    break;
                case 3:
                    System.out.println(q.peek());
                    break;
                default:
                    System.out.println("Invalid option");
            }
        }

    }
}
8 голосов | спросил CodeYogi 19 MonEurope/Moscow2016-12-19T10:20:18+03:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2016 10:20:18 +0300 2016, 10:20:18

6 ответов


5

Возможно, вы могли бы сделать лучше, если бы вы:

  • Определить интерфейс с полным JavaDoc.
  • Сделать s1 и s2 final
  • Напишите JUnit-Test с постоянными testdata вместо чтения ввода с клавиатуры. Не используйте System.out.println в JUnit.
ответил Tobias Otto 19 MonEurope/Moscow2016-12-19T18:31:31+03:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2016 18:31:31 +0300 2016, 18:31:31
4

вы можете использовать generics для поддержки любого типа данных в очереди

   class MyQueue<T> {
      private Stack<T> s1;
      private Stack<T> s2;
ответил Damaji kalunge 19 MonEurope/Moscow2016-12-19T12:33:47+03:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2016 12:33:47 +0300 2016, 12:33:47
3

Вы можете заменить магические числа в выражениях case константами со значимыми именами.

ответил Timothy Truckle 19 MonEurope/Moscow2016-12-19T15:15:37+03:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2016 15:15:37 +0300 2016, 15:15:37
0

К сожалению, это не очередь. Последовательность

push A
push B
pop
push C
pop
pop

выходы ACB вместо ABC , Операция push должна скопировать s2 назад s1 перед выполнением s1.push().

ответил vnp 19 MonEurope/Moscow2016-12-19T21:26:26+03:00Europe/Moscow12bEurope/MoscowMon, 19 Dec 2016 21:26:26 +0300 2016, 21:26:26
0

Логика совершенна. Вышеупомянутый случай не встречается

Operation       Stack:s1     Stack:S2   output       Comment
 Push A            A                           
 -----------------------------------------------
 Push B            B                               
                   A  
------------------------------------------------
 Pop                           A           A          s2 is empty hence will   
                               B                       copy whole 1 to s2
------------------------------------------------
 Push C             C          B
------------------------------------------------
 Pop                C                      B            s2 is not empty not do
                                                        any operation of move
---------------------------------------------------
 Pop                            C          C            S2 becomes empty hence 
                                                         will copy from s1
ответил Damaji kalunge 20 TueEurope/Moscow2016-12-20T08:51:15+03:00Europe/Moscow12bEurope/MoscowTue, 20 Dec 2016 08:51:15 +0300 2016, 08:51:15
0

ENQUEUE (Q, ELEMENT)

1) В то время как stack1 не пуст, нажимайте все от satck1 до stack2.

2) Нажмите ELEMENT для stack1

3) Вставьте все обратно в стек1.

DQueue (д)

1) Если stack1 пуст, тогда ошибка

2) Поместите элемент из stack1 и верните его

ответил user126250 20 TueEurope/Moscow2016-12-20T18:00:33+03:00Europe/Moscow12bEurope/MoscowTue, 20 Dec 2016 18:00:33 +0300 2016, 18:00:33

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132