文章目錄

1. 堆疊
- 1.1 概念
- 1.2 助解圖題
- 1.3 堆疊的陣列實作
- 1.4 問題
- 1.5 堆疊的單鏈表實作
2. 佇列
- 2.1 概念
- 2.2 問題
- 2.3 佇列的單鏈表實作
- 2.4 陣列實作佇列
- 2.5 回圈佇列
- 2.6 雙端佇列
3. 堆疊和佇列練習題
- 3.1 有效的括號
- 3.2 用佇列實作堆疊
- 3.3 用堆疊實作佇列
- 3.4 實作一個最小堆疊
- 3.5 設計回圈佇列

1. 堆疊

1.1 概念

堆疊：是一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，
特點：堆疊中的資料元素遵循先進后出的原則，但要注意進的同時也可以出，元素不是要全部進展后才能出堆疊
堆疊頂：進行資料插入和洗掉操作的一端
堆疊底：堆疊頂的另一端
壓堆疊：堆疊的插入操作就做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂
出堆疊：堆疊的洗掉操作就叫做出堆疊，出資料在堆疊頂

1.2 助解圖題

助解圖：

手槍的彈夾其實就類似是一個堆疊

在這里插入圖片描述

當我們壓子彈的時候，就是壓堆疊在這里插入圖片描述

當我們上膛后，打槍時，就是出堆疊在這里插入圖片描述

助解題：

題一： 一個堆疊的入堆疊順序是 a、b、c、d、e，該堆疊不可能的出堆疊順序是（） A.edcba B.decba C.dceab D.abcde

結果為：C
題二： 中綴運算式為 a + b * c + ( d * e + f ) * g，那么它的后綴運算式為什么？

結果為：a b c * + d e * f + g * +

方法步驟（快捷方法）：

該方法中將括號的運算子移到括號前面得到的結果就是前綴運算式

本題背景：我們平常使用的運算式一般為中綴運算式，中綴運算式便于人們的理解與計算，而后綴運算式的運算子更方便計算機的運算（如二叉樹、堆疊的方法計算）
題三： 通過堆疊回傳后綴運算式 a b c * + d e * f + g * + 計算的結果

結果為：a + b * c + ( d * e + f ) * g

方法：當引數是數字時就壓堆疊，當引數為運算子時，出堆疊第一個數作為運算子后的引數，出堆疊第二個引數作為運算子前的引數，將結果再壓入堆疊中，

1.3 堆疊的陣列實作

在 Java 中堆疊的底層其實是一個陣列，并且它擁有壓堆疊、出堆疊等等方法，借助這些我們來自己實作一個堆疊

public class MyStack{
    // 定義一個整型的陣列，也可以直接使用泛型
    public int[] elem;
    // 定義陣列已經使用的長度，初始時為0
    public int usedSize;
    // 創建 MyStack 的構造方法
    public MyStack(){
        // 用 Mystack 創建物件時初始化陣列的長度為10
        this.elem=new int[10];
    }
    // 判斷堆疊是否已滿
    public boolean isFull(){
        return usedSize==this.elem.length;
    }
    // 壓堆疊
    public int push(int val){
        if(isFull()){
            // 擴容
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize++]=val;
        return val;
    }
    // 出堆疊
    public int pop(){
        if(empty()){
            throw new RuntimeException("堆疊為空");
        }
        this.usedSize--;
        return this.elem[this.usedSize];
    }
    // 查看堆疊頂元素，不洗掉
    public int peek(){
        if(empty()){
        	throw new RuntimeException("堆疊為空");
        }
        return this.elem[this.usedSize-1];
    }
    // 判斷堆疊是否為空
    public boolean empty(){
        return usedSize==0;
    }
}

1.4 問題

我們上述的堆疊是用陣列實作的，入堆疊和出堆疊的時間復雜度都為 O(1)

那么堆疊能否用單鏈表實作呢？

使用頭插法：入堆疊時間復雜度為 O(1)，出堆疊時間復雜度為 O(1)

