在文章《SystemVerilog的那些数组》中对SV中各类数组做了介绍和区分。除了数组，SV还提供了一种叫队列的复合数据结构。
 队列跟数组很像，都可以用来作为多个数据的容器，但同时又拥有自己的优势特性。本文将介绍队列的特性和使用方法，最后再总结SV中数组和队列在使用选择上的一些考虑因素。
 
01队列(Queue)
 

 
队列有哪些基本特性？跟数组又有哪些区别？
 
队列是可变长的、有序的、连续存放的同类数据集合。对队列中任意元素的访问，以及在队列头和尾进行元素增删操作几乎没有额外的时间开销，但是对队列中间的元素的增删操作就不一样了。
 
可以看出来，队列中的数据元素必须是相同数据类型的，这个特点跟所有数组都是一样的。而有序性，跟定长数组和动态数组是一样的；可变性，跟关联数组一样。
 
可变性，指的是队列允许在仿真中对元素进行增删操作，从而导致该数据结构的大小是可变的。但队列为了同时具备有序性，借鉴了链表（Linked list）数据结构的特点，它需要更多的指针来维系元素的先后关系。
 

 
链表跟队列又是什么关系？为什么不直接用链表？
 
队列中的数据元素是连续存放的，这也是它跟关联数组和链表的区别。在之前SV还是支持链表的，在IEEE 1800-2005及之前的SV标准中还能看到。
 
原来SV定义的链表结构是一个参数化类，类似于C++编程中的STL(standard template library)列表容器结构。链表的节点不是连续存放的，链表靠指针维系顺序，它可以是单向的或者双向的，即每一个节点除了数据本身，还带了两个指针分别指向上一个节点和下一个节点或者只有

 
使用线性数组可以很容易地表示队列。 在每个队列的情况下实现有两个变量，即前面(front)和后面(rear)。 前后变量指向队列中执行插入和删除的位置。 最初，front和queue的值为-1，表示空队列。 包含5个元素的队列的数组表示以及前后的值如下图所示。
 

 
上图显示了形成英文单词“HELLO”的字符队列。 因为，到目前为止在队列中没有执行删除报操作，因此font的值保持为0。 但是，每次在队列中执行插入时，rear的值都会增加1。 将元素插入上图所示的队列后，队列将如下所示。 rear的值将变为5，而font的值保持不变。
 

 
删除一个元素后，front的值将从0增加到1。当前，队列内容将类似于如下。
 

 
1. 在队列中插入元素的算法
 
通过将rear与max - 1进行比较来检查队列是否已满，如果是，则返回溢出错误。
 
如果要将数据项作为列表中的第一个元素插入，则在这种情况下将前后值设置为0并将元素插入后端。否则继续增加rear的值并逐个插入每个元素，使用rear作为索引。
 
算法
 
第1步：IF REAR = MAX - 1
 
写OVERFLOW
 
转到第4步
 
[IF结束]
 
第2步：IF FRONT = -1且REAR = -1
 
SET FRONT = REAR = 0
 
其他
 
SET REAR = REAR + 1
 
[IF结束]
 
第3步：设置QUEUE [REAR] = NUM
 
第4步：退出
 
使用C语言实现以下算法如下所示 -
 
void insert (int queue[], int max, int front, int rear, int item)
 
{
 
if (rear + 1 == max)
 
{
 
printf("overflow");
 
}
 
else
 
{
 
if(front == -1 && rear == -1)
 
{
 
front = 0;
 
rear = 0;
 
}
 
else
 
{
 
rear = rear + 1;
 
}
 
queue[rear]=item;
 
}
 
}
 
2. 从队列中删除元素的算法
 
如果front的值为-1或front的值大于rear，则提示下溢信息并退出。
 
否则，继续增加前后的值并每次返回存储在队列前端的数据项。
 
算法
 
第1步：IF FRONT = -1或FRONT> REAR
 
提示溢出
 
其他
 
SET VAL = QUEUE [FRONT]
 
SET FRONT = FRONT + 1
 
[IF结束]
 
第2步：退出
 
C语言实现算法，如下所示 -
 
int delete (int queue[], int max, int front, int rear)
 
