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