java循环队列的实现

㈠ 实现循环队列的基本操作（初始化、判断队空、判断队满、入队、出队）

/*
实现循环队列的基本操作（初始化、判断队空、判断队满、入队、出队）
*/
//在javascript中，可以使用数组来实现一个队列
functionstack(){
this.datastore=newArray();//初始化
this.isEmpty=isEmpty;//判断队空
this.isFull=isFull;//判断队满
this.add=add;//入队
this.remove=remove;//出队
this.count=0;

functionisEmpty(){
if(this.count==0)returntrue;
returnfalse;
}

functionisFull(){
if(!isEmpty())returntrue;
returnfalse;
}

functionadd(value){
alert(this.count);
this.datastore[this.count++]=value;
}

functionremove(){
if(this.count<=0){
this.count=0;
alert('当前队列为空，无法删除！');
return;
}
deletethis.datastore[--this.count];
}

}

㈡ 循环队列-实现

姓名：张钰 学号：21011210154 学卖厅院：通信工程学院

【嵌牛导读】循环队列是对前文提出的简单队列的改进，能减少对存储空间的浪费。

【嵌牛鼻子】循环队列

【嵌牛提问】循环队列如何实现

【嵌牛正文】

循环队列也是一种线性数据结构，其操作表现基于先进先出原则，并且队尾被连接在队首之后以形成一个循环。循环队列的一个好处是可以利用这个队列之前用过的空间。在上文提出的队列中，只要队列满仿李了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用中大隐这些空间去存储新的值，减少对存储空间的浪费。

我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置，来实现循环队列，基本思路如下：

1、队列为空状态时，两个指针 head = tail = -1

2、入队操作：如果入队前是空的，则将head 和 tail 都向右移一位，使得下标变为为0；否则只需右移tail

3、出队操作：如果出队时队列不为空，且只剩最后一个元素，即head == tail，则令head = tail = -1；否则只需右移head

4、队列首元素：只要队不为空，head指向队首元素

5、队列尾元素：只要队不为空，tail指向队尾元素

6、判定队列为空：指针 head = tail = -1，此时为空

7、判定队列为满：tail右移发现与head重合，则没有地方放入新的元素，此时为满

python实现：

㈢ java8 中concurrenthashmap数据结构和HashMap一样，且线程安全 为什么还要HashMap

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阻塞队列的实现类

3.1.1 ArrayBlockingQueue类

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

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

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

3.1.2 LinkedBlockingQueue

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

3.1.3 PriorityBlockingQueue

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

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

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

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

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

Graphic3-3PriorityBlockingQueue的类关系

3.2.1.1 TreeMap

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

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

3.2.1.2 ConcurrentSkipListMap

另外一种实现了SortedMap接口的映射表是ConcurrentSkipListMap。ConcurrentSkipListMap提供了一种线程安全的并发访问的排序映射表。SkipList（跳表）结构，在理论上能够在O(log(n))时间内完成查找、插入、删除操作。SkipList是一种红黑树的替代方案，由于SkipList与红黑树相比无论从理论和实现都简单许多，所以得到了很好的推广。SkipList是基于一种统计学原理实现的，有可能出现最坏情况，即查找和更新操作都是O(n)时间复杂度，但从统计学角度分析这种概率极小。Graphic3-6给出了SkipList的数据表示示例。有关skipList更多的说明可以参考：http://blog.csdn.net/caoeryingzi/archive/2010/11/18/6018070.aspx和http://en.wikipedia.org/wiki/Skip_list这里不在累述。希望读者自行学习。

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

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

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

Graphic3-6 SkipList示例

3.2.1.3 HashMap类

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

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

3.2.1.4 ConcurrentHashMap类

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

3.2.2 ConcurrentSkipListSet类

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

3.2.3 CopyOnWriteArrayList类

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

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

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

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

3.2.4简单总结

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

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

㈣ java中，实现一个循环队列，其中的边界条件有些弄不明白，请看我的代码：

//我做了一个测试类，你运行一下试试吧
//问题的关键在于这个类的设计似乎是，假设size是3，但是数组的size是4
//putloc是0,但是put的位置在数组中是1
//总觉得这个类的设计很怪，既然size是3，底层实现也做成3就好了。

import java.util.Arrays;

