　1.隊列的介紹

　　隊列（queue ）簡稱隊，它同堆棧一樣，也是一種運算受限的線性表，其限制是僅允許
在表的一端進行插入，而在表的另一端進行刪除。在隊列中把插入數據元素的一端稱為隊尾
rear，刪除數據元素的一端稱為隊首（front））。向隊尾插入元素稱為進隊或入隊，新元素
入隊后成為新的隊尾元素；從隊列中刪除元素稱為離隊或出隊，元素出隊后，其后續元素成
為新的隊首元素。
　　由于隊列的插入和刪除操作分別在隊尾和隊首進行，每個元素必然按照進入的次序離
隊，也就是說先進隊的元素必然先離隊，所以稱隊列為先進先出表（First In First Out,簡稱
FIFO）。隊列結構與日常生活中排隊等候服務的模型是一致的，最早進入隊列的人，最早得
到服務并從隊首離開；最后到來的人只能排在隊列的最后，最后得到服務并最后離開。

1.1隊列的抽象定義

public interface Queue {
    /**
     *返回隊列大小
     */
    public int getSize();

    /**
     * 判斷隊列是否為空
     */
    public  boolean isEmpty();

    /**
     *數據元素e進入隊列
     */
    public void enqueue(Object e);

    /**
     * 隊首出隊元素
     */
    public Object dequeue() throws QueueEmptyException;

    /**
     *取隊首元素
     */
    public Object peek() throws QueueEmptyException;
}

1.2隊列的順序存儲實現

　　在隊列的順序存儲實現中，我們可以將隊列當作一般的表用數組加以實現，但這樣做的
效果并不好。盡管我們可以用一個指針 last 來指示隊尾，使得 enqueue 運算可在Ο(1)時間內
完成，但是在執行 dequeue 時，為了刪除隊首元素，必須將數組中其他所有元素都向前移動
一個位置。這樣，當隊列中有 n 個元素時，執行 dequeue 就需要Ο(n)時間。
為了提高運算的效率，我們用另一種方法來表達數組中各單元的位置關系。設想數組
A[0.. capacity-1]中的單元不是排成一行，而是圍成一個圓環，即 A[0]接在 A[capacity-1]的后
面。這種意義下的數組稱為循環數組，如圖 4-3 所示。

　　用循環數組實現的隊列稱為循環隊列，我們將循環隊列中從隊首到隊尾的元素按逆時針
方向存放在循環數組中一段連續的單元中。并且直接用隊首指針 front 指向隊首元素所在的
單元，用隊尾指針 rear 指向隊尾元素所在單元的后一個單元。如圖 4-3 所示，隊首元素存儲
在數組下標為 0 的位置，front=0；隊尾元素存儲在數組下標為 2 的位置，rear=3。
當需要將新元素入隊時，可在隊尾指針指示的單元中存入新元素，并將隊尾指針 rear 按
逆時針方向移一位。出隊操作也很簡單，只要將隊首指針 front 依逆時針方向移一位即可。
容易看出，用循環數組來實現隊列可以在Ο(1)時間內完成 enqueue 和 dequeue 運算。執行一
系列的入隊與出隊運算，將使整個隊列在循環數組中按逆時針方向移動。
　　當然隊首和隊尾指針也可以有不同的指向，例如也可以用隊首指針 front 指向隊首元素
所在單元的前一個單元，或者用隊尾指針 rear 指向隊尾元素所在單元的方法來表示隊列在
循環數組中的位置。但是不論使用哪一種方法來指示隊首與隊尾元素，我們都要解決一個細
節問題，即如何表示滿隊列和空隊列。
　　下面以圖 4-3 所示的表示方法來說明這個問題。在圖 4-3 中用隊首指針front指向隊首元
素所在的單元，用隊尾指針rear指向隊尾元素所在單元的后一個單元。如此在圖 4-4（b）中
所示循環隊列中，隊首元素為e 0 ，隊尾元素為e 3 。當e 4 、e 5 、e 6 、e 7 相繼進入隊列后，如圖 4-4
（c）所示，隊列空間被占滿，此時隊尾指針追上隊首指針，有rear = front。反之，如果從圖
4-4（b）所示的狀態開始，e 0 、e 1 、e 2 、e 3 相繼出隊，則得到空隊列，如圖 4-4（a）所示，此
時隊首指針追上隊尾指針，所以也有front = rear。可見僅憑front與rear是否相等無法判斷隊

