C++循环队列与FFmpeg队列

喜欢ヅ旅行 2022-06-02 03:28 213阅读 0赞

# 目录 #

*  目录
 *  前言
 *  循环队列
    
     *  考虑细节总结
     *  代码实现
 *  FFmpeg队列
    
     *  为什么要使用队列
     *  实现方式
     *  考虑细节总结
     *  代码
 *  总结
 *  链接地址

# 前言 #

# 循环队列 #

如果用数组实现队列，因为队列的先入先出特性。如果不使用循环队列，那么队列中删除队头剩下的空间将不会被使用。也就导致数组队列使用的不便性。所以，如果用数组实现队列，最好的方法就是循环队列。这样可以循环利用有限而固定的数组空间。

## 考虑细节总结 ##

*  如何实现一个循环队列，我们需要考虑些什么？  
    
    
    1.  如何判断的队列为空  
        在循环队列中，如果头指针和尾指针指向同一块内存，表示队列为空。
    2.  如何判断队列为满  
        判断队列为满，就要知道循环队列在满队时的性质：首先当队列为空我们知道队列的头指针和尾指针指向同一块内存，同时这块内存为空内存，也就是没有数据；所以可以知道当满队是队列的头指针和尾指针应该指向不同的内存地址。因为是循环队列，由下图可以显而易见的知道：  
        ![0][]

// m_front表示头指针下标
    // m_rear表示尾指针下标
    m_front=(m_rear+1)%m_size;

1.  如何存取数据  
    因为是数组实现循环队列，所以我们不需要取释放内存，只需要在队列使用完成后，统一释放内存或者由系统自动释放。存数据的过程先存数据，在移动尾指针(尾指针指向空内存)；取数据的过程先取数据，然后再移动头指针。

博主记：**头指针指向最先需要取出的数据，尾指针指向最新存在数据内存的下一个内存地址**

## 代码实现 ##

*  main.cpp

#include <iostream>
    #include "cycleQueue.cpp"
    
    using namespace std;
    
    int main()
    {
        cycleQueue<int> q(10);
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);
        for(int i=0; i<4; i++)
            cout << q.pop() << endl;
    
        return 0;
    }

*  cycleQueue.h

#ifndef CYCLEQUEUE_H_INCLUDED
    #define CYCLEQUEUE_H_INCLUDED
    
    #include <iostream>
    using namespace std;
    
    template <class T>
    class cycleQueue
    {
    public:
        cycleQueue();
        cycleQueue(unsigned int m_size);
        ~cycleQueue();
        bool isEmpty();
        bool isFull();
        T pop();
        bool push(T data);
    private:
        unsigned int m_size;
        int m_front;
        int m_rear;
        T* data;
    };
    
    #endif // CYCLEQUEUE_H_INCLUDED

*  cycleQueue.cpp

#include "cycleQueue.hpp"
    
    template <class T>
    cycleQueue<T>::cycleQueue()
    {
    
    }
    
    template <class T>
    cycleQueue<T>::cycleQueue(unsigned int m_size):m_size(m_size),m_front(0),m_rear(0)
    {
        data = new T[m_size];
    }
    
    template <class T>
    cycleQueue<T>::~cycleQueue()
    {
        delete [] data;
    }
    
    template <class T>
    bool cycleQueue<T>::isEmpty()
    {
        return m_front == m_rear;           // if equal, return true; otherwise, return false;
    }
    
    template <class T>
    bool cycleQueue<T>::isFull()
    {
        return m_front == (m_rear+1)%m_size;  // only size-1 include valid data
    }
    
    template <class T>
    bool cycleQueue<T>::push(T d)
    {
        if(isFull())
        {
            return false;
        }
    
        data[m_rear] = d;
        m_rear = (m_rear+1)%m_size;
    
        return true;
    }
    
    template <class T>
    T cycleQueue<T>::pop()
    {
        if(isEmpty())
        {
            return false;
        }
        T d = data[m_front];
        m_front = (m_front+1)%m_size;
    
        return d;
    }

# FFmpeg队列 #

## 为什么要使用队列？ ##

因为在读取视频的时候，在视频比较大的时候(比如2G)，如果使用while(1)\{\}连续不断的读取视频时，就会占用2G的内存，所以会造成系统假死等状态。

## 实现方式 ##

我们要实现的是视频从一端读入(**头取**)，从另一端读出(**尾插**)，这种使用队列是最好不过了。队列可以实现成**链表形式**，也可以实现成**数组形式**。数组形式内存固定，不宜扩展，一般形成循环队列。而另外一种方式，使用链表，可以灵活的增加和减少元素，同时对内存能够进行有效的利用，所以FFmpeg中使用了链表形式的队列。博主刚开始就是使用循环队列，但是接触到链表队列之后，感觉更靠谱一些！

