#include <iostream>
#include <bits/stdc++.h>
#include <time.h>
#include <pthread.h>
#include <atomic>
#include <string>
#include <chrono>

class WriteDescriptor {
    public:
    bool op;
    int value;

    WriteDescriptor(bool o) {
        //pop
        op = o;
    }
    WriteDescriptor(bool o) {
        //constroctor for push
    }

};

class Desc {
    public:
    int size;
    WriteDescriptor<int>* dop;

    Desc(bool op) {
        //pop
        dop = new WriteDescriptor<int>(op);
    }

    Desc(int x, bool op) {
        // constructor for push
    }

    // initialize size

};

class Node {
    public:
    int value;
    bool fnode;
    Node *next;

    //constructors

};


class Stack {

    public:
    atomic<Node<int>*> head;
    atomic<Node<int>*> garbage;
    atomic<Desc<int>*> descriptor;
    atomic<int> numOps;

    Stack() {
        //constructor
    }

    bool complete() {
        Desc<int>* d = descriptor.load();
        if(d->dop->op == false) {
            //push
            //code for completing push
            return true;
        }
        else {
            //pop
            //code for completing push

            return true;
        }
    }

    bool push(int x) {

        Desc<int> *d = new Desc<int>(x, false);
        Desc<int> *old_d = descriptor.load();

        do {
            d->size = old_d->size + 1;
            complete();
        }
        while(!descriptor.compare_exchange_strong(old_d, d));
        complete();
        atomic_fetch_add(&numOps, 1);

        return true;
    }

    bool pop() {
        Desc<int> *d = new Desc<int>(true);
        Desc<int> *old_d = descriptor.load();


        do {
            if(old_d->size > 0)
                d->size = old_d->size - 1;

            complete();
        }
        while(!descriptor.compare_exchange_strong(old_d, d));


        complete();
        atomic_fetch_add(&numOps, 1);

        return true;

    }

    bool collect_garbage(Node<int> *n) {

        Node<int> *old_garbage_head = garbage.load();
        do {
            n->next = old_garbage_head;
        } while(!garbage.compare_exchange_weak(old_garbage_head, n));

        return true;
    }
};



int main() {

    return 0;

}