使用尾插法：入堆疊時間復雜度為 O(N)，出堆疊時間復雜度為 O(N)

綜上分析，堆疊可以通過單鏈表的頭插頭刪法實作

1.5 堆疊的單鏈表實作

接下來將使用單鏈表實作堆疊，注意要使用頭插頭刪法

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}
public class MyStack{
    Node head=null;
    // 壓堆疊
    public int push(int val){
        Node node=new Node(val);
        node.next = head;
        head = node;
        return head.val;
    }
    // 出堆疊
    public int pop(){
        if(empty()){
            throw new RuntimeException("堆疊為空");
        }
        int val=head.val;
        head=head.next;
        return val;
    }
    // 查看堆疊頂元素，不洗掉
    public int peek(){
        if(empty()){
            throw new RuntimeException("堆疊為空");
        }
        return head.val;
    }
    // 判斷堆疊是否為空
    public boolean empty(){
        return head==null;
    }
}

2. 佇列

2.1 概念

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉操作的特殊線性表，
特點：佇列具有先進先出的特點
對頭：進行洗掉操作的一端
隊尾：進行插入操作的一段

在這里插入圖片描述

2.2 問題

在我們實作佇列前，要思考佇列是靠陣列實作呢還是拿鏈表實作呢？

在 Java 當中，佇列是由 LinkedList 實作的，它的底層是一個雙向鏈表，

對于雙向鏈表：我們只要在尾節點進行入隊操作，在頭節點進行出隊操作就很容易實作
對于單鏈表：我們只要增加一個尾巴節點，然后尾巴節點進行入隊操作，頭節點進行出隊操作也能實作

至于陣列，我們上述通過它實作了堆疊，而堆疊的特點其實是先進后出，與佇列的先進先出原則矛盾，使用陣列來實作佇列會很麻煩，

2.3 佇列的單鏈表實作

根據 Java 中佇列的一些方法，接下來我們來實作自己的佇列

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}
public class MyQueueLinked {
    private Node front;
    private Node rear;
    private int usedSize;
    // 入佇列
    public void offer(int val){
        Node node=new Node(val);
        if(this.front==null){
            this.front=node;
            this.rear=node;
        }else{
            this.rear.next=node;
            this.rear=node;
        }
        this.usedSize++;
    }
    // 出佇列
    public int poll(){
       if(isEmpty()){
           throw new RuntimeException("佇列為空");
       }
       int val=this.front.val;
       if(this.front.next==null){
           this.front=null;
           this.rear=null;
       }else{
           this.front=this.front.next;
       }
        this.usedSize--;
        return val;
    }
    // 得到隊頭元素不洗掉
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("佇列為空");
        }else{
            return this.front.val;
        }
    }
    // 判斷佇列是否為空
    public boolean isEmpty(){
        return this.usedSize==0;
    }
    // 得到佇列長度
    public int size(){
        return this.usedSize;
    }
}

上述佇列是用單鏈表實作的，也叫鏈式佇列，大家也可以自行嘗試一下雙鏈表實作佇列，

2.4 陣列實作佇列

假設現在我們用陣列模擬入佇列和出佇列的模型在這里插入圖片描述

解決方法：

方法一：出隊時，移動陣列將后面的元素往前覆寫（時間復雜度為 O(N)）
方法二：使用回圈的方法，實作回圈佇列（時間復雜度為 O(1)）

2.5 回圈佇列

回圈佇列即陣列使用了回圈的方式，讓陣列方便佇列的入隊和出隊，那么怎么實作呢？模型如下在這里插入圖片描述

front：指向的位置就是佇列的頭，既已經存放資料的第一個下標（洗掉資料一端）
rear：指向的位置就是佇列的尾巴，即可以存放資料的第一個下標（插入資料一端）

問題1：如何判斷 front = rear 時是慷訓是滿？

為了能夠區別是慷訓是滿，我們常假定當 front = rear 時為空，而對于滿的話，我們則會將這個陣列保留一個空的位置，那么當 rear+1 = front 時，則佇列滿了

問題2：當 front 在陣列最后一個位置時，如何再移它到陣列的第一個位置呢？