{
 
int y;
 
if (front == -1 || front > rear)
 
{
 
printf("underflow");
 
}
 
else
 
{
 
y = queue[front];
 
if(front == rear)
 
{
 
front = rear = -1;
 
else
 
front = front + 1;
 
}
 
return y;
 
}
 
}
 
完整的代码实现如下所示 -
 
#include
 
#include
 
#define maxsize 5
 
void insert();
 
void delete();
 
void display();
 
int front = -1, rear = -1;
 
int queue[maxsize];
 
void main()
 
{
 
int choice;
 
while (choice != 4)
 
{
 
printf("*************************Main Menu*****************************\n");
 
printf("=================================================================\n");
 
printf("1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
 
printf("Enter your choice ?");
 
scanf("%d", &choice);
 
switch (choice)
 
{
 
case 1:
 
insert();
 
break;
 
case 2:
 
delete();
 
break;
 
case 3:
 
display();
 
break;
 
case 4:
 
exit(0);
 
break;
 
default:
 
printf("Enter valid choice??\n");
 
}
 
}
 
}
 
void insert()
 
{
 
int item;
 
printf("\nEnter the element\n");
 
scanf("\n%d", &item);
 
if (rear == maxsize - 1)
 
{
 
printf("OVERFLOW\n");
 
return;
 
}
 
if (front == -1 && rear == -1)
 
{
 
front = 0;
 
rear = 0;
 
}
 
else
 
{
 
rear = rear + 1;
 
}
 
queue[rear] = item;
 
printf("Value inserted ");
 
}
 
void delete()
 
{
 
int item;
 
if (front == -1 || front > rear)
 
{
 
printf("UNDERFLOW\n");
 
return;
 
}
 
else
 
{
 
item = queue[front];
 
if (front == rear)
 
{
 
front = -1;
 
rear = -1;
 
}
 
else
 
{
 
front = front + 1;
 
}
 
printf("value deleted ");
 
}
 
}
 
void display()
 
{
 
int i;
 
if (rear == -1)
 
{
 
printf("Empty queue\n");
 
}
 
else
 
{
 
printf("printing values .....\n");
 
for (i = front;i <= rear;i++)
 
{
 
printf("\n%d\n", queue[i]);
 
}
 
}
 
}
 
执行上面示例代码，得到以下结果 -
 
*************Main Menu**************
 
==============================================
 
1.insert an element
 
2.Delete an element
 
3.Display the queue
 
4.Exit
 
Enter your choice ?1
 
Enter the element
 
123
 
Value inserted
 
*************Main Menu**************
 
==============================================
 
1.insert an element
 
2.Delete an element
 
3.Display the queue
 
4.Exit
 
Enter your choice ?1
 
Enter the element
 
90
 
Value inserted
 
*************Main Menu**************
 
===================================
 
1.insert an element
 
2.Delete an element
 
3.Display the queue
 
4.Exit
 
Enter your choice ?2
 
value deleted
 
*************Main Menu**************
 
==============================================
 
1.insert an element
 
2.Delete an element
 
3.Display the queue
 
4.Exit
 
Enter your choice ?3
 
printing values .....
 
90
 
*************Main Menu**************
 
==============================================
 
1.insert an element
 
2.Delete an element
 
3.Display the queue
 
4.Exit
 
Enter your choice ?4
 
3. 数组实现的缺点
 
虽然，创建队列很容易，但是使用这种技术来实现队列存在一些缺点。
 
内存浪费：数组的空间(用于存储队列元素)永远不能被重用来存储该队列的元素，因为元素只能插入前端而前面的值可能很高，所以， 在此之前的所有空间，永远不会被填补。
 

 
上图显示了如何在队列的数组表示中浪费内存空间。 在上图中，示出了具有3个元素的大小为10的队列。 front变量的值为5，因此，不能将值重新插入front位置之前已删除元素的位置。 数组的那么多空间被浪费了，以后不能使用(对于这个队列)。
 
确定数组大小
 
关于数组实现的最常见问题是需要事先声明的数组的大小。 由于队列可以在运行时根据问题进行扩展，因此数组大小的扩展是一个耗时的过程，并且由于发生了大量的重新分配，因此几乎不可能在运行时执行。 由于这个原因，要声明数组足够大，以便可以尽可能地存储队列元素，但这个声明的主要问题是，大多数数组插槽(接近一半)永远不能被重用。 它将再次导致内存浪费。
 
¥ 我要打赏
 
纠错/补充
 
收藏
 
加QQ群啦，易百教程官方技术学习群
 
注意：建议每个人选自己的技术方向加群，同一个QQ最多限加 3 个群。

       我们都知道，队列是一种先进先出的数据结构，每当有人问你队列是什么，你的回答就是 "一种先进先出的数据结构",当然这样的回答也是完全没有错的，它就是一种先进先出的数据结构，为什么我们不能描述的多一点呢？更详细一点？下面我们就来详细的描述一下队列。
 
       队列是我们学习数据结构的一种重要的结构，它能帮我们帮我们解决生活中的一些问题，例如到银行办理业务，当人多的时候就需要取号排队，这就是队列的一种应用。队列的实现可以有两种方式来实现，一是用数组，二是链表，在这里我们就来说一下数组实现的方式，链表的实现方式我会在后续的更新中发出来。
 
     下面我会先用图文的方式来描述队列到底是一个什么东西，以及它是怎么先进先出的，然后会说明一下怎么用代码去自己实现。
 
    我们都知道队列是一种先进先出的数据结构，怎么个先进先出法？
 
    首先，我们拥有一个数组,数组应当有这三个属性，头指针，尾指针，和长度。头指针应当指向队列的头一个元素，当从队列里面取出一个元素后，应当将它向后移一个位置，尾指针当有一个元素进来后也向后移一个位置。
 
首先一个初始的队列应该是这样的：
 
队头指针和队尾指针都在第一个位置，也表示这是一个空队列。
 
 
这时假如我们入队一个元素 1：
 
 
这时队列的头指针不变，队尾向后移动一次。
 
再入队一个元素 2：
 
 
这时候出队一个元素：
 
这时候对头指针向后移动，队尾指针不变。
 
 
以上就是队列的基本操作，入队出队的具体过程，你理解了嘛？
 
其实基本操作看起来比较简单，但是利用代码来完成这个过程还是有一定难度的。
 
我们在用代码实现的时候还要考虑许多问题，比如说我们怎么判断队列是空的还是满的，队列中有几个元素，还有就是当队尾指针到达数组的尾部之后怎么走？
 
这些问题都是我们需要考虑的。
 
下面我就展示一下代码：
 
定义我们需要的四个属性
 
    private int maxSize; //数组长度
    private int front;  //对头指针
    private int real;   //队尾指针
    private int[] arr;  //数组
    //初始化  构造器
    public myQueue(int maxSize){
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }
 
判断队列是否满了：当队尾指针加一等于队头指针就队满了。
 
这里我们需要考虑到的因素是当队尾指针比队头指针小的情况。
 
 public boolean isFull(){
        return (real+1)%maxSize == front;  //最后一个位置没用到
    }
 
判断队列是否为空：
 
public boolean isEmpty(){
        return front == real;
    }
 
添加元素：
 
尾指针不能光顾着加啊，还要考虑到到达尾部之后要走到数组的前面去啊。
 
public void Add(int n){
        if(isFull()){
            System.out.println("队满");
            return;
        }
        arr[real] = n;
        real = (real+1)%maxSize;
    }
 
出队：
 
public int OutQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空!");
        }
        int temp = arr[front];
        front = (front+1)%maxSize;
        return temp;
    }
 
