template<typename T>
class lock_free_stack
{
private:
    struct node
    {
        T data;
        node* next;
        node(T const& data_):
        data(data_)
        {
        }
    };

    std::atomic<node*> head;

public:
    void push(T const& data)
    {
        node* const new_node=new node(data);
        new_node->next=head.load();  

        /*
        ** 當(dāng)前值.compare_exchange_weak(期望值, 設(shè)置值)
        ** 單線程的情況：
        ** 第一次執(zhí)行while循環(huán)：
        ** 此時當(dāng)前值與期望值相等，修改當(dāng)前值為設(shè)定值 head = new_node，返回true
        ** 多線程的情況：
        ** 第一次執(zhí)行循環(huán)體的時候：
        ** compare_exchange_weak如果失敗, 返回false, 證明有其他線程更新了棧頂head，
        ** 當(dāng)前值與期望值不等時，將期望值修改為當(dāng)前值, 即new_node->next等于新的棧頂head,
        ** 被其他線程更新的新棧頂值會被更新到new_node->next中，
        ** 因此循環(huán)可以直接再次嘗試壓棧而無需由程序員更新new_node->next。
        ** 然后第二次執(zhí)行循環(huán)體：
        ** 此時 head == new_node->next, 所以 head = new_node.
        ** 如果這是仍有其他線程干擾，則仍為循環(huán)更新new_node->next
        */
        while(!head.compare_exchange_weak(new_node->next,new_node));
    }
};

bool compare_and_swap ( int *memory_location, int expected_value, int new_value)
{
    if (*memory_location == expected_value)
    {
        *memory_location = new_value;
        return true;
    }
    return false;
}