堆疊的認識

堆疊的功能

實作

入堆疊

取堆疊頂元素

出堆疊

堆疊是否為空

佇列的認識

佇列的功能

實作

入佇列

出佇列

取對頭元素

判斷佇列是否為空

堆疊的認識

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，

壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，

出堆疊：堆疊的洗掉操作叫做出堆疊,出資料在堆疊頂

堆疊是一種先進后出的資料結構

堆疊的功能

由于堆疊是一種特殊的資料結構,一次出堆疊的元素只能出最后入堆疊的元素,所以不能通過下標進行隨機查詢,也不能通過下標進行隨機取元素操作,以下是堆疊涉及到的操作

public boolean empty() // 回傳堆疊是否為空，  
public int peek()  // 回傳堆疊頂部的物件，而不從堆疊中洗掉它，  
public int pop() 	// 洗掉堆疊頂部的物件，并將該物件作為此函式的值回傳，  
public void push()  // 入堆疊操作

接下來,就使用 Java 實作以上的方法,在實作功能前,先創建一個陣列用來儲存資料,再創建一個變數 top 記錄當前堆疊頂的元素.

class MyStack{	
    private int[] elem;//陣列存放元素
    private int top;// 堆疊頂指標
	
    public MyStack() {
        this.elem = new int[10];// 初始容量為10
        this.top = 0;
    }
}

實作

入堆疊

從圖中,可以知道,每次入堆疊操作,都在 top 指標處插入資料,且 top 指標自增一次,所以可以寫成在陣列的top位置進行插入資料.

public void push(int item) {
    
     // 可以分為兩步操作
     /*
     this.elem[top] = item;
     this.top++;
     */
    // 也可以一步到位
     this.elem[top++] = item;
}

取堆疊頂元素

這個操作,是不會把堆疊中的元素進行洗掉,所以根據圖片可以看到,要想得到堆疊頂的元素,top 指標要往下走一步,且不能改變 top 的位置,否則下次插入會改變當前堆疊首元素的值,所以可以直接取 top - 1 位置處的元素,既不改變 top,也能拿到堆疊頂元素,不過在 top 為 0 的情況下,也就是堆疊為空的情況下,我們需要進行處理,否則會產生陣列越界例外.

??public int peek() {
    if (this.top == 0) {
        throw new UnsupportedOperationException("堆疊中元素為空!");// 手動拋一個例外 提示
    }
    return this.elem[this.top - 1]; // 回傳top - 1 的元素,不改變 top 本身
}

出堆疊

出堆疊操作,使用的是覆寫方法,將當前 top 指標往下一位,等下次添加元素的時候就能覆寫當前要洗掉的元素,即使沒有要添加的元素,由于 top 指標變了,當前其它操作也訪問不到洗掉的元素,所以移動 top 指標既可達到我們邏輯上的洗掉.

public int pop() {
    if (this.top == 0) {
        throw new UnsupportedOperationException("堆疊頂元素為空");
    }
    return this.elem[--this.top];// 將 top 指標下移一位,切回傳當前的要洗掉的元素
}

堆疊是否為空

判斷當前 top 是否等于 0 即可

public boolean empty() {
    return this.top == 0;
}

堆疊的使用

實作完方法之后,接下來簡單了解一下堆疊的使用方法

public static void main(String[] args) {
        MyStack myStack = new MyStack();
        Stack<Integer> stack = new Stack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        while (!myStack.empty()){
            System.out.print(myStack.pop() + " ");
        }
}

由于添加的順序是 1 -> 2 -> 3 -> 4 -> 5 , 根據后進先出的特性,輸出應該為 5 -> 4 -> 3 -> 2 -> 1

以上就是關于如何使用 JAVA 實作堆疊的所有內容,接下來我們去學習一下另外一種資料結構 <佇列>

佇列的認識

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表

入佇列：進行插入操作的一端稱為隊尾（Tail）

出佇列：進行洗掉操作的一端稱為隊頭（Head）

佇列是一個具有先進先出特性的資料結構

佇列的功能