查看队头元素：
 
//查看队列的第一个元素
    public int HeadNum(){
        if(isEmpty()){
            throw new RuntimeException("队列为空!");
        }
        return arr[front];
    }
 
查看队列中有效元素的个数：
 
  public int CountQueue(){
        if(isEmpty()){
            return 0;
        }
        return (real+maxSize-front)%maxSize;
    }
 
显示队列所有元素：
 
 //显示队列的所有数据
    public void ShowQueue(){
        if(isEmpty()){
            System.out.println("队列中没有数据");
            return;
        }
        for(int i = front;i < front+CountQueue();i++){
            System.out.println(arr[i%maxSize]);
        }
    }
 
本文中有几个需要注意的公式，就是判断队列是否满了：
 
(real+1)%maxSize == front
 
还要就是队尾指针和队头指针移动的操作：
 
real = (real+1)%maxSize;
 
查看队列中有效元素的个数：
 
(real+maxSize-front)%maxSize
 
还有就是遍历队列：
 
for(int i = front;i < front+CountQueue();i++){
    System.out.println(arr[i%maxSize]);
}
 
这些都是需要仔细想一下的地方，还请花点时间理解一下！

 
一、背景
 
上篇文章《c语言数据结构实现-数组队列/环形队列》讲述了数组队列的原理与实现，本文编写一个双线程进行速度测试
 