public class CircularQueue {
private char q[];
private int putloc, getloc;

public static void main(String[] args) {
CircularQueue circularQueue = new CircularQueue(3);
circularQueue.put('1');
circularQueue.put('1');
circularQueue.put('1');
circularQueue.put('1');
}

private void paint(String s) {
System.out.println(s + ": putloc=" + putloc + " getloc=" + getloc + " "
+ Arrays.toString(q));
}

public CircularQueue(int size) {
q = new char[size + 1];// 注意：这里数组长度加 1。
putloc = getloc = 0;
paint("create!");
System.out.println();
}

public void put(char ch) {
paint("before put");
if (putloc + 1 == getloc | ((putloc == q.length - 1) & (getloc == 0))) { // 第一个边界条件想不清楚，为什么putloc+1==getloc
System.out.println("--Queue is full.");
return;
}
putloc++;
if (putloc == q.length)
putloc = 0;
q[putloc] = ch;
paint("after put");
System.out.println();
}

public char get() {
paint("before get");
if (getloc == putloc) {
System.out.println("--Queue is empty.");
return (char) 0;
}
getloc++;
if (getloc == q.length)
getloc = 0;
paint("after get");
System.out.println();
return q[getloc];
}
}

㈤ 用java实现循环队列

简单写了下，希望你能看明白

import java.util.ArrayList;

public class SeqQueue {

ArrayList<String> list;

public SeqQueue() {
list = new ArrayList<String>();
}

public String getFirst() {
if (!list.isEmpty()) {
String s = list.get(0);
list.remove(0);
return s;
}
return null;
}

public void insertLast(String s) {
list.add(s);
}

public static void main(String[] args) {
SeqQueue seq = new SeqQueue();
seq.insertLast("111");
seq.insertLast("222");
seq.insertLast("333");
System.out.println(seq.getFirst());
System.out.println(seq.getFirst());
System.out.println(seq.getFirst());
}

}

㈥ 循环队列的条件处理

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是空还是满。
解决这个问题的方法至少有两种：
① 另设一布尔变量以区别队列的空和满；
②另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。如图情况，队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。

类型定义采用环状模型来实现队列,各数据成员的意义如下：
front指定队首位置，删除一个元素就将front顺时针移动一位；
rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；
count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元素。
队空：count=0
队满：count=MaxQSize
#define QueueSize 100//应根据具体情况定义该值
typedef char DataType;//DataType的类型依赖于具体的应用
typedef struct{
int front;//头指针，队非空时指向队头元素
int rear;//尾指针，队非空时指向队尾元素的下一位置
int count;//计数器，记录队中元素总数DataTypedata[QueueSize];
}CirQueue;
基本运算
用第三种方法，循环队列的六种基本运算：
① 置队空
voidInitQueue(CirQueue*Q){ Q->front=Q->rear=0;Q->count=0; }//计数器置0
② 判队空
intQueueEmpty(CirQueue*Q){ returnQ->count==0; }//队列无元素为空
③ 判队满
intQueueFull(CirQueue*Q){ returnQ->count==QueueSize;}//队中元素个数等于QueueSize时队满
④ 入队
voidEnQueue(CirQueue*Q,DataTypex){
if(QueueFull(Q))Error(Queueoverflow); //队满上溢
Q->count++; //队列元素个数加1
Q->data[Q->rear]=x; //新元素虚让插入队尾
Q->rear=(Q->rear+1)%QueueSize; //循环意义下将尾指针加1
}
⑤ 出队
DataTypeDeQueue(CirQueue*Q){
DataType temp;
if(QueueEmpty(Q))Error(Queueunderflow); //队空下溢
temp=Q->data[Q->差配局front];
Q->count--; //队列元素个数减1
Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1returntemp;}
⑥取队头元素
DataTypeQueueFront(CirQueue*Q){
if(QueueEmpty(Q))Error(Queueisempty.);
returnQ->data[Q->front];
}
````````````````````````````````````````````````````````````````````````````````````
队卖握列的操作特点是“先进先出”。前者主要是头指针、尾指针的使用，后者主要是理解循环队列提出的原因及其特点。两者都要掌握队列空与满的判定条件以及出队列、入队列操作的实现。

㈦ java中的arraydeque是循环队列吗

ArrayDeque的实现Java中的双端队列是用数组实现的，是循环队列。

