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

成都創(chuàng)新互聯(lián)公司長期為上1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為通道企業(yè)提供專業(yè)的成都網(wǎng)站制作、成都網(wǎng)站設(shè)計，通道網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

一、棧（Stack）

1、定義

2、順序結(jié)構(gòu)模擬實現(xiàn)棧和常用方法

（1）.棧的順序存儲

（2）.基本方法

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

（1）.對比

4、區(qū)分概念

（1）.棧

（2）.虛擬機(jī)棧

（3）.棧幀

二、隊列（Queue）

1、定義

2、鏈?zhǔn)浇Y(jié)構(gòu)模擬實現(xiàn)隊列及常用方法

（1）.隊列的鏈?zhǔn)浇Y(jié)構(gòu)初始化

（2）.常用方法

[1].入隊

[2].出隊

[3].獲取隊頭元素

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

[5]. 檢測是否為空

3、循環(huán)隊列

（1）.循環(huán)隊列的數(shù)組下標(biāo)

（2）.區(qū)分空的循環(huán)隊列和滿的循環(huán)隊列

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

5、雙端隊列（Deque）

（1）.定義

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

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

一、棧（Stack） 1、定義

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

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

出棧：棧的元素刪除操作

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

該棧的底層邏輯是一組地址連續(xù)的存儲單元，用來從棧底開始存放元素

（2）.基本方法

[1]. 構(gòu)造一個空的棧。

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].獲取個數(shù)

int size() 獲取棧中有效元素個數(shù)

public int size(){
    return usedSize;
}

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

相比于順序結(jié)構(gòu)的棧，鏈?？梢赃M(jìn)行多個棧共享存儲空間以提高內(nèi)存利用率并且?guī)缀醪粫嬖跅M的情況。此外在時間復(fù)雜度上順序棧和鏈棧相同均為O(1)。

在空間上順序棧需要事先確定一個固定的長度，因此存取時很方便，但是可能會存在空間浪費(fèi)。鏈?zhǔn)綏Ｔ诳臻g上通過指針域連接下一個元素，雖然增加了一點(diǎn)內(nèi)存的消耗但是棧的長度可以是無限的且不會存在空間浪費(fèi)。

所以如果棧在使用過程中元素個數(shù)變化大,最好是用鏈棧。反之,如果元素個數(shù)的變化在一定范圍內(nèi),建議使用順序棧。

4、區(qū)分概念（1）.棧

是一種數(shù)據(jù)元素先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)

（2）.虛擬機(jī)棧

具有特殊作用的一塊內(nèi)存空間。jvm為了對數(shù)據(jù)進(jìn)行更好的管理，將內(nèi)存按照不同的需求劃分出來的結(jié)構(gòu)。

棧區(qū)：線程私有的，棧區(qū)中存放的是函數(shù)調(diào)用相關(guān)的一些信息，主要是棧幀。

當(dāng)棧區(qū)中內(nèi)存空間不足時，會拋出StackOverflowException；當(dāng)中的元素（棧幀）是按照數(shù)據(jù)結(jié)構(gòu)中的棧的特性來實現(xiàn)的

（3）.棧幀

一種結(jié)構(gòu)，這種結(jié)構(gòu)與函數(shù)調(diào)用相關(guān)的，內(nèi)部：局部變量表、操作數(shù)棧。

每個方法在運(yùn)行時，jvm都會創(chuàng)建一個棧幀，然后將棧幀壓入到虛擬機(jī)棧中。當(dāng)方法調(diào)用結(jié)束時，該方法對應(yīng)的棧幀會從虛擬機(jī)棧中出棧。

注意：每個方法的棧幀中結(jié)構(gòu)都是一樣，大小可能不同，但是棧幀的大小在程序編譯時就已經(jīng)確定好。

二、隊列（Queue） 1、定義

只允許在一端進(jìn)行數(shù)據(jù)插入（這一端稱為隊尾Head/Front），在另一端進(jìn)行數(shù)據(jù)刪除（這一端稱為隊尾Tail/Rear）的特殊線性表。數(shù)據(jù)元素先進(jìn)先出。

入隊：隊列的數(shù)據(jù)元素插入操作

出隊：隊列的數(shù)據(jù)元素刪除操作

2、鏈?zhǔn)浇Y(jié)構(gòu)模擬實現(xiàn)隊列及常用方法（1）.隊列的鏈?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是個接口，底層是通過鏈表實現(xiàn)的

（2）.常用方法

[1].入隊

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].出隊

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

[3].獲取隊頭元素

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

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

public int getUsedSize() {
    return usedSize;
}

[5]. 檢測是否為空

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

3、循環(huán)隊列

循環(huán)隊列通常使用數(shù)組實現(xiàn),我們把隊列的這種頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊列。

當(dāng)隊頭指針front = array.length-1后，再前進(jìn)x個位置就自動到下一個循環(huán)，這可以利用除法取余實現(xiàn)。

初始時：front =rear=0。

判空：front=rear

判滿：(rear+1)%array.length=front

隊首指針退x：front = (front + array.length - x) % array.length

隊尾指針進(jìn)x：rear = (rear + x) % array.length

隊列長度：len=(rear - front + array.length) % array.length

（1）.循環(huán)隊列的數(shù)組下標(biāo)

[1].下標(biāo)在最后一個時再往后

index=(index+x)%arr.length

[2].下標(biāo)在第一個時再往后

(index+arr.length-x)%arr.length

（2）.區(qū)分空的循環(huán)隊列和滿的循環(huán)隊列

[1].添加usedSize屬性

我們可以創(chuàng)建一個成員變量 usedSize，只有當(dāng) usedSize==隊列長度時判滿，當(dāng) usedSize==0 為空隊列。

[2].使用標(biāo)記

類型中增設(shè)flag數(shù)據(jù)成員，以區(qū)分是隊滿還是隊空。

flag 等于0時，如果刪除后 front = = rear ，則為隊空；

flag 等于 1 時，如果插入后 front == rear ，則為隊滿。

[3].保留一個位置

為了區(qū)分隊空和隊滿，我們保留最后一個位置。

如下圖,當(dāng)rear=front便認(rèn)為是隊空，當(dāng)rear+1=front時認(rèn)為是隊滿。

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

在空間上：鏈?zhǔn)疥犃械臄?shù)據(jù)存儲是通過指針域連接的，會產(chǎn)生一些空間上的開銷；而循環(huán)隊列有一個固定的長度，所以在存儲空間上存在浪費(fèi)，因此鏈隊更加的靈活。

在時間上：兩者數(shù)據(jù)操作的時間復(fù)雜度都是O(1)。鏈?zhǔn)疥犃幸驗槭峭ㄟ^指針域連接的，所以每次添加和刪除結(jié)點(diǎn)都會存在一些時間消耗，而循環(huán)隊列是先申請一個固定空間，使用時不釋放，如果入隊頻繁，則兩者還是有細(xì)微差異。

因此在確定隊列大值時，使用循環(huán)隊列；無法確定隊列的長度時，則用鏈?zhǔn)疥犃小?/p>5、雙端隊列（Deque）（1）.定義

雙端隊列（deque）是允許兩端都可以入隊和出隊操作的隊列（隊頭可以出隊入隊，隊尾也可以出隊入隊）。deque 是 “double ended queue” 的簡稱。

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

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

Dequestack = new ArrayDeque<>();//雙端隊列的線性實現(xiàn)
Dequequeue = new LinkedList<>();//雙端隊列的鏈?zhǔn)綄崿F(xiàn)

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

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

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

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

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