## 考虑细节总结 ##

*  如何实现一个链表队列，我们要考虑些什么？  
    
    
    1.  指向链表头的指针和指向链表尾的指针  
        如何描述一个队列，使用两个指针分别指向第一个元素和最后一个元素的地址即可。其中第一个元素中含有指向下一个元素的指针，最后一个元素的指针指向NULL。
    2.  链表指针指向的元素中，有**指向下一个元素的指针**和**元素数据**两部分
    3.  取链表数据的速度快于存链表数据的速度时的**同步问题**  
        如果取链表元素的数据比存元素数据的数据快，那么某个时刻将没有元素数据可取，这时候取不到链表数据，也就是取链表数据的函数应该进入阻塞状态，知道存链表数据的函数有数据的时候通知取链表数据的函数继续工作。
    4.  取链表数据和存链表数据的**互斥问题**  
        也就是存链表数据和取链表数据不能同时进行。
    5.  存取链表数据的链表头指针和尾**指针指向问题**，以及**内存释放问题**
    6.  当**链表数据不为空**和**链表数据为空**时的存取数据问题  
        如何判断链表数据为空？当头尾指针指向NULL的时候，队列为空。

## 代码 ##

*  PacketQueue.h

#ifndef PACKETQUEUE_H
    #define PACKETQUEUE_H
    
    #include <QDebug>
    
    typedef struct PacketQueue
    {
        AVPacketList *first_pkt, *last_pkt;
        int nb_packets;
        int size;
        SDL_mutex *mutex;
        SDL_cond *cond;
    }PacketQueue_t;
    
    void packet_queue_init(PacketQueue *q);
    int packet_queue_put(PacketQueue *q, AVPacket *pkt);
    int packet_queue_get(PacketQueue *q, AVPacket *pkt, int block);
    
    #endif // PACKETQUEUE_H

*  PacketQueue.cpp

#include "packetqueue.h"
    
    void packet_queue_init(PacketQueue *q)
    {
        memset(q, 0, sizeof(PacketQueue));
        q->mutex = SDL_CreateMutex();
        q->cond  = SDL_CreateCond();
        q->size  = 0;
        q->nb_packets = 0;
        q->first_pkt  = NULL;
        q->last_pkt   = NULL;
    }
    
    int packet_queue_put(PacketQueue *q, AVPacket *pkt)
    {
        AVPacketList *pkt1;
    
        if (av_dup_packet(pkt) < 0) // copy from pkt
        {
            return -1;
        }
    
        pkt1 = (AVPacketList*)av_malloc(sizeof(AVPacketList));
        if (!pkt1)
        {
            return -1;
        }
    
        pkt1->pkt = *pkt;
        pkt1->next = NULL;
    
        SDL_LockMutex(q->mutex);
    
        if (!q->last_pkt)
            q->first_pkt = pkt1;
        else
            q->last_pkt->next = pkt1;
    
        q->last_pkt = pkt1;
        q->nb_packets++;
        q->size += pkt1->pkt.size;
        SDL_CondSignal(q->cond);
    
        SDL_UnlockMutex(q->mutex);
    
        return 0;
    }
    
    int packet_queue_get(PacketQueue *q, AVPacket *pkt, int block)
    {
        AVPacketList *pkt1;
        int ret;
    
        SDL_LockMutex(q->mutex);
    
        for (;;)
        {
            pkt1 = q->first_pkt;
            if (pkt1)
            {
                q->first_pkt = pkt1->next;
                if (!q->first_pkt)
                    q->last_pkt = NULL;
                q->nb_packets--;
                q->size -= pkt1->pkt.size;
                *pkt = pkt1->pkt;
                av_free(pkt1);
                ret = 1;
                break;
            }
            else if (!block)
            {
                ret = 0;
                break;
            }
            else
            {
                SDL_CondWait(q->cond, q->mutex);
            }
        }
    
    // qDebug() << "packet_queue_get";
    
        SDL_UnlockMutex(q->mutex);
        return ret;
    }

*  \-

# 总结 #

博主认为能快速学到知识的两种方式分别是：  
1. 找一个NB的老师的视频，如果幸运可以面搜的话，提高很快！  
2. 找到相关的可以运行的代码，根据运行结果，慢慢理解！  
总之，博主认为，初级的学习阶段，自己看书是效率最低的时候，最好就是先跟别人学！跟代码学！站在巨人的肩膀上，才能走得更远！

# 链接地址 #

[循环队列实现(C++) Ring Buffer][C_ Ring Buffer]

[0]: /images/20220602/120b60d612654a71ada472dad4e7751d.png
[C_ Ring Buffer]: https://www.cnblogs.com/diegodu/p/4619104.html