C++.用头文件定义链队列的数据类型LinkQueue,包括入队,出队,取对头元素等基本 *** 作.

#include<iostream>

typedef char QElemType;

typedef struct QNode{ //队列结点

QElemType data;

struct QNode next;

}QNode,QueuePtr;

typedef struct{

QueuePtr front,rear;

}LinkQueue;

void InitQueue(LinkQueue &Q){ //创建一个带头结点的空队列

Qfront=new QNode;

if (!Qfront) exit(0);

Qrear=Qfront;

Qfront->next=NULL;

}

void DestroyQueue(LinkQueue &Q){ //销毁队列

while(Qfront){

Qrear=Qfront->next;

delete Qfront;

Qfront=Qrear=NULL;

}

}

void EnQueue(LinkQueue &Q,QElemType e){ //入队

QueuePtr p;

p=new QNode;

if (!p) exit(0);

p->data=e;

p->next=NULL;

if(Qfront==Qrear) Qfront->next=p;

Qrear->next=p;

Qrear=p;

}

void DeQueue(LinkQueue &Q,QElemType &e){ //出队

QueuePtr p;

if (Qfront==Qrear) return; //如果是空队列则返回

p=Qfront->next;

e=p->data; //将队头的值保存在e中

Qfront->next=p->next;

if (Qrear==p) Qrear=Qfront; //如果要删除的是队列中最后一个元素

delete p;

}

void GetFront(LinkQueue Q,QElemType &e)

{

if(Qfront==Qrear)return;

e=Qfront->next->data;

}

阻塞队列与普通队列的区别在于，当队列是空的时，从队列中获取元素的 *** 作将会被阻塞，或者当队列是满时，往队列里添加元素的 *** 作会被阻塞。试图从空的阻塞队列中获取元素的线程将会被阻塞，直到其他的线程往空的队列插入新的元素。同样，试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞，直到其他的线程使队列重新变得空闲起来，如从队列中移除一个或者多个元素，或者完全清空队列

从50开始，JDK在javautilconcurrent包里提供了阻塞队列的官方实现。尽管JDK中已经包含了阻塞队列的官方实现，但是熟悉其背后的原理还是很有帮助的。一下是阻塞队列的实现:

public class BlockingQueue {

private List queue = new LinkedList();

private int limit = 10;

public BlockingQueue(int limit){

thislimit = limit;

}

public synchronized void enqueue(Object item)

throws InterruptedException {

while(thisqueuesize() == thislimit) {

wait();

}

if(thisqueuesize() == 0) {

notifyAll();

}

thisqueueadd(item);

}

public synchronized Object dequeue()

throws InterruptedException{

while(thisqueuesize() == 0){

wait();

}

if(thisqueuesize() == thislimit){

notifyAll();

}

return thisqueueremove(0);

}

}

分析:

queue:队列

特性:只能访问首尾元素

访问接口:push，pop，front，back，queue(复制构造函数)，size，empty

结论:

只能访问首尾元素(访问方式看接口)，中间元素无法访问

如果要访问中间元素，请用其他容器，

vector、list等都可以

链队列的实现/

#include <iostream>

using namespace std;

/链队列类型定义/

typedef struct QNode

{

struct QNode next;

char data;

}QNode,queuePtr;//结点的定义

typedef struct linkQueue

{

queuePtr rear;

queuePtr front;

}linkQueue;//队列的定义

/链队列的初始化/

void initQueue_L(linkQueue &Q)

{

Qfront=Qrear=new QNode;//为队列申请一个空间

Qfront->next=0;//使队列的头指针指向空

}

/销毁链队列/

void destroyQueue_L(linkQueue &Q)

{

while(Qfront)

{

queuePtr p;

p=Qfront;

Qfront=Qfront->next;

delete p;//销毁链队列得把结点一个一个销毁掉

}

}

/入队/

void enterQueue_L(linkQueue &Q,char x)

