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 []