(下標+1)%陣列長度

接下來讓我們實作回圈佇列

public class MyCircularQueue {
    private int[] elem;
    private int front;
    private int rear;
    public MyCircularQueue(int k){
        this.elem=new int[k+1];
    }
    // 判斷佇列是否滿了
    public boolean isFull(){
        return (this.rear+1)%this.elem.length==this.front;
    }
    // 判斷佇列是否為空
    public boolean isEmpty(){
        return this.front==this.rear;
    }
    // 入隊
    public void enQueue(int val){
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.rear]=val;
        this.rear=(this.rear+1)%this.elem.length;
    }
    // 出隊
    public int deQueue(){
        if(isEmpty()){
            throw new RuntimeException("佇列為空");
        }
        int val=this.elem[this.front];
        this.front=(this.front+1)%this.elem.length;
        return val;
    }
    // 得到隊頭元素
    public int getFront(){
        if(isEmpty()){
            throw new RuntimeException("佇列為空");
        }
        return this.elem[this.front];
    }
    // 得到隊尾元素
    public int getRear(){
        if(isEmpty()){
            throw new RuntimeException("佇列為空");
        }
        if(this.rear==0){
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.rear - 1];
    }
}

注意：

假設一個陣列長度為3，做題時可能人家用例入隊了3次，但是按照上述佇列為滿的方式，我們其實是保留了一個位置是不能存放資料的，因此對于這種題目我們可以將我們的陣列開大一位

2.6 雙端佇列

雙端佇列：是指允許兩端都可以進行入隊和出隊操作的佇列

特點：元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊

雙端佇列較簡單，可以使用雙向鏈表實作，這里就展示一下雙端佇列的模型在這里插入圖片描述

3. 堆疊和佇列練習題

3.1 有效的括號

題目（OJ 鏈接）：

給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串 s ，判斷字串是否有效，

有效字串需滿足：左括號必須用相同型別的右括號閉合，左括號必須以正確的順序閉合，

題解：使用堆疊，遍歷字串，是左括號就進行入堆疊，是右括號就與堆疊頂元素比較，

public boolean isValid(String s) {
    Stack<Character> stack=new Stack<>();
    for(int i=0;i<s.length();i++){
        char ch=s.charAt(i);
        switch(ch){
            case ')':
                if(stack.empty()||stack.pop()!='('){
                    return false;
                }
                break;
            case '}':
                if(stack.empty()||stack.pop()!='{'){
                    return false;
                }
                break;
            case ']':
                if(stack.empty()||stack.pop()!='['){
                    return false;
                }
                break;
            default:
                stack.push(ch);
                break;
        }
    }
    if(stack.empty()){
        return true;
    }
    return false;
}

3.2 用佇列實作堆疊

題目（OJ鏈接）：

請你僅使用兩個佇列實作一個后入先出（LIFO）的堆疊，并支持普通堆疊的全部四種操作（push、top、pop 和 empty），

題解：

由于佇列是先進先出，堆疊是先進后出，故一個佇列無法滿足實作堆疊的能力，而使用兩個佇列，對于入堆疊，我們我只要找到堆疊不為空的佇列進行入隊就行；對于出堆疊，我們只要將不為空的佇列的除最后一個入隊的元素全部轉移到另一個空佇列中，再將留下的元素出隊

代碼：

