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