二、相关知识
 
多线程编程接口:
 
1) 创建线程 pthread_create 函数
 
SYNOPSIS
 
#include int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
 
void *(*start_routine) (void *), void *arg);
 
Compile and link with -pthread.
 
DESCRIPTION:
 
The pthread_create() function starts a new thread in the calling process.  The new thread starts execution by invoking start_routine(); arg is passed as the sole argument of start_routine().
 
RETURN VALUE:
 
On success, pthread_create() returns 0; on error, it returns an error number, and the contents of *thread are undefined.
 
2) 设置线程属性 pthread_attr_setdetachstate
 
SYNOPSIS
 
#include int pthread_attr_setdetachstate(pthread_attr_t *attr, int detachstate);
 
Compile and link with -pthread.
 
DESCRIPTION
 
The pthread_attr_setdetachstate() function sets the detach state attribute of the thread attributes object referred to by attr to the value specified in detachstate. The detach state attribute determines whether a thread created using the thread attributes object attr will be created in a joinable or a detached state.
 
RETURN VALUE
 
On success, these functions return 0; on error, they return a nonzero error number.
 
3) 线程锁 pthread_mutex_init、pthread_mutex_lock、pthread_mutex_unlock、pthread_mutex_destory
 
线程锁是用于多线程直接的同步，用来保护临界资源(数值队列)，同样类似的功能有 Posix 的 sem信号量。
 
4) 条件变量 pthread_cond_init、pthread_cond_signal、pthread_cond_wait、pthread_cond_destroy
 
条件变量是同步线程的一种机制，它允许线程挂起，让出处理器等待其他线程向它发送信号，该线程收到该信号后被唤醒继续执行程序。
 
三、实现
 
数据结构 test_t 为用户数据，instance_t 为程序上下文
 
typedef struct item_t
 
{
 
int value;
 
} test_t;
 
typedef struct instance
 
{
 
sem_t sem_mutex;
 
pthread_mutex_t thd_mutex;
 
pthread_cond_t thd_cond;
 
bufqueue_t queue;
 
} instance_t;
 
主线程创建子线程，并生产数据进行入列操作，顺序地生产 times 个 pitem 数据进行入列，生产完成后等待子线程消费
 
线程的工作方式分别有三种：线程完全异步的机制、使用sem保证实时线程同步、使用条件变量保持同步
 
int test_mutilthread(int times)
 
{
 
int ret = FAILURE;
 
int ix = 0;
 
pthread_t tid = 0;
 
pthread_attr_t attr;
 
instance_t inst = {.queue = {0}};
 
test_t *pitem = NULL;
 
#ifdef TEST_SEM
 
printf("Sem sem_mutex mode\n");
 
assert(SUCCESS == ( ret = sem_init(&inst.sem_mutex, 0, 0) ));
 
#elif defined(TEST_COND)
 
printf("Pthread Cond mode\n");
 
assert(SUCCESS == ( ret = pthread_mutex_init(&inst.thd_mutex, NULL) ));
 
assert(SUCCESS == ( ret = pthread_cond_init(&inst.thd_cond, NULL) ));
 
#endif
 
assert(SUCCESS == ( ret = bufqueue_create(&inst.queue, times, sizeof(test_t)) ));
 
assert(SUCCESS == ( ret = pthread_attr_init(&attr) ));
 
assert(SUCCESS == ( ret = pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED) ));
 
assert(SUCCESS == ( ret = pthread_create(&tid, NULL, __do_customer, &inst) ));
 
/* Producer */
 