java數組實現：

public class QueueArray implements Queue {

    private static final int CAP = 7; //隊列默認大小
    private Object[] elements;         //數據元素數組
    private int capacity;               //數組的大小，elements.length
    private int front;                  //隊首指針，指向隊首
    private int rear;                   //隊尾元素，只想隊尾后一個位置

    public QueueArray() {
        this(CAP);
    }

    public QueueArray(int cap) {
        capacity = cap + 1;
        elements = new Object[capacity];
        front = rear = 0;
    }

    @Override
    public int getSize() {
        return (rear - front + capacity) % capacity;
    }

    @Override
    public boolean isEmpty() {
        return rear == front;
    }

    @Override
    public void enqueue(Object e) {
        if (getSize() == capacity - 1) {
            expandSpace();
        } else {
            elements[rear] = e;
            rear = (rear + 1) % capacity;
        }
    }

    private void expandSpace() {
        Object[] a = new Object[elements.length * 2];
        int i = front;
        int j = 0;
        while (i != rear) {
            a[j++] = elements[i];
            i = (i + 1) % capacity;
        }
        elements = a;
        capacity = elements.length;
        front = 0;
        rear = j; //設置新的隊首、隊尾指針
    }

    @Override
    public Object dequeue() throws QueueEmptyException {
        if (isEmpty()) {
            throw new QueueEmptyException("錯誤：隊列為空");
        }
        Object obj = elements[front];
        elements[front] = null;
        front = (front + 1) % capacity;
        return obj;
    }

    @Override
    public Object peek() throws QueueEmptyException {
        if (isEmpty()) {
            throw new QueueEmptyException("錯誤：隊列為空");
        }
        Object obj = elements[front];
        return obj;
    }
}

1.3隊列的鏈式存儲實現

　　隊列的鏈式存儲可以使用單鏈表來實現。為了操作實現方便，這里采用帶頭結點的單鏈
表結構。根據單鏈表的特點，選擇鏈表的頭部作為隊首，鏈表的尾部作為隊尾。除了鏈表頭
結點需要通過一個引用來指向之外，還需要一個對鏈表尾結點的引用，以方便隊列的入隊操
作的實現。為此一共設置兩個指針，一個隊首指針和一個隊尾指針，如圖 4-5 所示。隊首指
針指向隊首元素的前一個結點，即始終指向鏈表空的頭結點，隊尾指針指向隊列當前隊尾元
素所在的結點。當隊列為空時，隊首指針與隊尾指針均指向空的頭結點。

java鏈表實現：

public class QueueSLinked implements Queue {
    private SLNode front;
    private SLNode rear;
    private int size;

    public QueueSLinked() {
        this.front = new SLNode();
        this.rear = front;
        this.size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void enqueue(Object e) {
        SLNode p=new SLNode(e,null);
        rear.setNext(p);
        rear=p;
        size++;
    }

    @Override
    public Object dequeue() throws QueueEmptyException {
        if (size<1)
            throw  new QueueEmptyException("錯誤：隊列為空");
        SLNode p = front.getNext();
        front.setNext(p.getNext());
        size--;
        if (size<1)
            rear=front;//如果隊列為空，
        return p.getData();
    }

    @Override
    public Object peek() throws QueueEmptyException {
        if (size<1)
            throw  new QueueEmptyException("錯誤：隊列為空");
        return front.getNext().getData();
    }
}

posted on 2020-04-30 21:24 duan2 閱讀(349) 評論(0) 收藏舉報

刷新頁面返回頂部

導航

1.隊列的介紹

1.1隊列的抽象定義

1.2隊列的順序存儲實現

1.3隊列的鏈式存儲實現

　1.隊列的介紹