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"）
}
}