佇列這種特殊的資料結構的特性,在現實生活中很多也很常見,拿火車站買票來說,先到售票視窗前的人能先買到票,后到購票視窗的人只能排隊等先到的人買完才能買,佇列也是,只有先入佇列的元素出佇列之后,后面入佇列的元素才能出佇列,不允許隨機訪問元素

public boolean isEmpty() // 判斷佇列是否為空
public void offer(E e)   // 入佇列,則將指定的元素插入到此佇列中，  
public int peek() // 回傳隊頭元素
public int poll() // 出佇列,洗掉隊頭元素,并回傳改值

上面就是佇列的常用方法,在實作功能前,我們先考慮是用陣列來實作佇列,還是用鏈表來實作比較好?我們可以比較一下兩種結構的時間復雜度

入佇列:入佇列的時候使用的是尾插法

陣列:用陣列實作尾插法 , 使用一個指標記錄尾部 , 進行插入時直接通過尾部指標進行插入 , 不需要格外的遍歷 , 時間復雜度為 O(1).

鏈表:用鏈表實作尾插法 , 使用一個尾節點記錄尾部 , 進行插入時直接通過尾節點進行插入,不需要格外的遍歷 , 時間復雜度為 O(1)

出佇列:出佇列的時候使用的是頭刪法

陣列:用陣列實作頭刪法 , 需要將后面的資料覆寫前面的資料 , 時間復雜度是O(N)

鏈表:用鏈表實作頭刪法,只需要使用一個頭節點記錄對頭位置 , 洗掉時將頭節點指向當前對頭的下一個節點即可

由此得出,在實作佇列使用的存盤方式時,使用鏈表的時間復雜度更低,那就先創建一個節點類,用來存盤資料及下一個節點的地址

public class MyQueue {
    
    // 可以使用內部類,定義在實作類里面
    private static class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    private Node head;// 記錄頭節點
    private Node tail; // 記錄尾節點
}

實作

入佇列

入佇列分為兩種情況

第一次入佇列,佇列是為空的,需要先將頭節點和尾節點都指向當前的節點
非第一次佇列,需要將 tail 的 next 指標指向當前插入的節點,且 tail 節點也要更新成當前節點

public void offer(int val) {
    // 創建新節點
    Node node = new Node(val);
    //尾插法  需要判斷是不是第一次插入
    if (isEmpty()) {
        this.head = node;
        this.tail = node;
        return;
    }
    this.tail.next = node;
    this.tail = node;
}

出佇列

出佇列也分兩種情況

佇列為空:如果佇列為空,呼叫出佇列的方法時,我們應該拋出一個例外提示
佇列不為空:佇列不為空,采用頭刪法,將 head 節點更新成 head.next 的節點,此時就能達到洗掉隊頭元素的效果了.

public int poll() {
    //判斷是否為空佇列的
    if (isEmpty()) {
        throw new UnsupportedOperationException("佇列為空");
    }
    // 記錄要洗掉對頭的元素
    int ret = this.head.val;
    // 更改 head 指向
    this.head = this.head.next;
    return ret;
}

取對頭元素

我們在前面使用了 head 參考,記錄了隊頭,所以只需要放回 head 參考的值即可,需要判斷佇列是否為空,為空的話需要拋出例外提示

public int peek() {
    //不要移動first
    if (isEmpty()) {
        throw new UnsupportedOperationException("鏈表為空");
    }
    return this.head.val;
}

判斷佇列是否為空

判斷 head 參考或者 tail 參考是否 == null 即可

public boolean isEmpty() {
    return this.head == null;
}

佇列的使用

簡單添加幾個資料并輸出,測驗佇列能否正常使用

public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        myQueue.offer(4);
        myQueue.offer(5);
        while (!myQueue.isEmpty()){
            System.out.print(myQueue.poll() + " ");
        }
}

添加元素順序為 1 -> 2 -> 3 -> 4 -> 5 , 根據先進先出的特性, 輸出的順序也應該為 1 -> 2 -> 3 -> 4 -> 5