假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素
假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法(在出队列算法中要返回队头元素)。
循环队列满的条件是：quelen==m。 & &(1)数据结构 & &struct Queue{ & & & &DataType sequ[m]; & & & &int rear, & &}; & &typedef struct Queue*PQ & &(2)思路 & &入队列和出队列的算法和普通队列的思路近似，只是原来用两指针指向之差来表示队列中元素的个数，现在直接用quelen来表示。 & &(3)算法 & &PQueue createEmptyQueue(){ & &/*创建空队列*/ & & & &PQueue pqu=(PQueue)malloc(sizeof(struct Queue)); & & & &pqu-＞rear=0; & & & &pqu-＞quelen=0; & &/*初始化*/ & &} & &void enQueue(PQueue pqu,DataType x){ & &/*入队列*/ & & & &if(pqu-＞quelen==m){ & & & & & &printf(&Overflow!in&); & & & & & & & & & &} & & & &pqu-＞sequ[pqu-＞rear]=x; & & & &pqu-＞rear=(pqu-＞rear+1)%m; & & & &pqueue-＞quelen++; & &} & &DataType deQueue(PQueue pqu){ & &/*对非空队列,求队列的头元素,并出队列*/ & & & &int front=(pqu-＞rear-pqu-＞quelen)%M; & & & &pqu-＞quelen--; & & & &return pqu-＞sequ[front]； & &} & &(4)代价分析 & &上述几个算法都不包含循环，只有常数条语句，因此每个算法的时间代价均为O(1)。今天看啥 热点：
数据结构（C实现）------- 顺序队列(循环队列之少用一个存储空间实现) .，-------队列
&&&&&&上节已经提到有三种方法来实现循环顺序队列，其中第一种设立标识不常用，最常的就是后两种，上一节已经讨论了用计数器来实现循环顺序队列，这节就用第三种方法，也就是少用一个存储空间来实现循环顺序队列，其基本操作和用计数实现类同，下面是具体实现：
顺序队列（循环队列）类型描述：
//顺序队列的类型描述
#define MAXSIZE 5
typedef int ElemT
typedef struct{
ElemType *
int front,
基本操作：
&&&&&&&&&1.&初始化顺序队列(循环队列)&Init_SqQueue(SqQueue* Q)
void Init_SqQueue(SqQueue* Q){
Q-&data = (SqQueue*)malloc(sizeof(SqQueue) * MAXSIZE);
Q-&front = Q-&rear = 0;
&&&&&&& 2. 销毁顺序队列(循环队列)Destroy_SqQueue(SqQueue* Q)
void Destroy_SqQueue(SqQueue* Q){
if(Q-&data){
free(Q-&data);
Q-&front = Q-&rear = 0;
&&&&&&&3. 清空顺序队列(循环队列)Clear_SqQueue(SqQueue* Q)
void Clear_SqQueue(SqQueue* Q){
Q-&front = Q-&rear = 0;
&&&&& 4. 判断顺序队列(循环队列)是否为空IsEmpty_SqQueue(SqQueue* Q)
int IsEmpty_SqQueue(SqQueue* Q){
return (Q-&rear == Q-&front);
&&&&& &5.&判断顺序队列(循环队列)是否已满&iSFull_SqQueue(SqQueue* Q)
int iSFull_SqQueue(SqQueue* Q){
return ((Q-&rear + 1) % MAXSIZE == Q-&front);
&&&&& 6. 求得顺序队列(循环队列)的长度GetLength_SqQueue(SqQueue* Q)
int GetLength_SqQueue(SqQueue* Q){
return (Q-&rear - Q-&front + MAXSIZE) % MAXSIZE;
&&&&& 7. 取得顺序队列(循环队列)的的队头GetHead_SqQueue(SqQueue* Q,ElemType *x)
void GetHead_SqQueue(SqQueue* Q,ElemType *x){
if(IsEmpty_SqQueue(Q)){
printf(&顺序队列空!\n&);
*x = Q-&data[Q-&front];
&&&& & 8. 取得顺序队列(循环队列)的的队尾GetRear_SqQueue(SqQueue* Q,ElemType *x
void GetRear_SqQueue(SqQueue* Q,ElemType *x){
if(IsEmpty_SqQueue(Q)){
printf(&顺序队列空!\n&);
*x = Q-&data[(Q-&rear - 1 + MAXSIZE) % MAXSIZE];
&&&&& 9.&入顺序队列(循环队列)En_SqQueue(SqQueue* Q,ElemType x)
void En_SqQueue(SqQueue* Q,ElemType x){
if(iSFull_SqQueue(Q)){
printf(&顺序队列已满!\n&);
Q-&data[Q-&rear] =
Q-&rear = (Q-&rear + 1) % MAXSIZE;
&&&&& 10. 出顺序队列(循环队列)De_SqQueue(SqQueue* Q,ElemType *x)
void De_SqQueue(SqQueue* Q,ElemType *x){
if(IsEmpty_SqQueue(Q)){
printf(&顺序队列空!\n&);
*x = Q-&data[Q-&front];
Q-&front = (Q-&front + 1) % MAXSIZE;
&&&&&&&11. 打印顺序队列(循环队列)Print_SqQueue(SqQueue* Q)
void Print_SqQueue(SqQueue* Q){
int i = 0;
int j = Q-&
if(IsEmpty_SqQueue(Q)){
printf(&顺序队列空!\n&);
while(i & GetLength_SqQueue(Q)){
printf(&%d\t&,Q-&data[j]);
j = (j + 1) % MAXSIZE;
printf(&\n&);
&&&& 以上，就是循环顺序队列的另一种实现方法，也就是通过少用一个存储空间，和用计数器实现循环顺序队列的主要区别在判断队列满上。
帅哥，代码就算了吧，很长的，你可以去书店找《数据结构》严蔚敏的教材 我可以给你说一下其算法思路： 一般的讲，一个顺序队列一定要设计成顺序循环队列的数据结构，否则就会出现“假溢出”的现象。 假溢出是指，这样的溢出并不是由于存储空间不够而造成的，而是由于队列的队尾指针不能自动由所定义的最大值自动转为最小值（即由队尾转向队头） 防止假溢出的方法就是用“顺序循环队列” 假设对头指针是front,队尾指针是rear 那么让队尾指针+1就自动指向对头——这就是循环 这是靠%运算实现的： (rear+1)%N==front , 其中N是存储空间的大小 那么在顺序循环队列中，如何判断“队列满”和“队列空”这两种状态呢？ 一般的做法是，少用一个存储空间。这样的话： 队列空的条件：rear==front 队列满的条件：(rear+1)%N==front 你所说的只用对头指针实现顺序循环队列，我个人认为这样的实现似乎不现实且无意义，你想想什么是队列ne？不就是队头出队尾进吗？你连队尾指针都没有，每次插入数据都要通过遍历算法来遍历整个队列，这样的效率真是....垃圾得可以，与其只用对头指针，还不如改用数组，你说呢？？还有，我看到你的补充了，你所说的计数器，其实质不就是队尾指针吗？对头指针永远指向对头，front+Count(Count是计数器值)不就是队尾指针的位置吗？所以计数器不就是换了种形式的队尾指针不是吗？
队列长度应该为：（rear - front + m）% m 循环队列主要是两种情况：1.front在上面,比如一个长度为5的循环队列：-代表空，x代表有数据|-------5||-------4| &-rear|xxxxxx3||xxxxxx2|&-front|-------1|那么队列的长度是rear-front是没有问题的2.由于是循环队列，入队的时候从尾巴进，出来的时候从front出来，如果情况1再进来2个元素就变为|xxxxx5||xxxxx4||xxxxx3||xxxxx2|&-front|-------|&-rear显然，这种情况下用rear-front得出来的结果就不正确了，所以就出来上面的公式了其实我觉得取绝对值也可以吧
相关搜索：
相关阅读：
相关频道：
&&&&&&&&&&&&&&&&
WEB编程教程最近更新扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋基于循环数组的无锁队列 - 推酷
基于循环数组的无锁队列
在之前的两篇博客（
）中，分别写了在只有一个读线程、一个写线程的情况下，以及只有一个写线程、两个读线程的情况下，不采用加锁技术，甚至原子运算的循环队列的实现。但是，在其他的情况下，我们也需要尽可能高效的线程安全的队列的实现。本文实现了一种基于循环数组和原子运算的无锁队列。采用原子运算（compare and swap）而不是加锁同步，可以很大的提高运行效率。之所以用循环数组，是因为这样在使用过程中不需要反复开辟内存空间，可以达到较好的效率。本文的实现参考了论文Implementing Lock-Free Queues所提到的方法。但是，在这篇论文中，作者并没有给出具体的实现。本文的实现也和论文中的方法有所不同。本文的实现基于Windows操作系统，代码在Visual Studio 2010下测试通过。
本文的实现基于compare and swap这个原子操作，简写为CAS。其原型为
long CAS(long* ptr, long old_value, long new_value).
其操作为，如果ptr所指向的变量和old_value相等，则将其置为new_value. 否则什么也不做。返回值为ptr所指向的变量。
本文提出的方法的基本原理如下。代码会在其后附上。
首先，我们约定，有一个特殊的数值，叫做EMPTY，存入数组的所有数都不能是这个数值。在一开始，将整个buffer的值都初始化为EMPTY.
第二，以两个变量，readCnt和writeCnt，来记录读和写的次数。这两个数模数组长度，就可以得到下一次读和写的位置。如果readCnt和writeCnt模buffer大小相等，则说明当前队列为控；而如果在写的位置不是EMPTY，则说明buffer已满。
第三，也就是最重要的，线程同步的原理。在进行写buffer操作时，首先通过CAS操作将buffer对应位置置为指定值，而writeCnt不变，因此其他线程无法在同样的位置进行写操作，这样防止了其他写线程的覆盖。而由于此时writeCnt还没有变，读线程此时也无法读该位置的数据，这样防止了其他读线程的冲突。接下来，第二步，则是通过CAS操作，将writeCnt加一。可以看到，代码中在第一个CAS操作失败的情况下，会执行一个增大writeCnt的原子操作。这样做的目的是避免某个线程停掉导致其他所有线程都停掉。
而在进行写操作时，首先通过判断readCnt和writeCnt是否相等来判断当前队列是否已满。这样做的原因如前所述，是为了避免和写线程之间的冲突。接下来，如果当前位置可以读，则通过一个CAS操作将readCnt加一。这样，其他读线程就无法再读这个位置。而由于这个位置值还不是EMPTY，其他写线程也无法写这个位置。接下来，在读走数值之后，再通过CAS操作将buffer中的这个位置置为EMPTY. 此时，写线程可以在这个位置写入数据。
但是，这个实现其实还有点问题。如果读线程比较多，例如，读线程个数和数组长度一样，就可能两个读线程同时读同一个位置。这样的读冲突这个程序是无法避免的。另外，如果读数据过程中有一个读线程停掉了，那么其他线程在读或者写到这个位置时，也会被阻塞。
代码如下。
1 #include &windows.h&
2 #include &stdlib.h&
4 #define CAS(ptr, oldval, newval) (InterlockedCompareExchange(ptr, newval, oldval))
6 static const long EMPTY=-1;
8 class NBQueue {
: queueSize(0)
, buffer(NULL)
, readCnt(0)
, writeCnt(0){}
~NBQueue() {
bool init(int size) {
queueSize =
buffer = new long[queueSize];
catch (...) {
queueSize = 0;
buffer = NULL;
return false;
for (int i = 0; i & queueS i++) {
buffer[i] = EMPTY;
return true;
void uninit() {
if (buffer != NULL) {
buffer = NULL;
queueSize = 0;
bool put(long v) {
tail = writeC
index = tail % queueS
if (buffer[index] != EMPTY) {
return false;
long oldval = CAS(&buffer[index], EMPTY, v);
succ = oldval == EMPTY;
if (!succ) {
CAS(&writeCnt, tail, tail + 1);
} while (!succ);
CAS(&writeCnt, tail, tail + 1);
return true;
bool get(long* v) {
head = readC
if (head == writeCnt % queueSize) {
return false;
long oldval = CAS(&readCnt, head, head + 1);
succ = oldval ==
} while (!succ);
long index = head % queueS
*v = buffer[index];
CAS(&buffer[index], *v, EMPTY);
return true;
84 private:
int queueS
long readC
long writeC
已发表评论数()
已收藏到推刊！
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
排版有问题
没有分页内容
视频无法显示
图片无法显示