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