写一个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;
}
运行结果
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 这一部分讲了W先生和J小姐各种秘密约会的艰难,两人的关系更加密切,互相吐露心声,W先生回忆了和前妻的痛苦时光,J...
    Celia欢阅读 2,953评论 0 0
  • 骚风今年35,男人35一枝花,入IT行13年。 最近特流行一标语:“just do it”,就是做IT 做了13年...
    许多许多许多多阅读 2,656评论 1 1
  • 可能,家乡依旧是家乡吧。
    小驴很开心阅读 1,098评论 0 0
  • 昨天又和母亲闹了点别扭,因为教育孩子的事。俗话说隔辈亲,这在我父母那里更加明显。母亲现在越来越像小孩...
    明睿心理佟顶阅读 2,454评论 0 0