Зваротны метад пераварочвае элементы чарзе

Гэта не з'яўляецца HW або прызначэнне. Гэта тое, што я буду практыкаваць самастойна.

Улічваючы чаргу, напісаць зваротны метад пераварочвае элементы чарзе. MyQueue застаецца нязменным.

подпіс:

public Queue reverse(Queue myQueue) {

Заўвага: невядома, калі чаргу вырабляецца з выкарыстаннем вузлоў ці масіва.

Очеред метады ўжо рэалізаваны, што мы можам выкарыстоўваць:

void enqueue(T element)
T dequeue();
boolean isFull();
boolean isEmpty();
int size();
6
Вы маеце на ўвазе гэта не JDK ў Queue рэалізацыя?
дададзена аўтар fge, крыніца
@ User503413 той пункт, вы проста атрымаеце імёны метадаў, якія вы можаце выкарыстоўваць:
дададзена аўтар user2272227, крыніца
@ User503413 той пункт, вы проста атрымаеце імёны метадаў, якія вы можаце выкарыстоўваць:
дададзена аўтар user2272227, крыніца
Hack: Выкарыстоўвайце java.util.ArrayList у якасці буфера.
дададзена аўтар johnchen902, крыніца
Hack: Выкарыстоўвайце java.util.ArrayList у якасці буфера.
дададзена аўтар johnchen902, крыніца
Калі ласка, вы можаце напісаць код, які вы ўжо напісалі?
дададзена аўтар Olimpiu POP, крыніца
Калі ласка, вы можаце напісаць код, які вы ўжо напісалі?
дададзена аўтар Olimpiu POP, крыніца

12 адказы

Вы можаце адмяніць чарзе з дапамогай стэка.

Вось як у Java:

public void reverse(Queue q)
{
    Stack s = new Stack();  //create a stack

    //while the queue is not empty
    while(!q.isEmpty())
    {  //add the elements of the queue onto a stack
       s.push(q.serve());
    } 

    //while the stack is not empty
    while(!s.isEmpty())
    { //add the elements in the stack back to the queue
      q.append(s.pop());
    }

}
<�Р> <�моцны> Append </моцны> і <�моцны> служыць </моцны> метады чаргі з'яўляюцца для дадання і выдалення элементаў гэтай чарзе. </Р>

Вось прыклад:

Чарга змяшчае элементы:

1 2 3 4

Калі элементы дадаюцца ў стэк, лік 1 будзе знаходзіцца ў ніжняй частцы спісу і 4 у верхняй часткі:

1 2 3 4 <- top

Цяпер поп-стэк і змясціць элементы назад у чаргу:

4 3 2 1

Я спадзяюся, што гэта дапамагло.

6
дададзена

Вы можаце адмяніць чарзе з дапамогай стэка.

Вось як у Java:

public void reverse(Queue q)
{
    Stack s = new Stack();  //create a stack

    //while the queue is not empty
    while(!q.isEmpty())
    {  //add the elements of the queue onto a stack
       s.push(q.serve());
    } 

    //while the stack is not empty
    while(!s.isEmpty())
    { //add the elements in the stack back to the queue
      q.append(s.pop());
    }

}
<�Р> <�моцны> Append </моцны> і <�моцны> служыць </моцны> метады чаргі з'яўляюцца для дадання і выдалення элементаў гэтай чарзе. </Р>

Вось прыклад:

Чарга змяшчае элементы:

1 2 3 4

Калі элементы дадаюцца ў стэк, лік 1 будзе знаходзіцца ў ніжняй частцы спісу і 4 у верхняй часткі:

1 2 3 4 <- top

Цяпер поп-стэк і змясціць элементы назад у чаргу:

4 3 2 1

Я спадзяюся, што гэта дапамагло.

6
дададзена

Вы можаце адмяніць чарзе з дапамогай стэка.

Вось як у Java:

public void reverse(Queue q)
{
    Stack s = new Stack();  //create a stack

    //while the queue is not empty
    while(!q.isEmpty())
    {  //add the elements of the queue onto a stack
       s.push(q.serve());
    } 

    //while the stack is not empty
    while(!s.isEmpty())
    { //add the elements in the stack back to the queue
      q.append(s.pop());
    }

}
<�Р> <�моцны> Append </моцны> і <�моцны> служыць </моцны> метады чаргі з'яўляюцца для дадання і выдалення элементаў гэтай чарзе. </Р>

Вось прыклад:

Чарга змяшчае элементы:

1 2 3 4

Калі элементы дадаюцца ў стэк, лік 1 будзе знаходзіцца ў ніжняй частцы спісу і 4 у верхняй часткі:

1 2 3 4 <- top

Цяпер поп-стэк і змясціць элементы назад у чаргу:

4 3 2 1

Я спадзяюся, што гэта дапамагло.

6
дададзена
    <�Літый> Dequeue элементы ўваходных чэргі ў стэк </літый> <�Літый> поп элементы з стэка, enqueueing кожны ў выходны чарзе.
5
дададзена
Дзякуй браценік, вось што я на самой справе зрабіў, але я хацеў, каб убачыць, ці ёсць лепшае рашэнне?
дададзена аўтар user2272227, крыніца
Ці не з інтэрфейсам вы далі. Існуе структура дадзеных называецца двухбаковая чарзе , што дазваляе дадаваць і выдаляць элементы на абодвух канцах. Рэверсіўны такую ​​структуру дадзеных можа быць зроблена без якога-небудзь часовага буфера.
дададзена аўтар Oswald, крыніца
    <�Літый> Dequeue элементы ўваходных чэргі ў стэк </літый> <�Літый> поп элементы з стэка, enqueueing кожны ў выходны чарзе.
5
дададзена
Дзякуй браценік, вось што я на самой справе зрабіў, але я хацеў, каб убачыць, ці ёсць лепшае рашэнне?
дададзена аўтар user2272227, крыніца
Ці не з інтэрфейсам вы далі. Існуе структура дадзеных называецца двухбаковая чарзе , што дазваляе дадаваць і выдаляць элементы на абодвух канцах. Рэверсіўны такую ​​структуру дадзеных можа быць зроблена без якога-небудзь часовага буфера.
дададзена аўтар Oswald, крыніца
    <�Літый> Dequeue элементы ўваходных чэргі ў стэк </літый> <�Літый> поп элементы з стэка, enqueueing кожны ў выходны чарзе.
5
дададзена
Дзякуй браценік, вось што я на самой справе зрабіў, але я хацеў, каб убачыць, ці ёсць лепшае рашэнне?
дададзена аўтар user2272227, крыніца
Ці не з інтэрфейсам вы далі. Існуе структура дадзеных называецца двухбаковая чарзе , што дазваляе дадаваць і выдаляць элементы на абодвух канцах. Рэверсіўны такую ​​структуру дадзеных можа быць зроблена без якога-небудзь часовага буфера.
дададзена аўтар Oswald, крыніца

Вы можаце зрабіць гэта без якіх-небудзь іншых масіваў або спісаў, проста рэкурсіі:

public static  Queue flip(Queue q) {
    Queue ret = new Queue<>();
    recursiveFlip(q, ret);
    return ret;
}

private static  void recursiveFlip(Queue src, Queue dest) {
    T buffer = src.dequeue();
    if(!src.isEmpty()) {
        recursiveFlip(src, dest);
    }
    dest.enqueue(buffer);
}

Першыя элементы будуць выкладзеныя ў «дробных» часткі стэку, у той час як апошнія элементы «глыбей» часткі, і калі Рэкурсія даходзіць да канца, «глыбей» значэння будуць дададзеныя першымі і «дробным» у мінулым.

Але зьвярніце ўвагу, што кожны элемент азначае адзін крок ўглыб рэкурсіі, таму стэк памылку перапаўнення будзе адбывацца, калі чарга занадта вялікая.

Акрамя таго, арыгінальная чаргу не будзе «выжыць» фліп.

3
дададзена

Вы можаце зрабіць гэта без якіх-небудзь іншых масіваў або спісаў, проста рэкурсіі:

public static  Queue flip(Queue q) {
    Queue ret = new Queue<>();
    recursiveFlip(q, ret);
    return ret;
}

private static  void recursiveFlip(Queue src, Queue dest) {
    T buffer = src.dequeue();
    if(!src.isEmpty()) {
        recursiveFlip(src, dest);
    }
    dest.enqueue(buffer);
}

Першыя элементы будуць выкладзеныя ў «дробных» часткі стэку, у той час як апошнія элементы «глыбей» часткі, і калі Рэкурсія даходзіць да канца, «глыбей» значэння будуць дададзеныя першымі і «дробным» у мінулым.

Але зьвярніце ўвагу, што кожны элемент азначае адзін крок ўглыб рэкурсіі, таму стэк памылку перапаўнення будзе адбывацца, калі чарга занадта вялікая.

Акрамя таго, арыгінальная чаргу не будзе «выжыць» фліп.

3
дададзена

Вы можаце зрабіць гэта без якіх-небудзь іншых масіваў або спісаў, проста рэкурсіі:

public static  Queue flip(Queue q) {
    Queue ret = new Queue<>();
    recursiveFlip(q, ret);
    return ret;
}

private static  void recursiveFlip(Queue src, Queue dest) {
    T buffer = src.dequeue();
    if(!src.isEmpty()) {
        recursiveFlip(src, dest);
    }
    dest.enqueue(buffer);
}

Першыя элементы будуць выкладзеныя ў «дробных» часткі стэку, у той час як апошнія элементы «глыбей» часткі, і калі Рэкурсія даходзіць да канца, «глыбей» значэння будуць дададзеныя першымі і «дробным» у мінулым.

Але зьвярніце ўвагу, што кожны элемент азначае адзін крок ўглыб рэкурсіі, таму стэк памылку перапаўнення будзе адбывацца, калі чарга занадта вялікая.

Акрамя таго, арыгінальная чаргу не будзе «выжыць» фліп.

3
дададзена

Я выкарыстаў два розных падыходу, якія не залежаць ад памеру чарзе. Першы з іх выкарыстоўвае <�моцны> Stack і другі адзін - <�моцны> Java 8 Паток API (самы хуткі).

Найбольш эфектыўнае рашэнне для реверсівного чарзе ў маіх тэстах:

private Queue reverse(Queue queue) {
        List collect = queue.stream()
                .collect(Collectors.toList());
        Collections.reverse(collect);
        return new LinkedList<>(collect);
    }
1
дададзена

Я выкарыстаў два розных падыходу, якія не залежаць ад памеру чарзе. Першы з іх выкарыстоўвае <�моцны> Stack і другі адзін - <�моцны> Java 8 Паток API (самы хуткі).

Найбольш эфектыўнае рашэнне для реверсівного чарзе ў маіх тэстах:

private Queue reverse(Queue queue) {
        List collect = queue.stream()
                .collect(Collectors.toList());
        Collections.reverse(collect);
        return new LinkedList<>(collect);
    }
1
дададзена

Я выкарыстаў два розных падыходу, якія не залежаць ад памеру чарзе. Першы з іх выкарыстоўвае <�моцны> Stack і другі адзін - <�моцны> Java 8 Паток API (самы хуткі).

Найбольш эфектыўнае рашэнне для реверсівного чарзе ў маіх тэстах:

private Queue reverse(Queue queue) {
        List collect = queue.stream()
                .collect(Collectors.toList());
        Collections.reverse(collect);
        return new LinkedList<>(collect);
    }
1
дададзена