【資料結構】——佇列 (鏈佇列和基于Java的運算實作)

目錄

鏈佇列

基本運算實作

鏈佇列

概述：一種限制在表頭洗掉和表尾插入操作的單鏈表，

圖示：

基本運算實作

//鏈表結點類
public class QueueNode {
    //資料域
    private Object data;
    //指標域
    private QueueNode next;

    public QueueNode() {
    }

    public QueueNode(Object data, QueueNode next) {
        this.data = data;
        this.next = next;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public QueueNode getNext() {
        return next;
    }

    public void setNext(QueueNode next) {
        this.next = next;
    }
}

public class LinkQueue {
    //定義隊頭指標
    QueueNode front = new QueueNode();
    //定義隊尾指標
    QueueNode rear = new QueueNode();

    //構造空佇列
    public void InitQueue() {
        //尾指標指向頭結點
        rear = front;
        rear.setNext(null);
    }

    //判隊空
    public boolean QueueEmpty() {
        //頭尾指標相等佇列為空
        return rear == front;
    }

    //入佇列
    public void EnQueue(Object x) {
        //申請新結點
        QueueNode queueNode = new QueueNode();
        //資料域賦值
        queueNode.setData(x);
        //指標域置空
        queueNode.setNext(null);
        //新結點鏈到原隊尾結點之后
        rear.setNext(queueNode);
        //隊尾指標指向新的隊尾結點
        rear = queueNode;
    }

    //取隊頭元素
    public Object GetFront() {
        //判斷佇列是否為空
        if (QueueEmpty()) {
            System.out.println("Queue underflow!");
            return null;
        } else {
            //回傳原隊頭元素值
            return front.getNext().getData();
        }
    }

    //出佇列
    public Object DeQueue() {
        //判斷佇列是否為空
        if (QueueEmpty()) {
            System.out.println("Queue underflow!");
            return null;
        } else {
            //申請新結點
            QueueNode queueNode;
            //新結點指向頭結點
            queueNode = front;
            //頭指標指向原隊頭結點
            front = front.getNext();
            //回傳原隊頭結點的資料值
            return queueNode.getData();
        }
    }

    //遍歷佇列
    public void LinkQueueShow() {
        //申請新結點
        QueueNode p;
        //新結點指向頭結點
        p = front;
        //定義一個狀態值
        int i = -1;
        //回圈輸出佇列元素結點值
        while (p != null) {
            //跳過輸出為null的頭結點
            if (i == -1) {
                i++;
                p = p.getNext();
            }
            System.out.println(p.getData());
            //移動指標，使其指向下一個結點
            p = p.getNext();
        }
    }
}

public class LinkQueueTest {
    public static void main(String[] args) {
        //創建鏈佇列物件
        LinkQueue linkQueue = new LinkQueue();

        //構造空佇列
        linkQueue.InitQueue();
        //判隊空
        boolean b = linkQueue.QueueEmpty();
        System.out.println("佇列是否為空：" + b);

        //入佇列
        linkQueue.EnQueue("qq");
        linkQueue.EnQueue("ww");
        linkQueue.EnQueue("ee");
        linkQueue.EnQueue("rr");
        //遍歷佇列
        System.out.println("遍歷佇列：");
        linkQueue.LinkQueueShow();
        //取隊頭元素
        Object o = linkQueue.GetFront();
        System.out.println("隊頭元素為：" + o);
        System.out.println();

        //出佇列
        linkQueue.DeQueue();
        linkQueue.DeQueue();
        //遍歷佇列
        System.out.println("遍歷佇列：");
        linkQueue.LinkQueueShow();
        //取隊頭元素
        Object o1 = linkQueue.GetFront();
        System.out.println("隊頭元素為：" + o1);
        //判隊空
        boolean b1 = linkQueue.QueueEmpty();
        System.out.println("佇列是否為空：" + b1);
    }
}

運行結果：