Pino

Tehtäväsi on toteuttaa oma tehokas pino-tietorakenne, joka tarjoaa seuraavat toiminnot:

• Lisää luku pinon päälle
• Palauta ja poista luku pinon päältä
• Kasvata pinon k päällimmäisen luvun arvoa yhdellä

Tietorakenteen jokaisen operaation tulee olla O(1)-aikainen. Voit olettaa, että jokainen alkio on kokonaisluku väliltä 1 \dots 10^9.

Toteuta tiedostoon stack.py luokka Stack seuraavan mallin mukaisesti.

class Stack:
    def __init__(self):
        # TODO

    def push(self, x):
        # TODO

    def pop(self):
        # TODO

    def increase(self, k):
        # TODO

if __name__ == "__main__":
    s = Stack()
    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 []