CSES - Kääntölista Tehtäväsi on toteuttaa oma tehokas tietorakenne kääntölista, joka tarjoaa seuraavat toiminnot:
  • Lisää alkio listan loppuun
  • Palauta ja poista alkio listan lopusta
  • Lisää alkio listan alkuun
  • Palauta ja poista alkio listan alusta
  • Käännä listan sisältö
Tietorakenteen jokaisen operaation tulee olla $O(1)$-aikainen. Voit olettaa, että jokainen alkio on kokonaisluku väliltä $1 \dots 10^9$.

Python

Toteuta tiedostoon fliplist.py luokka FlipList seuraavan mallin mukaisesti.
class FlipList:
    def push_last(self,x):
        # TODO

    def push_first(self,x):
        # TODO

    def pop_last(self):
        # TODO

    def pop_first(self):
        # TODO

    def flip(self):
        # TODO

if __name__ == "__main__":
    f = FlipList()
    f.push_last(1)
    f.push_last(2)
    f.push_last(3)
    print(f.pop_first()) # 1
    f.flip()
    print(f.pop_first()) # 3
Java

Toteuta tiedostoon FlipList.java luokka FlipList seuraavan mallin mukaisesti.
public class FlipList {
    public void pushLast(int x) {
        // TODO
    }

    public void pushFirst(int x) {
        // TODO
    }

    public int popLast() {
        // TODO
    }

    public int popFirst() {
        // TODO
    }

    public void flip() {
        // TODO
    }

    public static void main(String[] args) {
        FlipList f = new FlipList();
        f.pushLast(1);
        f.pushLast(2);
        f.pushLast(3);
        System.out.println(f.popFirst()); // 1
        f.flip();
        System.out.println(f.popFirst()); // 3
    }
}