for ( ix = 1; ix < times; ix++ ) {
 
assert(NULL != ( pitem = (test_t*)bufqueue_tail(&inst.queue) ));
 
/* Set custom item */
 
pitem->value = ix;
 
assert(SUCCESS == ( ret = bufqueue_push(&inst.queue) ));
 
printf("Enqueue %u/%u\n", pitem->value, ix);
 
#ifdef TEST_SEM
 
sem_post(&inst.sem_mutex);
 
#elif defined(TEST_COND)
 
pthread_cond_signal(&inst.thd_cond);
 
#endif
 
}
 
while ( !bufqueue_isempty(&inst.queue) ) {
 
printf("Wait dequeue...\n");
 
usleep(300);
 
}
 
ret = SUCCESS;
 
_E1:
 
pthread_attr_destroy(&attr);
 
bufqueue_destroy(&inst.queue, free);
 
#ifdef TEST_SEM
 
sem_destroy(&inst.sem_mutex);
 
#elif defined(TEST_COND)
 
pthread_cond_destroy(&inst.thd_cond);
 
pthread_mutex_destroy(&inst.thd_mutex);
 
#endif
 
return ret;
 
}
 
子线程负责取队列中的数据，取成功 times 次后就退出
 
线程的工作方式分别也有三种：线程完全异步的机制、使用sem保证实时线程同步、使用条件变量保持同步
 
static void *__do_customer(void *args)
 
{
 
instance_t *pinst = (instance_t *)args;
 
test_t *pitem = NULL;
 
u32 cnt = 1;
 
u32 max = 0;
 
ASSERT_FAIL(NULL, args);
 
for ( max = pinst->queue.size; cnt < max; ) {
 
#ifdef TEST_SEM
 
sem_wait(&pinst->sem_mutex);
 
#elif defined(TEST_COND)
 
if ( bufqueue_isempty(&pinst->queue) ) {
 
pthread_mutex_lock(&pinst->thd_mutex);
 
pthread_cond_wait(&pinst->thd_cond, &pinst->thd_mutex);
 
pthread_mutex_unlock(&pinst->thd_mutex);
 
printf("Wait enqueue...\n");
 
continue;
 
}
 
#else
 
if ( bufqueue_isempty(&pinst->queue) ) {
 
usleep(300);
 
printf("Wait enqueue...\n");
 
continue;
 
}
 
#endif
 
assert(NULL != (pitem = (test_t*)bufqueue_pop(&pinst->queue) ));
 
assert(cnt++ == pitem->value);
 
printf("Dequeue %u/%u\n", pitem->value, cnt);
 
}
 
printf("Dequeue Done\n");
 
_E1:
 
return NULL;
 
}
 
main函数
 
int main(int argc, char *argv[])
 
{
 
int ret = FAILURE;
 
u32 times = 1024;
 
if ( argc > 1 ) {
 
times = atoi(argv[1]);
 
}
 
ret = test_mutilthread(times)
 
printf("Test result:\t\t\t\t[%s]\n", ret ? "FAILURE" : "SUCCESS");
 
exit(ret ? 1 : 0);
 
}
 
注意以上写法为原型断言的写法，保证断言失败时程序立刻退出，仅为测试使用，不符合实际的代码规范
 
四、总结分析
 
测试硬件为Intel(R) Core(TM) i7-4500U CPU @ 1.80GHz
 
样本大小：100'000个
 
主线程得知队列空的情况后，加入一个时间统计的功能，分别得出一秒钟操作的速度：
 
线程完全异步：20000'000 次/每秒
 
使用sem保证实时线程同步：1960'000 次/每秒
 
使用条件变量保持同步：9000'000 次/每秒
 
数组队列在三种工作方式下均能成功执行，速度上为无锁的情况为最快，CPU占用也是最大(usleep轮询)
 
综合结果考虑来说使用条件变量正好可以避免 子线程过多地占用CPU进行轮询操作，速度也仅为无锁的一半
 
参考文章：
 
[1] Linux C++的多线程编程, http://www.cnblogs.com/youtherhome/archive/2013/03/17/2964195.html
 
[2] 多线程编程-互斥锁 http://blog.chinaunix.net/uid-21411227-id-1826888.html