队列的存储实现
#include<stdio.h>
#include<stdbool.h>
#include<malloc.h>
typedef
int
typedata;
struct
node
{
struct
node
*prev,
*next;
typedata
data;
};
typedef
struct
node
node;
typedef
struct
node*
link;
//
============init_head===============
//
//头节点的初始化
link
init_head(void)
{
link
head
=
(link)malloc(sizeof(node));
if(head
!=
NULL)
{
head->prev
=
head->next
=
head;
}
return
head;
}
//
============newnode
================
//
//创建新节点
link
newnode(typedata
data)
{
link
new
=
(link)malloc(sizeof(node));
if(new
!=
NULL)
{
//前趋指针和后趋指针都指向自己
new->prev
=
new->next
=
new;
new->data
=
data;
}
return
new;
}
//
=================is_empty================
//
bool
is_empty(link
head)
{
//为空时，头节点的前趋指针和后趋指针都指向head（头节点）
if((head->next==head)
&&
(head->prev==head))
return
true;
return
false;
}
//
================insert_tail
==================
//
void
insert_tail(link
head,
link
new)
{
if(is_empty(head))
{
//第一个节点插入
head->next
=
head->prev
=
new;
new->next
=
new->prev
=
head;
return
;
}
//除了第一个节点插入
new->prev
=
head->prev;
new->next
=
head;
new->prev->next
=
new;
new->next->prev
=
new;
}
//
================show
====================
//
void
show(link
head)
{
//为空时，直接返回
if(is_empty(head))
return
;
//遍历整个链
link
tmp
=
head->next;
while(tmp
!=
head)
{
printf("%d\t",
tmp->data);
tmp
=
tmp->next;
}
printf("\n");
}
//
==============insert_opint
===============
//
void
insert_opint(link
end_node,
link
p)
{
p->prev
=
end_node;
p->next
=
end_node->next;
end_node->next->prev
=
p;
end_node->next
=
p;
}
//
================insertion_sort===========
//
//顺序排序
void
insertion_sort(link
head)
{
if(is_empty(head))
return;
//把队列分拆，头节点和第一个节点为一个已排序的队列，
//其他的节点逐个比较已排序队列插
link
p
=
head->next->next;
head->prev->next
=
NULL;
head->next->next
=
head;
head->next->prev
=
head;
head->prev
=
head->next;
while(p
!=
NULL)
{
link
end_node
=
head->prev;
if(p->data
>
end_node->data)
{
link
tmp
=
p;
p
=
p->next;
insert_tail(head,
tmp);
}
else
{
while(end_node!=head
&&
p->data<end_node->data)
end_node
=
end_node->prev;
link
tmp
=
p;
p
=
p->next;
insert_opint(end_node,
tmp);
}
}
}
int
main(void)
{
link
head
=
init_head();
if(head
==
NULL)
{
printf("falure\n");
return
0;
}
typedata
data;
while(1)
{
if(scanf("%d",
&data)
!=
1
)
break;
link
new
=
newnode(data);
if(new
==
NULL)
{
printf("falure\n");
return
0;
}
insert_tail(head,
new);
show(head);
}
printf("the
figure
is:\n");
show(head);
insertion_sort(head);
show(head);
return
0;
}
㈡ 队列的两种存储方式对比
队列的两种存储方式分为消息投递实时性：使用短轮询方式，实时性取决于轮询间隔时间：使用长轮询，同写入实时性一致，消息的写入延时通常在几个毫秒。总结：短轮询：周期性的向服务提供方发起请求，获取数据优点：前后端程序编写比较容易。缺点：请求中有大半是无用，难于维护，浪费带宽和服务器资源；响应的结果没有顺序（因为是异步请求，当发送的请求没有返回结果的时候，后面的请求又被发送。而此时如果后面的请求比前面的请 求要先返回结果，那么当前面的请求返回结果数据时已经是过时无效的数据了）。长轮询：客户端向服务器发送请求，服务器接到请求后保持住连接，直到有新消息才返回响应信息并关闭连接，客户端处理完响应信息后再向服务器发送新的请求。优点：在无消息的情况下不会频繁的请求，耗费资源小。缺点：服务器hold连接会消耗资源，难于管理维护。消费失败重试Kafka：消费失败不支持重试RocketMQ：消费失败支持定时重试，每次重试间隔时间顺延总结：kafka也可以通过编写代码来实现写入和消费失败的重试机制，这种要求需要用户来编写代码实现，kafka只是提供了这种方式，但并不是他推荐的使用方式，他的设计模式上只是兼顾了这种情况，并不是重点。RocketMQ在设计上就考虑了这种情况，在提供的官方api中提供了重试的设置，用户可以选择多种模式的重试机制，以及自定义的重试逻辑，简单场景下用户只用设置一下参数即可。关于需要重试的场景例如充值类应用，当前时刻调用运营商网关，充值失败，可能是对方压力过多，稍后在调用就会成功，如支付宝到银行扣款也是类似需求。这里的重试需要可靠的重试，即失败重试的消息不因为Consumer宕机导致丢失。
㈢ 队列的 2 种实现方式
队列，是一个线性表，和数组，栈，链表类似。队列和栈类似，戏称“边吃边拉”。即 FIFO。
队列和栈还有一个不同，栈只需维护一个栈顶指针，而队列需要维护 2 个指针，队首和队尾。
队列可以使用数组实现，例如 Java 类库的 LinkedBlockingQueue，也可以使用数组实现，例如 Java 的 ArrayBlockingQueue。这里我们讨论数组的实现。
通常使用数组实现，会使用循环数组，也称 ringBuffer，好处是不用 数组进行迁移，另外，传统实现，如果数组满了，就不能再继续插入了，即使前面还有空间，因此就需要刚刚说的 进行迁移。下面是最简单的一个 Java 循环数组实现。
这个是一个标准的实现，但是存在一个问题：如果队列长度是 8，那么就只能存储 7 个元素。原因下面分析。
这个图，表示队列为空，因为 put 指针和 get 指针，指向了同一个槽位。get 指针不能够再继续移动。
那如果表示满了呢？
这个图，get 指针在 5 槽位，put 指针 4 槽位，put 指针不能再继续移动，否则会覆盖 5 槽位的值。
由此我们得到公式：
isEmpty = put == get;
ifFull = (put + 1) % n == get;
所以，put 一定比 get 少在一个槽位。
当 put 在 7 这个槽位，get 在 0 这个槽位，他还能继续放入元素在 7 这个位置吗？答案是不能，因为我们通过 put + 1 % n == get 这个公式计算，如果 在 7 个槽位加入了元素，那么 put 指针就会变成 0，问题来了，put 是 0 ，get 也是0。
而 isEmpty 的公式是 put == get。这个时候，就会发生判断错误：原本是满的，却判断是空的。
所以，这个实现导致必须有一个空位。当然，我们也可以把槽位加1，也就是把数组长度加 1，避免实际长度不符合预期，也可以避免这个问题。
通过上面的分析，我们知道了，如果不加上1，将导致 isEmpty 判断错误。原因是如果 put 和 get 指针重合，我们无法区分到底是 满了 还是 空了。因为我们判断是满还是空，利用的是指针。
如果不使用指针呢？使用一个计算器，例如，添加一个元素，计算器 + 1， 删除一个元素，计算器 - 1. 是否可以呢？答案是可以的.
下面是具体实现：
我们判断 ifEmpty ，使用 size == 0 判断；判断 isFull，使用 size == n 判断，这样就解决了这个问题。
队列可以使用链表和数组实现，通常使用使用数组实现，效率高，不用搬移。使用循环数组，需要考虑的是 ifFull 判断和 isEmpty 判断。
这里我建议使用 size 这种方式，而不是 + 1 这种方式，为什么呢？使用 size 这种方式，我们可以利用 & 运算来快速计算下标——只要用户指定的队列长度是 2 的幂次方。
如果使用 + 1 的方式，即使用户指定的队列长度是 2 的幂次方，也无法使用 & 运算快速获取下标。
当然，我们也可以根据用户指定的队列长度是否为2 的幂次方，来觉得到底是使用 size 方式，还是使用 + 1 方式。
㈣ 队列的存储结构为什么一般采用循环队列的形式
循环队列属于逻辑结构,其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可以为分散的链表或是连续的线性表，与其逻辑结构实现功能无关