目錄
成都創(chuàng)新互聯(lián)公司長(zhǎng)期為上1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為通道企業(yè)提供專業(yè)的成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)，通道網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。一、棧（Stack）
1、定義
2、順序結(jié)構(gòu)模擬實(shí)現(xiàn)棧和常用方法
（1）.棧的順序存儲(chǔ)
（2）.基本方法
3、棧的鏈?zhǔn)浇Y(jié)構(gòu)與順序結(jié)構(gòu)對(duì)比
（1）.對(duì)比
4、區(qū)分概念
（1）.棧
（2）.虛擬機(jī)棧
（3）.棧幀
二、隊(duì)列（Queue）
1、定義
2、鏈?zhǔn)浇Y(jié)構(gòu)模擬實(shí)現(xiàn)隊(duì)列及常用方法
（1）.隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)初始化
（2）.常用方法
[1].入隊(duì)
[2].出隊(duì)
[3].獲取隊(duì)頭元素
[4].獲取有效元素個(gè)數(shù)
[5]. 檢測(cè)是否為空
3、循環(huán)隊(duì)列
（1）.循環(huán)隊(duì)列的數(shù)組下標(biāo)
（2）.區(qū)分空的循環(huán)隊(duì)列和滿的循環(huán)隊(duì)列
4、鏈?zhǔn)浇Y(jié)構(gòu)隊(duì)列和循環(huán)隊(duì)列的比較
5、雙端隊(duì)列（Deque）
（1）.定義
（2）.Deque是一個(gè)接口，使用時(shí)必須創(chuàng)建LinkedList對(duì)象
（3）.Deque接口使用較多，棧和隊(duì)列均可使用該接口
棧是一種特殊的線性組，只允許在一端進(jìn)行插入和刪除元素（這一端稱為 棧頂，另一端稱為 棧底）。數(shù)據(jù)元素遵循 先進(jìn)后出的原則。
入棧（壓棧）：棧的元素插入操作
出棧：棧的元素刪除操作
該棧的底層邏輯是一組地址連續(xù)的存儲(chǔ)單元，用來(lái)從棧底開(kāi)始存放元素
（2）.基本方法
[1]. 構(gòu)造一個(gè)空的棧。
重慶分公司
重慶分公司
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack(){
this.elem=new int[10];
}
}[2].入棧
public void push(int val){
if(isFull()){
elem= Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++]=val;
}
public boolean isFull(){
return usedSize==elem.length;
}[3].出棧
public int pop(){
if(isEmpty()){
throw new EmptyException("棧為空?。?！");
}
int val=elem[usedSize-1];
usedSize--;
return val;
}[4].判空
public boolean isEmpty(){
return usedSize==0;
}[5].讀取棧頂元素（不出棧）
public int peek(){
if(isEmpty()){
throw new EmptyException("棧為空?。。?);
}
return elem[usedSize-1];
}[6].獲取個(gè)數(shù)
int size() 獲取棧中有效元素個(gè)數(shù)
public int size(){
return usedSize;
}相比于順序結(jié)構(gòu)的棧，鏈?？梢赃M(jìn)行多個(gè)棧共享存儲(chǔ)空間以提高內(nèi)存利用率并且?guī)缀醪粫?huì)存在棧滿的情況。此外在時(shí)間復(fù)雜度上順序棧和鏈棧相同均為O(1)。
在空間上順序棧需要事先確定一個(gè)固定的長(zhǎng)度，因此存取時(shí)很方便，但是可能會(huì)存在空間浪費(fèi)。鏈?zhǔn)綏Ｔ诳臻g上通過(guò)指針域連接下一個(gè)元素，雖然增加了一點(diǎn)內(nèi)存的消耗但是棧的長(zhǎng)度可以是無(wú)限的且不會(huì)存在空間浪費(fèi)。
所以如果棧在使用過(guò)程中元素個(gè)數(shù)變化大,最好是用鏈棧。反之,如果元素個(gè)數(shù)的變化在一定范圍內(nèi),建議使用順序棧。
4、區(qū)分概念 （1）.棧是一種數(shù)據(jù)元素先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)
（2）.虛擬機(jī)棧具有特殊作用的一塊內(nèi)存空間。jvm為了對(duì)數(shù)據(jù)進(jìn)行更好的管理，將內(nèi)存按照不同的需求劃分出來(lái)的結(jié)構(gòu)。
棧區(qū)：線程私有的，棧區(qū)中存放的是函數(shù)調(diào)用相關(guān)的一些信息，主要是棧幀。
當(dāng)棧區(qū)中內(nèi)存空間不足時(shí)，會(huì)拋出StackOverflowException；當(dāng)中的元素（棧幀）是按照數(shù)據(jù)結(jié)構(gòu)中的棧的特性來(lái)實(shí)現(xiàn)的
（3）.棧幀一種結(jié)構(gòu)，這種結(jié)構(gòu)與函數(shù)調(diào)用相關(guān)的，內(nèi)部：局部變量表、操作數(shù)棧。
每個(gè)方法在運(yùn)行時(shí)，jvm都會(huì)創(chuàng)建一個(gè)棧幀，然后將棧幀壓入到虛擬機(jī)棧中。當(dāng)方法調(diào)用結(jié)束時(shí)，該方法對(duì)應(yīng)的棧幀會(huì)從虛擬機(jī)棧中出棧。
注意：每個(gè)方法的棧幀中結(jié)構(gòu)都是一樣，大小可能不同，但是棧幀的大小在程序編譯時(shí)就已經(jīng)確定好。
二、隊(duì)列（Queue） 1、定義只允許在一端進(jìn)行數(shù)據(jù)插入（這一端稱為 隊(duì)尾Head/Front），在另一端進(jìn)行數(shù)據(jù)刪除（這一端稱為 隊(duì)尾Tail/Rear）的特殊線性表。數(shù)據(jù)元素 先進(jìn)先出。
入隊(duì)：隊(duì)列的數(shù)據(jù)元素插入操作
出隊(duì)：隊(duì)列的數(shù)據(jù)元素刪除操作
public class MyQueue {
static class Node{
public int val;
public Node next;
public Node(int val){
this.val=val;
}
}
public Node head;
public Node last;
public int usedSize;
}注意：Queue是個(gè)接口，底層是通過(guò)鏈表實(shí)現(xiàn)的
（2）.常用方法
public void offer(int val){
Node node=new Node(val);
if(head==null){
head=node;
last=node;
}else{
last.next=node;
last=node;
}
usedSize++;
}public int poll(){
if(empty()){
throw new EmptyException("隊(duì)列為空！?。?);
}
int ret=head.val;
head=head.next;
if(head==null){
last=null;
}
usedSize--;
return ret;
}public int peek(){
if(empty()){
throw new EmptyException("隊(duì)列為空?。?！");
}
return head.val;
}public int getUsedSize() {
return usedSize;
}public boolean empty(){
return first == null;
}循環(huán)隊(duì)列通常使用數(shù)組實(shí)現(xiàn),我們把隊(duì)列的這種頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列。
當(dāng)隊(duì)頭指針front = array.length-1后，再前進(jìn)x個(gè)位置就自動(dòng)到下一個(gè)循環(huán)，這可以利用除法取余實(shí)現(xiàn)。
初始時(shí)：front =rear=0。
判空：front=rear
判滿：(rear+1)%array.length=front
隊(duì)首指針退x：front = (front + array.length - x) % array.length
隊(duì)尾指針進(jìn)x：rear = (rear + x) % array.length
隊(duì)列長(zhǎng)度：len=(rear - front + array.length) % array.length
[1].下標(biāo)在最后一個(gè)時(shí)再往后
index=(index+x)%arr.length
[2].下標(biāo)在第一個(gè)時(shí)再往后
(index+arr.length-x)%arr.length
（2）.區(qū)分空的循環(huán)隊(duì)列和滿的循環(huán)隊(duì)列[1].添加usedSize屬性
我們可以創(chuàng)建一個(gè)成員變量 usedSize，只有當(dāng) usedSize==隊(duì)列長(zhǎng)度時(shí)判滿，當(dāng) usedSize==0 為空隊(duì)列。
[2].使用標(biāo)記
類型中增設(shè)flag數(shù)據(jù)成員，以區(qū)分是隊(duì)滿還是隊(duì)空。
flag 等于0時(shí)，如果刪除后 front = = rear ，則為隊(duì)空；
flag 等于 1 時(shí)，如果插入后 front == rear ，則為隊(duì)滿。
[3].保留一個(gè)位置
為了區(qū)分隊(duì)空和隊(duì)滿，我們保留最后一個(gè)位置。
如下圖,當(dāng)rear=front便認(rèn)為是隊(duì)空，當(dāng)rear+1=front時(shí)認(rèn)為是隊(duì)滿。
在空間上：鏈?zhǔn)疥?duì)列的數(shù)據(jù)存儲(chǔ)是通過(guò)指針域連接的，會(huì)產(chǎn)生一些空間上的開(kāi)銷；而循環(huán)隊(duì)列有一個(gè)固定的長(zhǎng)度，所以在存儲(chǔ)空間上存在浪費(fèi)，因此鏈隊(duì)更加的靈活。
在時(shí)間上：兩者數(shù)據(jù)操作的時(shí)間復(fù)雜度都是O(1)。鏈?zhǔn)疥?duì)列因?yàn)槭峭ㄟ^(guò)指針域連接的，所以每次添加和刪除結(jié)點(diǎn)都會(huì)存在一些時(shí)間消耗，而循環(huán)隊(duì)列是先申請(qǐng)一個(gè)固定空間，使用時(shí)不釋放，如果入隊(duì)頻繁，則兩者還是有細(xì)微差異。
因此在確定隊(duì)列大值時(shí)，使用循環(huán)隊(duì)列；無(wú)法確定隊(duì)列的長(zhǎng)度時(shí)，則用鏈?zhǔn)疥?duì)列。
5、雙端隊(duì)列（Deque） （1）.定義雙端隊(duì)列（deque）是允許兩端都可以入隊(duì)和出隊(duì)操作的隊(duì)列（隊(duì)頭可以出隊(duì)入隊(duì)，隊(duì)尾也可以出隊(duì)入隊(duì)）。deque 是 “double ended queue” 的簡(jiǎn)稱。
Dequestack = new ArrayDeque<>();//雙端隊(duì)列的線性實(shí)現(xiàn)
Dequequeue = new LinkedList<>();//雙端隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn) 
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
