Erikoispino

Toteuta luokka SpecialStack, jossa on seuraavat metodit:

• push(x): lisää luku x pinon päälle
• pop(): palauta ja poista pinon ylin luku
• increase(k): kasvata pinon $k$ ylimmän luvun arvoa yhdellä

Kaikkien metodien tulee toimia ajassa $O(1)$.

Toteuta tiedostoon specialstack.py luokka SpecialStack seuraavan mallin mukaisesti.

class SpecialStack:
    def __init__(self):
        # TODO

    def push(self, x):
        # TODO

    def pop(self):
        # TODO

    def increase(self, k):
        # TODO

if __name__ == "__main__":
    s = SpecialStack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.increase(2)
    print(s.pop()) # 4
    s.push(1)
    s.increase(2)
    print(s.pop()) # 2
    print(s.pop()) # 4
    print(s.pop()) # 1

Selitys: Pinon sisältö käyttäytyy koodipohjassa näin:

• $[]$
• push(1) $\rightarrow$ $[1]$
• push(2) $\rightarrow$ $[1,2]$
• push(3) $\rightarrow$ $[1,2,3]$
• increase(2) $\rightarrow$ $[1,3,4]$
• pop() $\rightarrow$ $[1,3]$
• push(1) $\rightarrow$ $[1,3,1]$
• increase(2) $\rightarrow$ $[1,4,2]$
• pop() $\rightarrow$ $[1,4]$
• pop() $\rightarrow$ $[1]$
• pop() $\rightarrow$ $[]$