目錄

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

一、棧（Stack）

1、定義

2、順序結構模擬實現棧和常用方法

（1）.棧的順序存儲

（2）.基本方法

3、棧的鏈式結構與順序結構對比

（1）.對比

4、區分概念

（1）.棧

（2）.虛擬機棧

（3）.棧幀

二、隊列（Queue）

1、定義

2、鏈式結構模擬實現隊列及常用方法

（1）.隊列的鏈式結構初始化

（2）.常用方法

[1].入隊

[2].出隊

[3].獲取隊頭元素

[4].獲取有效元素個數

[5]. 檢測是否為空

3、循環隊列

（1）.循環隊列的數組下標

（2）.區分空的循環隊列和滿的循環隊列

4、鏈式結構隊列和循環隊列的比較

5、雙端隊列（Deque）

（1）.定義

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

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

---

一、棧（Stack） 1、定義

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

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

出棧：棧的元素刪除操作

2、順序結構模擬實現棧和常用方法 （1）.棧的順序存儲

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

（2）.基本方法

[1]. 構造一個空的棧。

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].獲取個數

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

public int size(){
    return usedSize;
}

3、棧的鏈式結構與順序結構對比 （1）.對比

相比于順序結構的棧，鏈棧可以進行多個棧共享存儲空間以提高內存利用率并且幾乎不會存在棧滿的情況。此外在時間復雜度上順序棧和鏈棧相同均為O(1)。

在空間上順序棧需要事先確定一個固定的長度，因此存取時很方便，但是可能會存在空間浪費。鏈式棧在空間上通過指針域連接下一個元素，雖然增加了一點內存的消耗但是棧的長度可以是無限的且不會存在空間浪費。

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

4、區分概念 （1）.棧

是一種數據元素先進后出的數據結構

（2）.虛擬機棧

具有特殊作用的一塊內存空間。jvm為了對數據進行更好的管理，將內存按照不同的需求劃分出來的結構。

棧區：線程私有的，棧區中存放的是函數調用相關的一些信息，主要是棧幀。

當棧區中內存空間不足時，會拋出StackOverflowException；當中的元素（棧幀）是按照數據結構中的棧的特性來實現的

（3）.棧幀

一種結構，這種結構與函數調用相關的，內部：局部變量表、操作數棧。

每個方法在運行時，jvm都會創建一個棧幀，然后將棧幀壓入到虛擬機棧中。當方法調用結束時，該方法對應的棧幀會從虛擬機棧中出棧。

注意：每個方法的棧幀中結構都是一樣，大小可能不同，但是棧幀的大小在程序編譯時就已經確定好。

二、隊列（Queue） 1、定義

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

入隊：隊列的數據元素插入操作

出隊：隊列的數據元素刪除操作

2、鏈式結構模擬實現隊列及常用方法 （1）.隊列的鏈式結構初始化

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是個接口，底層是通過鏈表實現的

（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].獲取有效元素個數

public int getUsedSize() {
    return usedSize;
}

[5]. 檢測是否為空

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

3、循環隊列

循環隊列通常使用數組實現,我們把隊列的這種頭尾相接的順序存儲結構稱為循環隊列。

當隊頭指針front = array.length-1后，再前進x個位置就自動到下一個循環，這可以利用除法取余實現。

初始時：front =rear=0。

判空：front=rear

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

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

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

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

（1）.循環隊列的數組下標

[1].下標在最后一個時再往后

index=(index+x)%arr.length

[2].下標在第一個時再往后

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

（2）.區分空的循環隊列和滿的循環隊列

[1].添加usedSize屬性

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

[2].使用標記

類型中增設flag數據成員，以區分是隊滿還是隊空。

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

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

[3].保留一個位置

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

如下圖,當rear=front便認為是隊空，當rear+1=front時認為是隊滿。

4、鏈式結構隊列和循環隊列的比較

在空間上：鏈式隊列的數據存儲是通過指針域連接的，會產生一些空間上的開銷；而循環隊列有一個固定的長度，所以在存儲空間上存在浪費，因此鏈隊更加的靈活。

在時間上：兩者數據操作的時間復雜度都是O(1)。鏈式隊列因為是通過指針域連接的，所以每次添加和刪除結點都會存在一些時間消耗，而循環隊列是先申請一個固定空間，使用時不釋放，如果入隊頻繁，則兩者還是有細微差異。

因此在確定隊列大值時，使用循環隊列；無法確定隊列的長度時，則用鏈式隊列。

5、雙端隊列（Deque） （1）.定義

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

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

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

Dequestack = new ArrayDeque<>();//雙端隊列的線性實現
Dequequeue = new LinkedList<>();//雙端隊列的鏈式實現

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

文章標題：數據結構——棧和隊列-創新互聯
文章URL：http://vcdvsql.cn/article36/ceoppg.html

成都網站建設公司_創新互聯，為您提供營銷型網站建設、動態網站、定制開發、網站改版、App開發、服務器托管

廣告

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