{

QNode p;

p=new QNode;

p->data=x;

p->next=0;

Qrear->next=p;/这里和顺序队列不一样，此处的rear不是指向队列最后一个元素的下一个位置，而就是指向队列的最后一个元素。要知道Qrear和Qfront都是指针。/

Qrear=p;

}//这里没有队满的情况。

/出队/

char outputQueue_L(linkQueue &Q)

{

char x;

if(Qfront->next==0)//这里得考虑队列空的情况。

cout<<"Queue Empty!"<<endl;

QNode p;

p=Qfront->next;/应该注意顺序队列和链队列的不同之处，链队列中rear指向最后一个元素，front指向头结点，即第一个结点的前一个结点。而在顺序队列中正好相反，rear指向队列中的最后一个元素的下一个位置，而front就是指向第一个结点。/

x=p->data;

Qfront->next=p->next;

if(Qrear==p)

Qrear=Qfront;

delete p;

return x;

}

char GetQueneHead(linkQueue Q)

{

return Qfront->data;

}

void main()

{

linkQueue Q;

initQueue_L(Q);

enterQueue_L(Q,'a');

enterQueue_L(Q,'b');

enterQueue_L(Q,'c');

enterQueue_L(Q,'d');

cout<<outputQueue_L(Q)<<endl;

cout<<outputQueue_L(Q)<<endl;

cout<<outputQueue_L(Q)<<endl;

cout<<outputQueue_L(Q)<<endl;

//cout<<outputQueue_L(Q)<<endl;

destroyQueue_L(Q);

}

对于循环队列，求队列含有多少个元素的算法如下：

typedef struct

{

int tail,head;

int a[Max];

}queue;

void enqueue(int key,queue&q)

{

qa[qtail]=key;

qtail=(qtail+1)%Max;

}

int dequeue(queue&q)

{

int key;

key=qa[qhead];

qhead=(qhead+1)%Max;

return key;

}

扩展资料：

计算循环队列的元素个数：(尾－头＋表长)%表长

队列头指针为来front，队列尾指针为rear，队列容量为M，则元素个数为|rear-front+M|%M,注意，这个自%是求余运算。

设f为队头，r为队尾，m为队长，a为元素个数，则1 f>r时，a=m+r-f; 2 f<=r时，a=r-f

java阻塞队列应用于生产者消费者模式、消息传递、并行任务执行和相关并发设计的大多数常见使用上下文。

BlockingQueue在Queue接口基础上提供了额外的两种类型的 *** 作，分别是获取元素时等待队列变为非空和添加元素时等待空间变为可用。

BlockingQueue新增 *** 作的四种形式：

插入 *** 作是指向队列中添加一个元素，至于元素存放的位置与具体队列的实现有关。移除 *** 作将会移除队列的头部元素，并将这个移除的元素作为返回值反馈给调用者。检查 *** 作是指返回队列的头元素给调用者，队列不对这个头元素进行删除处理。

抛出异常形式的 *** 作，在队列已满的情况下，调用add方法将会抛出IllegalStateException异常。如果调用remove方法时，队列已经为空，则抛出一个NoSuchElementException异常。（实际上，remove方法还可以附带一个参数，用来删除队列中的指定元素，如果这个元素不存在，也会抛出NoSuchElementException异常）。如果调用element检查头元素，队列为空时，将会抛出NoSuchElementException异常。

特殊值 *** 作与抛出异常不同，在出错的时候，返回一个空指针，而不会抛出异常。

阻塞形式的 *** 作，调用put方法时，如果队列已满，则调用线程阻塞等待其它线程从队列中取出元素。调用take方法时，如果阻塞队列已经为空，则调用线程阻塞等待其它线程向队列添加新元素。

超时形式 *** 作，在阻塞的基础上添加一个超时限制，如果等待时间超过指定值，抛出InterruptedException。

