队列性能明智,这是更好的实现 – 数组或链接列表

当我必须插入很少的元素时,哪种方式可以更快地排队和出列,是否数组比链表更好？

我需要插入一些元素,我必须从队列中删除并读取已删除的元素.
如果是数组,我可能每次删除元素时都要修改索引.插入和删除也可能同时发生.

从下面的案例中哪个更好？

typedef struct{
    mylist list;
    struct mylistQ *next;
}mylistQ;

数组代码

static mylist myListQ[QUEUESIZE+1];
int qLast = 0;

void enqueue_element(mylist qItem)
{
        myListQ[qLast] = qItem;
    qLast++;
}

mylist dequeue_element()
{
 retryq:
   if(qLast >0) {
    mylist qReturn = myListQ[0];  
    int i;
    for (i = 0; i < qLast - 1; i++){
        myListQ[i] = myListQ[i + 1];
    }
    qLast--; 
    return qReturn;
     }
   else {
    goto retryq;
    }
}

链接列表

int qLast = 0;

mylistQ *headElement = NULL;   
mylistQ *tailElement = NULL;     

void enqueue_element(mylist *List)
{
    mylistQ *newnode;      
    newnode=(mylistQ*)av_malloc(sizeof(mylistQ));
    newnode->next=NULL;
    newnode->list=*List;
    qLast++;
    if(headElement==NULL && tailElement==NULL)
    {
        headElement=newnode;
        tailElement=newnode;
    }
    else
    {
        tailElement->next=newnode;
        tailElement=newnode;
    }
 }

mylist dequeue_element()
{
    mylistQ *delnode;      /* Node to be deleted */
    mylist Dellist;
    if(headElement==NULL && tailElement==NULL){
        LOg( "Queue is empty to delete any element");
        }
    else
    {
       Log("In dequeue_picture queue is not empty");
        delnode=headElement;
        headElement=headElement->next;
    if (!headElement){
        tailElement=NULL;
    }
        Dellist = delnode->list;
        av_free(delnode);
    qLast--;
    }
        return Dellist;
}

这取决于您将执行的操作数量以及阵列版本的实现方式.

如果你做的操作相对较少,即总共少于1000次排队/出队,那么数组会更快,因为它在内存中是连续的.保持指向前方的指针和指向后方的指针,始终在后面添加并在前面出列.

另一方面,即使列表不超过30左右,如果必须持续很长一段时间,您将不会有任何数组调整大小问题,这是数组的潜在问题.

链接列表保证了出色的性能,您必须注意调整大小.

编辑：
正如@Hans Passant所提到的,数组很快,因为它们具有CPU缓存局部性.只要您的阵列很小,您的硬件就会优化性能,以便与存储阵列相关的内存将保留在L2中.可能在登记册中的指数.这真的很快.从你不需要很多元素的事实来看,在这种情况下,数组是理想的.是的,你必须在移动元素时修改索引,但这实际上是一个非常快速的操作,因为如果你用优化构建代码,索引将存储在注册商中.

这里有一个问题,你提到你可能不得不同时进行入队和出队,这是否意味着它是并行的,即多个线程访问内存？如果是这种情况,阵列仍然会更快,但你会看到性能下降800倍.为什么？因为处理器不再能够缓冲与芯片上的队列相关联的存储器,但它必须存储在主存储器中.此外,您还存在在线程之间创建竞争条件的风险.想象一下,如果一个线程试图出列而另一个线程试图入队,并且列表中只有一个元素,那么你可能会遇到灾难.无论哪种方式,如果这个应用程序是非常性能驱动的,请确保编译(假设gcc)与NDEBUG和-O3标志.

第二编辑：
查看代码,并查看下面的其他答案,我建议使您的数组代码更有效并将其转换为循环数组,因为它听起来像是有元素数量的上限.作为旁注,你当前的数组实现是非常低效的,每次你删除你复制前面的队列的其余部分,这是没有意义的,只是增加一个指向“第一”索引的int指针.

伪代码：

int ciruclarArray[SIZE];
int front = 0;
int back = 0;

void enqueue(int elem)
{
    circularArray[back] = elem;
    if(back < (circularArray.length - 1))
        back++;
    else
        back = 0;
    return elem;
}

int dequeue()
{
    int toReturn = circularArray[front];
    //do same check for incrementing as enqueue
    return toReturn;
}

只是不要忘记对正常的东西进行错误检查.