队列和循环队列

问题

在分析ffplay源码时，他有两个重要的结构体PacketQueue和FrameQueue，前者是一个用链表实现的队列(队列还可以用数组以及栈等来实现)，后者是一个循环队列。所以必须得搞懂他的实现我们才能看懂ffplay的源码，下面我把java和c实现的方式都写出来。

链表实现队列

JAVA实现

先需要一个节点类Node

/**
 * 实现度列的node
 */
public class Node {
    int data;
    Node next;


    public Node(int data) {
        this.data = data;
    }
}

再来Queue

/**
 * 队列 用链表实现
 */
public class Queue {

    Node first;
    Node last;
    /**
     * 添加数据  添加到后面
     */
    public void add(int data){
        Node node = new Node(data);
        if(first==null){
            first=node;
            last=node;
        }else {
            //赋值到尾节点  然后尾节点往后移动
            last.next=node;
            last=node;
        }
    }
    /**
     * 取数据  从前面取数据 取出first 然后把first赋值给别人
     */
    public int  offer(){
      if(first==null){
          return 0;
      }else {
          return getNode().data;
      }
    }


    private Node getNode(){
        Node temp=first;
        first=first.next;
        return temp;
    }

}

其实原理很简单，大家看看就好。

C实现

c里面跟类对应的就是结构体，所以咱们需要一个Node和一个Queue结构体

typedef struct Node {
    struct Node *next;
    int data;

} Node;

typedef struct Queue {
    Node *first, *last;
};

然后就是写入和读取的方法了，思想和java的思想一模一样，就是java里面可以new直接有对象,C需要malloc

/**
 * 初始化queue
 * @return
 */
Queue *initQueue() {
    Queue *q = static_cast<Queue *>(malloc(sizeof(Queue)));
    return q;
}

/**
 * 添加数据
 * @param data
 */
void add(Queue *q, int data) {
    //node分配内存 把data 赋值进去 其实就是 java的new 构造函数的过程
    Node *node;
    node = static_cast<Node *>(malloc(sizeof(Node)));
    node->data = data;
    //有了node 节点后就要把它加到队列里面去了
    if (!q->first) {
        //如果头结点是null
        q->first = node;
        q->last = node;
    } else {
        //如果不是null就要拼接到后面
        q->last->next = node;
        q->last = node;
    }
}

/**
 * 获取数据
 */
int offer(Queue *q) {
    if (!q->first) {
        return -1;
    } else {
        int data = q->first->data;
        q->first = q->first->next;
        return data;
    }
}

关于链表实现其实还是比较简单的，了解了C 如何实现队列的功能后我们就可以搞明白PacketQueue的源码实现了，其实就是我们上面C代码。那关于FrameQueue他并没有采用这种实现方式，而是采用了一种循环队列的方式，相对来说会复杂一点，我们来看下java和c的实现。

循环队列

Java实现

一个CircleQueue就可以实现

/**
 * 循环队列的实现
 * <p>
 * 循环队列的特点是 得预分配他里面数组的大小  然后有一个头指针 和一个尾指针  通过取模来实现循环
 *
 */
public class CircleQueue {
    private int maxSize;
    int first;
    int last;
    Object[] data;
    int size;
    //初始化的时候就需要给到队列最大的size
    public CircleQueue(int maxSize) {
        this.maxSize = maxSize;
        data = new Object[maxSize];
    }
    //如果开始的时候first 和last相等 就是空
    public boolean isEmpty() {
        return first == last;
    }
    ///这里+1 是为了区分 empty 和full   如果不+1 那么empty了full没法区分
    //所以这里有一点是， 其实last 一直指向的是添加数据的后面一个  这里+1就会浪费一个地方不能被插入数据
    public boolean isFull() {
        return (last + 1) % maxSize == first;
    }


    public void add(Object object) {
        if (isFull()) {
            //如果满了 就直接返回
            //fixme 关于扩容
            Log.i(TAG, "add: 满了");
            return;
        }
        //给最后一个元素赋值
        data[last] = object;
        //last++  取模 这样的话就可以循环
        last = (last + 1) % maxSize;
        size++;
    }

    /**
     * 取出数据
     */
    public Object offer() {
        //如果是空  就返回NULL
        if (isEmpty()) {
            return null;
        }
        //取出first的数据 然后first往后移动
        Object o = data[first];
        data[first]=null;
        first = (first + 1) % maxSize;
        size--;
        return o;
    }

    public Object[] getData(){
        return data;
    }
}

如果不能理解代码的话看下这篇文章，图画的很容易理解，
https://juejin.im/post/6844903805264347149

C实现

上来还是需要定义两个结构体

#define MAX_SIZE 5

int size;
//这个是数据
typedef struct Object {
    int i;
}Object;


typedef struct CircleQueue {
    //定义队列的长度
    Object q[MAX_SIZE];
    int first;
    int last;

}CirCleQueue;

然后就是具体的实现函数

/**
 * 是否队列满了
 * @param q
 * @return
 */
bool isFull(CircleQueue *q) {
    return (q->last + 1) % MAX_SIZE==q->first;
}

bool isEmpty(CircleQueue *q) {
    LOGE(" isempty --------------%d %d",q->first,q->last);
    return q->last == q->first;
}

void enqueue(CircleQueue *c, int  data) {
    //object 分配内存
    Object *object;
    object= static_cast<Object *>(malloc(sizeof(Object)));
    object->i=data;
    if (isFull(c)) {
        LOGE("------------full---------");;
        return;
    }
    //last 的赋值
    c->q[c->last] = *object;
    //last后移
    c->last = (c->last + 1) % MAX_SIZE;
    LOGE(" last and first %d %d ",c->last,c->first);
    size++;
}



void dequeue(CircleQueue *c) {
    if (isEmpty(c)) {
        LOGE("----------------EMPTY");
    } else{
        //把fist 拿出去
        Object o = c->q[c->first];
        //删除first占用的内存
        free(&c->q[c->first]);
        //first往后移动
        c->first = (c->first + 1) % MAX_SIZE;
    }

}

这里面其实需要理解的就是如何判断满了 和空了，上面在java部分分享的链接如果仔细看很容易理解，我这里也就不赘言了。

总结

这里主要是介绍了队列和循环队列的java和c实现，java代码可能封装的比较好，大部分的数据结构都有java的集合类实现了，感觉在阅读java的一些源代码的时候遇到更多的是设计模式。但是在C里面，刚刚开始阅读ffplay就遇到了关于队列和循环队列的数据结构，所以这里就带着java一起复习下，在NDK的学习路上，如果再遇到其他数据结构还会拿出来跟大家一起重温，学习，因为数据结构是我们最基础的东西。具体ffplay这里为什么FrameQueue使用了循环队列我们就去ffplay源码部分窥探了。题外话：ffplay的源码正在研究进行中，研究透了ffplay的源码准备自己搞个开源的播放器，加油！