АСП1/К1 2020
< АСП1
Пређи на навигацију
Пређи на претрагу
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