阻塞队列实现了Queue接口，而Queue接口实现了Collection接口，因此BlockingQueue也提供了remove(e) *** 作，即从队列中移除任意指定元素，但是这个 *** 作往往不会按预期那样高效的执行，所以应当尽量少的使用这种 *** 作。

阻塞队列与并发队列（例如ConcurrentLinkQueue）都是线程安全的，但使用的场合不同。

Graphic3-1给出了阻塞队列的接口方法，Graphic3-2给出了阻塞队列的实现类结构。

Graphic 3-1 BlockingQueue接口

Graphic3-2阻塞队列的实现类

311 ArrayBlockingQueue类

一个以数组为基础的有界阻塞队列，此队列按照先进先出原则对元素进行排序。队列头部元素是队列中存在时间最长的元素，队列尾部是存在时间最短的元素，新元素将会被插入到队列尾部。队列从头部开始获取元素。

ArrayBlockingQueue是“有界缓存区”模型的一种实现，一旦创建了这样的缓存区，就不能再改变缓冲区的大小。ArrayBlockingQueue的一个特点是，必须在创建的时候指定队列的大小。当缓冲区已满，则需要阻塞新增的插入 *** 作，同理，当缓冲区已空需要阻塞新增的提取 *** 作。

ArrayBlockingQueue是使用的是循环队列方法实现的，对ArrayBlockingQueue的相关 *** 作的时间复杂度，可以参考循环队列进行分析。

312 LinkedBlockingQueue

一种通过链表实现的阻塞队列，支持先进先出。队列的头部是队列中保持时间最长的元素，队列的尾部是保持时间最短的元素。新元素插入队列的尾部。可选的容量设置可以有效防止队列过于扩张造成系统资源的过多消耗，如果不指定队列容量，队列默认使用IntegerMAX_VALUE。LinkedBlockingQueue的特定是，支持无限（理论上）容量。

313 PriorityBlockingQueue

PriorityBlockingQueue是一种基于优先级进行排队的无界队列。队列中的元素按照其自然顺序进行排列，或者根据提供的Comparator进行排序，这与构造队列时，提供的参数有关。

使用提取方法时，队列将返回头部，具有最高优先级（或最低优先级，这与排序规则有关）的元素。如果多个元素具有相同的优先级，则同等优先级间的元素获取次序无特殊说明。

优先级队列使用的是一种可扩展的数组结构，一般可以认为这个队列是无界的。当需要新添加一个元素时，如果此时数组已经被填满，优先队列将会自动扩充当前数组（一般认为是，先分配一个原数组一定倍数空间的数组，之后将原数组中的元素拷贝到新分配的数组中，释放原数组的空间）。

如果使用优先级队列的iterator变量队列时，不保证遍历次序按照优先级大小进行。因为优先级队列使用的是堆结构。如果需要按照次序遍历需要使用Arrayssort(pqtoArray())。关于堆结构的相关算法，请查考数据结构相关的书籍。

在PriorityBlockingQueue的实现过程中聚合了PriorityQueue的一个实例，并且优先队列的 *** 作完全依赖与PriorityQueue的实现。在PriorityQueue中使用了一个一维数组来存储相关的元素信息。一维数组使用最小堆算法进行元素添加。

Graphic3-3PriorityBlockingQueue的类关系

314 DelayQueue

一个无界阻塞队列，只有在延时期满时才能从中提取元素。如果没有元素到达延时期，则没有头元素。

32 并发集合

在多线程程序中使用的集合类，与普通程序中使用的集合类是不同的。因为有可能多个线程同时访问或修改同一集合，如果使用普通集合，很可能造成相应 *** 作出现差错，甚至崩溃。Java提供了用于线程访问安全的集合。（前面讨论的BlockingQueue也是这里集合中的一种）。下面针对这些集合，以及集合中使用的相应算法进行探讨。在设计算法时，仅对相应算法进行简要说明，如果读者需要深入了解这些算法的原理，请参考其他的高级数据结构相关的书籍。

321 ConcurrentMap接口

