АСП1/К1 2020

Задаци на сајту предмета.

2. задатак

Поставка

Нека је дат стек с1 на коме се налазе цели бројеви. Коришћењем додатног стека с2, трансформисати садржај стека с1 тако да он постане неопадајуће уређен низ. Сматрати да су операције за рад са стеком већ имплементиране.

Решење

SORT STACK(s1)
max = TOP(s1)
cnt = 0
while (not STACK_IS_EMPTY(s1)) do
    x = POP(s1)
    if (x > max) then
        max = x
    end_if
    PUSH(s2, x)
    cnt = cnt + 1
end_while
while (not STACK_IS_EMPTY(s2)) do
    x = POP(s2)
    PUSH(s1, x)
end_while
while (cnt) do
    num = cnt
    tmp = 0
    while (num) do
        x = POP(s1)
        if (x < max) then
            PUSH(s2, x)
        else
            cnt = cnt - 1
            tmp = tmp + 1
        end_if
        num = num - 1
    end_while
    for i = 1 to tmp do
        PUSH(s1, max)
        i = i + 1
    end_for
    if (cnt) then
        max = TOP(s2)
        while (not STACK_IS_EMPTY(s2)) do
            x = POP(s2)
            if (x > max) then
                max = x
            end_if
            PUSH(s1, x)
        end_while
    end_if
end_while