АСП1/К1 2020

2. zadatak

Postavka

Neka je dat stek s1 na kome se nalaze celi brojevi. Korišćenjem dodatnog steka s2, transformisati sadržaj steka s1 tako da on postane neopadajuće uređen niz. Smatrati da su operacije za rad sa stekom već implementirane.

Rešenje

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 = 0 to tmp - 1 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