ConcurrentMap接口在Map接口的基础上提供了一种线程安全的方法访问机制。ConcurrentMap接口额外提供了多线程使用的四个方法，这四个方法实际是对Map已有方法的一个组合，并对这种组合提供一种原子 *** 作。Graphic3-4给出了ConcurrentMap相关的 *** 作。Graphic3-5给出了ConcurrentMap的实现类关系图。

从Graphic3-5中可以看出ConcurrentNavigableMap继承自ConcurrentMap，ConcurrentNavigableMap是一种SortedMap，就是说，映射中的元素会根据键值进行排序的。在javautil类库中，有两个类实现了SortedMap接口，分别是TreeMap和ConcurrentSkipListMap。TreeMap使用的是红黑树结构。而ConcurrentSkipListMap使用作为底层实现的SkipList（翻译为跳表）数据结构。此外ConcurrentHashMap实现了ConcurrentMap接口，使用的是HashMap方法。

Graphic3-4 ConcurrentMap

Graphic3-5 实现ConcurrentMap接口。

3211 TreeMap

尽管TreeMap不是线程安全的，但是基于其数据结构的复杂性和方便对比说明，还是在这里简单提一下。TreeMap实现了SortedMap接口。TreeMap使用的是红黑树（这是高等数据结构中的一种），在红黑树算法中，当添加或删除节点时，需要进行旋转调整树的高度。使用红黑树算法具有较好的 *** 作特性，插入、删除、查找都能在O(log(n))时间内完成。红黑树理论和实现是很复杂的，但可以带来较高的效率，因此在许多场合也得到了广泛使用。红黑树的一个缺陷在于，可变 *** 作很可能影响到整棵树的结构，针对修改的局部效果不好。相关算法请参考>

TreeMap不是线程安全的，如果同时有多个线程访问同一个Map，并且其中至少有一个线程从结构上修改了该映射，则必须使用外部同步。可以使用CollectionssynchronizedSortedMap方法来包装该映射。（注意使用包装器包装的SortMap是线程安全的，但不是并发的，效率上很可能远远不及ConcurrentSkipListMap，因此使用包装器的方法并不十分推荐，有人认为那是一种过时的做法。包装器使用了锁机制控制对Map的并发访问，但是这种加锁的粒度可能过大，很可能影响并发度）。

3212 ConcurrentSkipListMap

另外一种实现了SortedMap接口的映射表是ConcurrentSkipListMap。ConcurrentSkipListMap提供了一种线程安全的并发访问的排序映射表。SkipList（跳表）结构，在理论上能够在O(log(n))时间内完成查找、插入、删除 *** 作。SkipList是一种红黑树的替代方案，由于SkipList与红黑树相比无论从理论和实现都简单许多，所以得到了很好的推广。SkipList是基于一种统计学原理实现的，有可能出现最坏情况，即查找和更新 *** 作都是O(n)时间复杂度，但从统计学角度分析这种概率极小。Graphic3-6给出了SkipList的数据表示示例。有关skipList更多的说明可以参考：>

使用SkipList类型的数据结构更容易控制多线程对集合访问的处理，因为链表的局部处理性比较好，当多个线程对SkipList进行更新 *** 作（指插入和删除）时，SkipList具有较好的局部性，每个单独的 *** 作，对整体数据结构影响较小。而如果使用红黑树，很可能一个更新 *** 作，将会波及整个树的结构，其局部性较差。因此使用SkipList更适合实现多个线程的并发处理。在非多线程的情况下，应当尽量使用TreeMap，因为似乎红黑树结构要比SkipList结构执行效率略优（无论是时间复杂度还是空间复杂度，作者没有做够测试，只是直觉）。此外对于并发性相对较低的并行程序可以使用CollectionssynchronizedSortedMap将TreeMap进行包装，也可以提供较好的效率。对于高并发程序，应当使用ConcurrentSkipListMap，能够提供更高的并发度。

