數據結構-隊列 - Onlywjy－IT工程師數位筆記本

文章出處

隊列

隊列（queue）簡稱隊，它同堆棧一樣，也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除。在隊列中把插入數據元素的一端稱為隊尾（rear），刪除數據元素的一端稱為隊首（front）。向隊尾插入元素稱為進隊或入隊，新元素入隊后成為新的隊尾元素；從隊列中刪除元素稱為離隊或出隊，元素出隊后，其后續元素成為新的隊首元素。

由于隊列的插入和刪除操作分別在隊尾和隊首進行，每個元素必然按照進入的次序離隊，也就是說先進隊的元素必然先離隊，所以稱隊列為先進先出表（First In First Out,簡稱 FIFO）。隊列結構與日常生活中排隊等候服務的模型是一致的，早進入隊列的人，早得到服務并從隊首離開；后到來的人只能排在隊列的后，后得到服務并后離開。

Queue 接口

代碼實現如下：

package com.wjy.Data_Structure.queue;

public interface Queue {

    /**
     * 返回隊列的大小
     *
     * @return
     */
    public int getSize();

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

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

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

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

異常類定義

package com.wjy.Data_Structure.queue;

public class QueueEmptyException extends RuntimeException {

    private static final long serialVersionUID = 1L;

    public QueueEmptyException(String err) {
        super(err);
    }
}

1.隊列的順序存儲實現

在隊列的順序存儲實現中，我們可以將隊列當作一般的表用數組加以實現，但這樣做的效果并不好,當我們刪除隊首元素時候必須將數組中所有其他元素都向前移動一個位置。為了提高運算的效率,設想數組 A[0.. capacity-1]中的單元不是排成一行，而是圍成一個圓環，即 A[0]接在 A[capacity-1]的后面。這種意義下的數組稱為循環數組，如圖所示：

代碼實現如下：

package com.wjy.Data_Structure.queue;

public class QueueArray implements Queue {
    private static final int CAP = 7; // 隊列默認大小
    private Object[] elements; // 數據元素數組
    private int capacity; // 數組的大小
    private int front; // 隊首指針，指向隊首
    private int rear; // 隊尾指針，指向隊尾后一個位置

    public QueueArray() {
        this(CAP);
    }

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

    private void expandSpace() {
        Object[] a = new Object[elements.length * 2];
        int i = front, j = 0;
        while (i != rear) {
            a[j++] = elements[i];
            i = (i + 1) % capacity;
        }
        elements = a;
        capacity = elements.length;
        front = 0;
        rear = j;

    }

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

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

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

    }

    @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("錯誤：隊列為空");
        return elements[front];
    }

}

2.隊列的鏈式存儲實現

隊列的鏈式存儲可以使用單鏈表來實現。這里采用帶頭結點的單鏈表結構。如圖所示。隊首指針指向隊首元素的前一個結點，即始終指向鏈表空的頭結點，隊尾指針指向隊列當前隊尾元素所在的結點。當隊列為空時，隊首指針與隊尾指針均指向空的頭結點。

代碼實現如下：

package com.wjy.Data_Structure.queue;

import com.wjy.Data_Structure.linearlist.common.SLNode;

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; // 如果隊列為空，rear指向頭結點
        return p.getData();
    }

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

}

文章列表