class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    public MyStack() {
        q1=new LinkedList<>();
        q2=new LinkedList<>();
    }
    // 入堆疊
    public void push(int x) {
        if(!q1.isEmpty()){
            q1.offer(x);
        }else if(!q2.isEmpty()){
            q2.offer(x);
        }else{
            q1.offer(x);
        }
    }
    // 出堆疊
    public int pop() {
        if(empty()){
            throw new RuntimeException("堆疊為空");
        }
        if(!q1.isEmpty()){
            int val1=0;
            while(!q1.isEmpty()){
                val1=q1.poll();
                if(!q1.isEmpty()){
                    q2.offer(val1);
                }
            }
            return val1;
        }else{
            int val2=0;
            while(!q2.isEmpty()){
                val2=q2.poll();
                if(!q2.isEmpty()){
                    q1.offer(val2);
                }
            }
            return val2;
        }
    }
    // 得到堆疊頂元素不洗掉
    public int top() {
        if(empty()){
            throw new RuntimeException("堆疊為空");
        }
        if(!q1.isEmpty()){
            int val1=0;
            while(!q1.isEmpty()){
                val1=q1.poll();
                q2.offer(val1);
            }
            return val1;
        }else{
            int val2=0;
            while(!q2.isEmpty()){
                val2=q2.poll();
                q1.offer(val2);
            }
            return val2;
        }
    }
    // 判斷堆疊是否為空
    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}

3.3 用堆疊實作佇列

題目（OJ 鏈接）：

請你僅使用兩個堆疊實作先入先出佇列，

題解：

我們可以創建兩個堆疊 s1、s2，s1 用來入隊，s2 用來出隊

代碼：

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    public MyQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    // 入隊
    public void push(int x) {
        s1.push(x);
    }
    // 出隊
    public int pop() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    // 回傳隊首元素，不洗掉
    public int peek() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    // 判斷佇列是否為空
    public boolean empty() {
        return s1.empty()&&s2.empty();
    }
}

3.4 實作一個最小堆疊

題目（OJ 鏈接）：

設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的堆疊，

題解：

我們可以創建兩個堆疊，一個堆疊就是用來存盤洗掉元素，另一個就是專門用來存盤最小值的堆疊，注意這個最小值是存盤該元素時該堆疊的最小值

代碼：

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    // 入堆疊
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            if(val<=minStack.peek()){
                minStack.push(val);
            }
        }
    }
    // 出堆疊
    public void pop() {
        int val=stack.pop();
        if(minStack.peek()==val){
            minStack.pop();
        }
    }
    // 得到堆疊頂元素，不洗掉
    public int top() {
        return stack.peek();
    }
    // 得到此時堆疊的最小值
    public int getMin() {
        return minStack.peek();
    }
}

3.5 設計回圈佇列

題目（OJ 鏈接）：

設計你的回圈佇列實作，回圈佇列是一種線性資料結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個回圈，它也被稱為“環形緩沖器”，

題解：

通過 (下標+1)%陣列長度 的方式將陣列形成一個回圈，先設定好陣列為空和為滿的條件，注意防止題目將陣列存滿，開陣列時的大小要注意，

代碼：

class MyCircularQueue {
    private int[] elem;
    private int front;
    private int rear;
    public MyCircularQueue(int k) {
        this.elem=new int[k+1];
    }
    // 入佇列
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.elem[rear]=value;
        this.rear=(this.rear+1)%this.elem.length;
        return true;
    }
    // 出佇列
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.elem.length;
        return true;
    }
    // 得到隊首元素，不洗掉
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.elem[front];
    }
    // 得到隊尾元素，不洗掉
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        if(this.rear==0){
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.rear-1];
    }
    // 判斷佇列是否為空
    public boolean isEmpty() {
        return this.rear==this.front;
    }
    // 判斷佇列是否滿了
    public boolean isFull() {
        return (this.rear+1)%this.elem.length==this.front;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/335538.html

標籤：java

上一篇：【Java系列】玩轉方法——Java中關于方法的那些小東西！

下一篇：SpringMVC學習（二）—— Controller

【資料結構 Java 版】詳解堆疊和佇列的實作

文章目錄

1. 堆疊

1.1 概念

1.2 助解圖題

1.3 堆疊的陣列實作

1.4 問題

1.5 堆疊的單鏈表實作

2. 佇列

2.1 概念

2.2 問題

2.3 佇列的單鏈表實作

2.4 陣列實作佇列

2.5 回圈佇列

2.6 雙端佇列

3. 堆疊和佇列練習題

3.1 有效的括號

3.2 用佇列實作堆疊

3.3 用堆疊實作佇列

3.4 實作一個最小堆疊

3.5 設計回圈佇列