㈧ Java如何使用数组实现循环队列的案例

class Element{
int id;
String name;
Element(int a,String n){
id=a;name=n;
}
}

class SeqQueue{
int first,last,maxsize;
Element queue[];
SeqQueue(int i){
maxsize=i;
first=last=-1;
queue=new Element[i];
}

public void clear(){//置空
first=last=-1;
}

public boolean isEmpty(){//判空
if(first==-1)return true;
else return false;
}

public Element getFirst(){//取队列头元素
if(first==-1)return null;
else return queue[first+1];
}

public boolean isFull(){//判满
if((last+1)%maxsize==first)return true;
else return false;
}

public boolean enQueue(Element e){//入队
if(this.isFull())return false;
if(this.isEmpty())
first=last=0;
else
last=(last+1)%maxsize;
queue[last]=e;
return true;
}

public Element deQueue(){//出队
Element t=queue[first];
if(this.isEmpty())return null;
if(first==last){
queue[first]=null;
this.clear();
return t;
}
queue[first]=null;
first=(first+1)%maxsize;
return t;
}

public int getLength(){//队列长度
if(last>=first)return last-first+1;
else return maxsize-(first-last)+1;
}

public void display(){//打印所有元素
int i,j;
for (i=first,j=0;j<this.getLength();i=(i+1)%maxsize,j++)
System.out.println(queue[i].id);
}
}

㈨ 各位大哥，在Java中用数组写的循环队列实现凯撒循环密码啊

import java.*;

public class Practise {
public static void main(String[] args) {
String P = new String();// 明文
String K = new String();// 密钥
String C = new String();// 密文
short LR=-1;//间隔的方向，向左为-1，向右为1

P = "benrencainiaoyi";
K = "P";
C = "QTCGTCRPXCXPDNXOWX";

System.out.println("明文："+P);
System.out.println("密钥："+K);
System.out.println("密文："+C+"\n");

CaesarCode caesar=new CaesarCode();
LR=1;
System.out.println("加密："+caesar.encrypt(P, K, LR));
LR=-1;
System.out.println("解密："+caesar.decrypt(K, C, LR).toLowerCase());

}
}

class CaesarCode {
private char alphabet[] = new char[26];//存储字母表

//加密
protected String encrypt(String P,String K,short LR)
{
int i=0,j=0,n=0;//n是间隔
String C=new String();//密文
P=P.toUpperCase();
P=getNewP(P);
K=K.toUpperCase();
n=getN(K);

//将明文转换成密文
for(i=0;i<P.length();i++)
{
j=String.valueOf(alphabet).indexOf(P.charAt(i));//获取密文字母在字母表所在的下标
j=(j+n*LR+26)%26;//向左或向右移动n位
C+=(char)(j+65);
}

return C;
}

//解密
protected String decrypt(String K,String C,short LR)
{
int i=0,j=0,n=0;//n是间隔
String P=new String();//明文
K=K.toUpperCase();
C=C.replaceAll(" +"," ");
C=C.toUpperCase();
n=getN(K);

//将密文转换成明文
for(i=0;i<C.length();i++)
{
j=String.valueOf(alphabet).indexOf(C.charAt(i));//获取密文字母在字母表所在的下标
j=(j+n*LR+26)%26;//向左或向右移动n位
P+=(char)(j+65);
}

return P;
}

//获取经过处理的明文
private String getNewP(String P)
{
int i=0;
char p[] = P.toCharArray();
for (i = 0; i < P.length(); i++) {
if (p[i] < 'A' || p[i] > 'Z')// 将非字母换成空格
{
p[i] = ' ';
}
}
P = String.valueOf(p);
P = P.replaceAll(" +", "");// 将明文的所有空格去掉

return P;
}

//获取间隔
private int getN(String K)
{
int i=0,n=0;
//生成字母表
for(i=0;i<26;i++)
{
alphabet[i]=(char)(i+65);//字母A在ASCII表中的值是065
}
if(isNum(K))
{
n=Integer.parseInt(K);
}
else
{
n=String.valueOf(alphabet).indexOf(K);//当K不是数字时适用
}
return n;
}

//判断密钥是否为数字
private boolean isNum(String K)
{
return K.matches("[0-9]+");//+表示1个或多个（如"3"或"225"）
}
}