Java實作棧和隊列

一、什麼是資料結構中的棧和隊列

• 棧

  (Stack)：隻允許在一端進行插入或删除的線性表。遵循後進先出原則（Last In First Out，簡稱LIFO）。

  • 棧頂

    ：允許插入删除元素的一側

  • 棧底

    ：不插入删除元素的那一側

• 隊列

  (Queue)：隻允許在一端進行插入操作，而在另一端進行删除操作的線性表。遵循先進先出原則（First In First Out，簡稱FIFO）。

  • 隊頭

    ：允許删除元素的一側

  • 隊尾

    ：允許插入元素的一側

二、實作思路——連結清單

由于數組具有容量大小限制的缺點，用連結清單實作更加簡單。

節點類Node

要想使用連結清單肯定要有節點類，這裡我們使用泛型來限制節點存儲值的類型

public class Node<E> {
    E value;		// 節點存儲的值
    Node<E> next;   // 下一節點

    public Node(E value) {
        this.value = value;
        next = null;
    }

    // 設定下一節點
    public void setNext(Node<E> next){
        this.next = next;
    }
}
           

棧

棧的特點是隻有一端有資料操作，是以我們隻需要定義一個頭節點即可，讓頭節點處進行資料的增删。

假設開始時棧是這樣

插入元素後，很顯然head要指向新節點，然後新節點要指向舊節點，我們的程式也這樣寫

public class MyStack<E> {
    private Node<E> head;	// 頭結點
    private int size;		// 元素數量

    // 構造函數，初始化頭結點為空，長度為0
    public MyStack(){		
        head  = null;
        size = 0;
    }

    // 入棧操作
    public void push(E e) {
        // 棧為空，初始化頭結點為新元素
        if(size == 0){
            head = new Node<E>(e);
        }else { // 棧不為空，head要指向新節點，新節點要指向舊節點
            Node<E> oldNode = head.next;
            Node<E> newNode = new Node<E>(e);
            newNode.setNext(oldNode);
            head.next = newNode;
        }
        size++;
    }

    // 出棧操作
    public E pop() {
        // 棧為空，抛出異常
        if(size == 0){
            throw new NullPointerException("棧中沒有資料！");
        }
        // 取出頭結點值并丢掉頭結點
        E e = head.value;
        head = head.next;
        size--;
        return e;
    }

    // 檢視元素數量
    public int size(){
        return size;
    }

    // 是否為空
    public boolean isEmpty() {
        return size == 0;
    }
    
    // 清空
    public void clear() {
        while (size > 0) {
            this.pop();
        }
    }
}
           

隊列

隊列的特點是一端插入元素一端删除元素，那麼我們定義兩個節點：頭結點(head)和尾節點(tail)

隊列的思路很好想：尾端插入頭部删除，

// 隊列
public class MyQueue<E> {
    // 頭結點、尾結點、長度
    private Node<E> head;
    private Node<E> tail;
    private int size;

    // 構造函數，初始化頭尾節點為空，長度為0
    public MyQueue() {
        head = tail = null;
        size = 0;
    }

    // 插入元素：尾端插入
    public void pull(E e) {
        // 若插入前為空隊列，則頭尾節點都是該元素
        if(size == 0){
            head = tail = new Node<>(e);
        }else { // 插入前不是空隊列，尾部插入節點
            tail.setNext(new Node<>(e));
            tail = tail.next;
        }
        size++;
    }

    // 删除元素：頭部删除
    public E take() {
        // 空隊列直接抛出異常
        if(size == 0){
            throw new NullPointerException("隊列為空！");
        }
        // 取出元素并抛棄頭結點
        E e = head.value;
        head = head.next;
        
        // 頭結點為空證明隊列中已經沒有元素，是以尾結點也要為null
        if(head == null){
            tail = null;
        }
        size--;
        return e;
    }

    // 傳回長度
    public int size() {
        return size;
    }

    // 是否為空
    public boolean isEmpty() {
        return size == 0;
    }
    
    // 清空
    public void clear() {
        while (size > 0) {
            this.take();
        }
    }
}