所以在多线程程序中，如果需要对Map的键值进行排序时，请尽量使用ConcurrentSkipListMap，可能得到更好的并发度。

注意，调用ConcurrentSkipListMap的size时，由于多个线程可以同时对映射表进行 *** 作，所以映射表需要遍历整个链表才能返回元素个数，这个 *** 作是个O(log(n))的 *** 作。

Graphic3-6 SkipList示例

3213 HashMap类

对Map类的另外一个实现是HashMap。HashMap使用Hash表数据结构。HashMap假定哈希函数能够将元素适当的分布在各桶之间，提供一种接近O(1)的查询和更新 *** 作。但是如果需要对集合进行迭代，则与HashMap的容量和桶的大小有关，因此HashMap的迭代效率不会很高（尤其是你为HashMap设置了较大的容量时）。

与HashMap性能有影响的两个参数是，初始容量和加载因子。容量是哈希表中桶的数量，初始容量是哈希表在创建时的容量。加载因子是哈希表在容器容量被自动扩充之前，HashMap能够达到多满的一种程度。当hash表中的条目数超出了加载因子与当前容量的乘积时，Hash表需要进行rehash *** 作，此时Hash表将会扩充为以前两倍的桶数，这个扩充过程需要进行完全的拷贝工作，效率并不高，因此应当尽量避免。合理的设置Hash表的初始容量和加载因子会提高Hash表的性能。HashMap自身不是线程安全的，可以通过Collections的synchronizedMap方法对HashMap进行包装。

3214 ConcurrentHashMap类

ConcurrentHashMap类实现了ConcurrentMap接口，并提供了与HashMap相同的规范和功能。实际上Hash表具有很好的局部可 *** 作性，因为对Hash表的更新 *** 作仅会影响到具体的某个桶（假设更新 *** 作没有引发rehash），对全局并没有显著影响。因此ConcurrentHashMap可以提供很好的并发处理能力。可以通过concurrencyLevel的设置，来控制并发工作线程的数目（默认为16），合理的设置这个值，有时很重要，如果这个值设置的过高，那么很有可能浪费空间和时间，使用的值过低，又会导致线程的争用，对数量估计的过高或过低往往会带来明显的性能影响。最好在创建ConcurrentHashMap时提供一个合理的初始容量，毕竟rehash *** 作具有较高的代价。

322 ConcurrentSkipListSet类

实际上Set和Map从结构来说是很像的，从底层的算法原理分析，Set和Map应当属于同源的结构。所以Java也提供了TreeSet和ConcurrentSkipListSet两种SortedSet，分别适合于非多线程（或低并发多线程）和多线程程序使用。具体的算法请参考前述的Map相关介绍，这里不在累述。

323 CopyOnWriteArrayList类

CopyOnWriteArrayList是ArrayList的一个线程安全的变体，其中对于所有的可变 *** 作都是通过对底层数组进行一次新的复制来实现的。

由于可变 *** 作需要对底层的数据进行一次完全拷贝，因此开销一般较大，但是当遍历 *** 作远远多于可变 *** 作时，此方法将会更有效，这是一种被称为“快照”的模式，数组在迭代器生存期内不会发生更改，因此不会产生冲突。创建迭代器后，迭代器不会反映列表的添加、移除或者更改。不支持在迭代器上进行remove、set和add *** 作。CopyOnWriteArraySet与CopyOnWriteArrayList相似，只不过是Set类的一个变体。

323 Collections提供的线程安全的封装

Collections中提供了synchronizedCollection、synchronizedList、synchronizedMap、synchronizedSet、synchronizedSortedMap、synchronizedSortedMap等方法可以完成多种集合的线程安全的包装，如果在并发度不高的情况下，可以考虑使用这些包装方法，不过由于Concurrent相关的类的出现，已经不这么提倡使用这些封装了，这些方法有些人称他们为过时的线程安全机制。

324 简单总结

