數(shù)據(jù)結(jié)構(gòu)——棧和隊(duì)列-創(chuàng)新互聯(lián)

成都創(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ù)；打造開放共贏平臺(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)和眾多成功案例,為您定制開發(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ì)列均可使用該接口

一、棧（Stack） 1、定義

棧是一種特殊的線性組，只允許在一端進(jìn)行插入和刪除元素（這一端稱為棧頂，另一端稱為棧底）。數(shù)據(jù)元素遵循先進(jìn)后出的原則。

入棧（壓棧）：棧的元素插入操作

出棧：棧的元素刪除操作

2、順序結(jié)構(gòu)模擬實(shí)現(xiàn)棧和常用方法（1）.棧的順序存儲(chǔ)

該棧的底層邏輯是一組地址連續(xù)的存儲(chǔ)單元，用來(lá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;
}

3、棧的鏈?zhǔn)浇Y(jié)構(gòu)與順序結(jié)構(gòu)對(duì)比（1）.對(duì)比

相比于順序結(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ù)元素刪除操作

2、鏈?zhǔn)浇Y(jié)構(gòu)模擬實(shí)現(xiàn)隊(duì)列及常用方法（1）.隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)初始化

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）.常用方法

[1].入隊(duì)

public void offer(int val){
    Node node=new Node(val);
    if(head==null){
        head=node;
        last=node;
    }else{
        last.next=node;
        last=node;
    }
    usedSize++;
}

[2].出隊(duì)

public int poll(){
    if(empty()){
        throw new EmptyException("隊(duì)列為空?。?！");
    }
    int ret=head.val;
    head=head.next;
    if(head==null){
        last=null;
    }
    usedSize--;
    return ret;
}

[3].獲取隊(duì)頭元素

public int peek(){
    if(empty()){
        throw new EmptyException("隊(duì)列為空！?。?);
    }
    return head.val;
}

[4].獲取有效元素個(gè)數(shù)

public int getUsedSize() {
    return usedSize;
}

[5]. 檢測(cè)是否為空

public boolean empty(){
    return first == null;
}

3、循環(huán)隊(duì)列

循環(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）.循環(huán)隊(duì)列的數(shù)組下標(biāo)

[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ì)滿。

4、鏈?zhǔn)浇Y(jié)構(gòu)隊(duì)列和循環(huán)隊(duì)列的比較

在空間上：鏈?zhǔn)疥?duì)列的數(shù)據(jù)存儲(chǔ)是通過(guò)指針域連接的，會(huì)產(chǎn)生一些空間上的開銷；而循環(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)稱。

（2）.Deque是一個(gè)接口，使用時(shí)必須創(chuàng)建LinkedList對(duì)象

（3）.Deque接口使用較多，棧和隊(duì)列均可使用該接口

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)查看詳情吧

文章標(biāo)題：數(shù)據(jù)結(jié)構(gòu)——棧和隊(duì)列-創(chuàng)新互聯(lián)
文章URL：http://muchs.cn/article36/ceoppg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營(yíng)銷型網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、定制開發(fā)、網(wǎng)站改版、App開發(fā)、服務(wù)器托管

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容