写一个bit队列，每次只能入队出队0或1

• 底层用普通的queue做容器，然后通过位操作精确操作容器queue中每个int（也可用char）的32位中存放的bit值。重点是要用到两个位置指针标记首元素和尾元素在int中的具体1-32的位置。

#include<iostream>
#include<queue>
using namespace std;

template<typename T>
class bit_queue
{
private:
    int size;
    int front_pos;  //首元素在第一个int数字的1-32位中的位置
    int back_pos;   //尾元素在最后一个int数字的1-32位中的位置
    queue<T> q;
public:
    bit_queue()
    {
        size = 0;
        front_pos = 1;
        back_pos = 0;
    }
    void push(const int& value)
    {
        //先检查back_pos若是已经到了int32或char8，说明尾部int的32位已经用完了，要新入队一个int或char
        if (0 == back_pos % (sizeof(T) * 8))
        {
            back_pos = 0;
            q.push(0);
        }
        size++;
        back_pos++;
        T& back = q.back(); //两种都可以取得最后一个char或int元素的引用，然后修改
        //T& back = q[q.size()-1];
        //将back中的第back_pos位修改为value值
        back = back | (value << (back_pos-1));
    }
    void pop()
    {
        //出队的时候要更新size，还要更新front_pos，若是当前等于1则要从实际队列中出一个元素
        if (sizeof(T) * 8 == front_pos)
        {
            q.pop();
            front_pos = 1;  //要记得将首位置置回1
            return;
        }
        //把要出的最后一个bit位置0
        //T& front = q[0];
        T& front = q.front();   //两种都可以取得第一个char或int元素的引用，然后修改
        front = front & (~(1 << (front_pos-1)));
        front_pos++;
        size--;
    }
    int getsize() const
    {
        return size;
    }
    bool empty() const
    {
        if (0 == size)
        {
            return true;
        }
        return false;
    }
    int front() //获取当前头部bit位
    {
        T& front = q.front();
        int bit = front>>(front_pos - 1);
        return bit&1;
    }
    int back()      //获取当前尾部bit位
    {
        T& back = q.back();
        int bit = back>>(back_pos - 1);
        return bit&1;
    }
};

int main()
{
    bit_queue<char> bit_q;
    bit_q.push(1);
    bit_q.push(1);
    bit_q.push(1);
    bit_q.push(1);
    bit_q.push(0);
    bit_q.push(1);
    bit_q.push(1);
    bit_q.push(1);
    //下面再用另一个char字符来存储
    bit_q.push(1);
    bit_q.push(0);
    bit_q.push(1);
    bit_q.push(0);

    int size = bit_q.getsize();
    cout << size << endl;
    for (int i = 0; i < size; i++)
    {
        cout << bit_q.front() << endl;
        bit_q.pop();
    }
    return 0;
}

运行结果