提供线程安全的集合简单概括分为三类，首先，对于并发性要求很高的需求可以选择以Concurrent开头的相应的集合类，这些类主要包括：ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentSkipListMap、ConcurrentSkipSet。其次对于可变 *** 作次数远远小于遍历的情况，可以使用CopyOnWriteArrayList和CopyOnWriteArraySet类。最后，对于并发规模比较小的并行需求可以选择Collections类中的相应方法对已有集合进行封装。

此外，本章还对一些集合类的底层实现进行简单探讨，对底层实现的了解有利于对何时使用何种方式作出正确判断。希望大家能够将涉及到原理（主要有循环队列、堆、HashMap、红黑树、SkipList）进行仔细研究，这样才能更深入了解Java为什么这样设计类库，在什么情况使用，应当如何使用。

AtomicInteger

可以用原子方式更新int值。类AtomicBoolean、AtomicInteger、AtomicLong和AtomicReference的实例各自提供对相应类型单个变量的访问和更新。java课程培训机构认为基本的原理都是使用CAS *** 作：

booleancompareAndSet(expectedValue,updateValue);

如果此方法（在不同的类间参数类型也不同）当前保持expectedValue，则以原子方式将变量设置为updateValue，并在成功时报告true。

循环CAS，参考AtomicInteger中的实现：

publicfinalintgetAndIncrement(){    for(;;){      intcurrent=get();      intnext=current+1;      if(compareAndSet(current,next))        returncurrent;

}

}  publicfinalbooleancompareAndSet(intexpect,intupdate){    returnunsafecompareAndSwapInt(this,valueOffset,expect,update);

}

ABA问题

因为CAS需要在 *** 作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A就会变成1A-2B－3A。

从Java15开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

ArrayBlockingQueue

一个由数组支持的有界阻塞队列。此队列按FIFO（先进先出）原则对元素进行排序。队列的头部是在队列中存在时间最长的元素。队列的尾部是在队列中存在时间最短的元素。新元素插入到队列的尾部，队列获取 *** 作则是从队列头部开始获得元素。这是一个典型的“有界缓存区”，固定大小的数组在其中保持生产者插入的元素和使用者提取的元素。一旦创建了这样的缓存区，就不能再增加其容量。试图向已满队列中放入元素会导致 *** 作受阻塞；试图从空队列中提取元素将导致类似阻塞。

此类支持对等待的生产者线程和使用者线程进行排序的可选公平策略。默认情况下，不保证是这种排序。然而，通过将公平性(fairness)设置为true而构造的队列允许按照FIFO顺序访问线程。公平性通常会降低吞吐量，但也减少了可变性和避免了“不平衡性”。

LinkedBlockingQueue

一个基于已链接节点的、范围任意的blockingqueue。此队列按FIFO（先进先出）排序元素。队列的头部是在队列中时间最长的元素。队列的尾部是在队列中时间最短的元素。新元素插入到队列的尾部，并且队列获取 *** 作会获得位于队列头部的元素。链接队列的吞吐量通常要高于基于数组的队列，但是在大多数并发应用程序中，其可预知的性能要低。

可选的容量范围构造方法参数作为防止队列过度扩展的一种方法。如果未指定容量，则它等于IntegerMAX_VALUE。除非插入节点会使队列超出容量，否则每次插入后会动态地创建链接节点。

如果构造一个LinkedBlockingQueue对象，而没有指定其容量大小，LinkedBlockingQueue会默认一个类似无限大小的容量（IntegerMAX_VALUE），这样的话，如果生产者的速度一旦大于消费者的速度，也许还没有等到队列满阻塞产生，系统内存就有可能已被消耗殆尽了。

以上就是关于C++.用头文件定义链队列的数据类型LinkQueue,包括入队,出队,取对头元素等基本 *** 作.全部的内容，包括:C++.用头文件定义链队列的数据类型LinkQueue,包括入队,出队,取对头元素等基本 *** 作.、Java中Queue和BlockingQueue的区别、stl中的queue怎么访问队列中某个元素等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！