前言
- 堆疊
  - 概念
  - 堆疊的設計
  - 編碼實作
  - 小結
- 佇列
  - 概念
  - 佇列的設計
  - 編碼實作
- 雙端佇列
  - 概念
  - 設計
  - 編碼
- 回圈佇列
  - 回圈佇列
  - 回圈雙端佇列
- 宣告

前言

堆疊

概念

什么是堆疊？

**堆疊 **：是一種特殊的線性表，只能在一端進行操作

入堆疊：往堆疊中添加元素的操作，一般叫做push

出堆疊：從堆疊中移除元素的操作，一般叫做pop，出堆疊（彈出堆疊頂元素）

注意：這里說的"堆疊"與記憶體中的"堆疊空間"是兩個不同的概念

堆疊的結構

相比于陣列和鏈表而言，堆疊同樣是存盤相同型別資料的線性資料結構，只不過堆疊的受限性比較大，比如說：堆疊只有一端是開放的（堆疊頂），所有的資料操作都是在這一端進行的，基于這個特性，有了所謂的"后進先出(Last In First Out, LIFO)"的特點，其他 3 面是封閉的，所以堆疊除了堆疊頂元素，堆疊中的其他元素都是未知的，堆疊同時也做不到隨機訪問，

圖示堆疊結構：

在這里插入圖片描述

后進先出：

在這里插入圖片描述

堆疊的設計

看到前面的堆疊結構圖，是不是很熟悉，事實上，堆疊除了三面封閉的特性，其他的是和之前寫過的線性資料結構一致的，所以堆疊的內部實作可以直接利用以前學過的資料結構實作，動態陣列DynamicArray，鏈表LinkedList都是可以的，沒有讀過前面的撰寫動態陣列DynamicArray，鏈表LinkedList的文章的可以先去看看，動手撰寫—動態陣列（Java實作) 以及動手撰寫-鏈表（Java實作)

但是我們撰寫的Stack堆疊類，并不是直接去繼承這些類，因為這樣子會暴露動態陣列DynamicArray，鏈表LinkedList的一些原有方法，例如隨機訪問，隨機插入，洗掉等等，這樣都會使得堆疊失去特性，采用組合模式的方式能夠解決這一點，畫一下類圖關系：

在這里插入圖片描述

堆疊的介面設計

1、屬性：

private List<E> list; —— 利用基于List介面的線性表實作類設計堆疊

2、介面方法：

int size(); —— 查看當前堆疊元素的數量
boolean isEmpty(); —— 判斷堆疊是否為空
public void push(E element); —— 入堆疊，添加元素
public E pop(); —— 出堆疊，洗掉尾部元素
public E top(); —— 添獲取堆疊頂元素
void clear(); —— 清除堆疊元素

完成設計后，是具體的方法編碼實作，因為是利用動態陣列DynamicArray，鏈表LinkedList實作的堆疊，呼叫的都是封裝好的方法，這里就不細講了

編碼實作

public class Stack<E> extends DynamicArray<E>{

   //利用動態陣列實作堆疊
   private List<E> list = new DynamicArray<>();

   //利用鏈表實作堆疊
   //private List<E> list = new DynamicArray<>();

   /**
    * 查看堆疊元素數量
    * @return
    */
   public int size() {
      return list.size();
   }

   /**
    * 判斷堆疊是否為空
    * @return
    */
   public boolean isEmpty() {
      return list.isEmpty();
   }

   /**
    * 入堆疊，添加元素
    * @param element
    */
   public void push(E element){
      list.add(element);
   }

   /**
    * 出堆疊，洗掉尾部元素
    */
   public E pop(){
      return list.remove(list.size() - 1);
   }

   /**
    * 獲取堆疊頂元素
    * @return
    */
   public E top(){
      return list.get(list.size() - 1);
   }


   /**
    * 清空堆疊元素
    */
   public void clear() {
      list.clear();
   }
}

小結

堆疊的應用

1、雙堆疊實作瀏覽器的前進和后退

2、軟體的撤銷（Undo）、恢復（Redo）功能

佇列

概念

什么是佇列？

佇列：與前面堆疊不同的一點是，堆疊只能在堆疊頂一端操作元素，而佇列能在首尾兩端進行操作，佇列同樣是一種特殊的線性表

入隊：只能從隊尾（rear）添加元素，一般叫做enQueue

出隊：只能從隊頭（front）移除元素，一般叫做deQueue

佇列的結構

相比于陣列、鏈表及堆疊而言，佇列同樣是存盤相同型別資料的線性資料結構，只不過佇列的受限性比堆疊小一點，但比陣列、鏈表大，比如說：佇列只能在隊尾一端添加資料，隊頭移除元素，基于這個特性，有了所謂的"先進先出的原則，First In First Out，FIFO"的特點，其他 2 面在結構設計上是封閉的，所以佇列除了隊頭元素，佇列中的其他元素都是未知的，當然隊尾元素也是可見的，但是我們一般只在隊尾進行元素添加操作，所以也不會開放這個方法，佇列同時也做不到隨機訪問，

圖示佇列結構：

在這里插入圖片描述

佇列的設計

佇列和陣列、鏈表、以及堆疊都是線性表結構，所以我們沒有必要去做一些重復的操作，利用之前寫好的動態陣列DynamicArray，鏈表LinkedList都是可以實作的，同樣利用堆疊也是可以實作佇列的，但是這里我們是用雙向鏈表Both_LinkedList實作，

在前面動手撰寫-鏈表（Java實作)一文講到，雙向鏈表的頭結點與尾結點有first與last指標指向，這對于佇列在隊頭、隊尾操作元素是十分方便的，當然是用動態陣列或者單向鏈表也是可以的，只是陣列在隊頭洗掉元素會使得后面的元素結點往前移動，而單向鏈表在隊尾添加元素時，指標head需要遍歷到尾部結點，這兩者都會造成復雜度的增加，所以選擇雙向鏈表更好

同樣的，但是我們撰寫的Queue佇列并不直接接去繼承這些類，依舊采用組合的方式實作，畫一下類圖關系

在這里插入圖片描述

佇列的介面設計

1、屬性：

private List<E> list; —— 利用基于List介面的線性表實作類設計佇列

2、介面方法：

int size(); —— 查看當前佇列元素的數量
boolean isEmpty(); —— 判斷佇列是否為空
public void enQueue(E element); —— 入隊，添加元素
public E deQueue(); —— 出隊，洗掉頭部元素
public E front(); —— 添獲取隊頭元素
void clear(); —— 清除佇列元素

完成設計后，是具體的方法編碼實作，因為是利用雙向鏈表Both_LinkedList實作的佇列，呼叫的都是封裝好的方法，這里不細講

編碼實作

雙向鏈表實作佇列：

public class Queue<E> {

   //利用雙向鏈表封裝好的方法實作佇列
   private List<E> list = new Both_LinkedList<>();

   /**
    * 獲取佇列元素數量
    * @return
    */
   public int size() {
      return list.size();
   }

   /**
    * 判斷當前佇列是否為空
    * @return
    */
   public boolean isEmpty() {
      return list.isEmpty();
   }

   /**
    * 入隊，從隊尾添加元素
    * @param element
    */
   public void enQueue(E element) {
      list.add(element);
   }

   /**
    * 出隊，從隊頭移除元素
    * @return
    */
   public E deQueue() {
      return list.remove(0);
   }

   /**
    * 獲取隊頭元素
    * @return
    */
   public E front() {
      return list.get(0);
   }

   /**
    * 清空佇列元素
    */
   public void clear() {
      list.clear();
   }
}

雙堆疊實作佇列：

public class QueueByStack<E> {

    //定義兩個堆疊，inStack用于隊尾入隊，outStack用于隊頭出隊
    private Stack<E> inStack,outStack;

    //使用建構式初始化
    public QueueByStack() {
        this.inStack = new Stack<>();
        this.outStack = new Stack<>();
    }

    /**
     * 獲取佇列元素數量
     * @return
     */
    public int size() {
        return inStack.size() + outStack.size();
    }

    /**
     * 判斷當前佇列是否為空
     * @return
     */
    public boolean isEmpty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    /**
     * 入隊，從隊尾添加元素
     * @param element
     */
    public void enQueue(E element) {
        inStack.push(element);
    }

    /**
     * 出隊，從隊頭添加元素
     * @return
     */
    public E deQueue() {
        checkOutStack();
        return outStack.pop();
    }

    /**
     * 獲取隊頭元素
     * @return
     */
    public E front() {
        checkOutStack();
        return outStack.top();
    }

    /**
     * 清空堆疊元素
     */
    public void clear() {
        inStack.clear();
        outStack.clear();
    }

    /**
     * 檢查outStack是否為空，如果不為空，等著出隊
     * 如果為空，且inStack不為空，將inStack中的
     * 元素出堆疊，入堆疊到outStack，然后準備出隊
     */
    private void checkOutStack() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

雙端佇列

概念

雙端佇列：是能在頭尾兩端添加、洗掉的佇列

結構圖示：

在這里插入圖片描述

設計

雙端佇列Deque與佇列Queue在實作關系上沒有區別，同樣是基于雙向鏈表Both_LinkedList，使用組合模式實作的

雙向佇列的介面設計

1、屬性：

private List<E> list; —— 利用基于List介面的線性表實作類設計佇列

2、介面方法：

int size(); —— 查看當前佇列元素的數量
boolean isEmpty(); —— 判斷佇列是否為空
public void enQueueRear(E element); —— 入隊，從隊尾入隊
public E deQueueRear(); —— 出隊，從隊尾出隊
public void enQueueFront(E element); —— 入隊，從隊頭入隊
public E enQueueFront(); —— 出隊，從隊頭出隊
public E front(); —— 添獲取隊頭元素
public E rear(); —— 添獲取隊尾元素
void clear(); —— 清除佇列元素

編碼

public class Deque<E> {

    //利用雙向鏈表封裝好的方法實作佇列
    private List<E> list = new Both_LinkedList<>();

    /**
     * 獲取佇列元素數量
     * @return
     */
    public int size() {
        return list.size();
    }

    /**
     * 判斷當前佇列是否為空
     * @return
     */
    public boolean isEmpty() {
        return list.isEmpty();
    }

    /**
     * 入隊，從隊尾入隊
     * @param element
     */
    public void enQueueRear(E element) {
        list.add(element);
    }

    /**
     * 出隊，從隊尾出隊
     * @return
     */
    public E deQueueRear() {
        return list.remove(list.size() - 1);
    }

    /**
     * 入隊，從隊頭入隊
     * @param element
     */
    public void enQueueFront(E element) {
        list.add(0, element);
    }

    /**
     * 出隊，從對頭出隊
     * @return
     */
    public E deQueueFront() {
        return list.remove(0);
    }

    /**
     * 獲取隊頭元素
     * @return
     */
    public E front() {
        return list.get(0);
    }

    /**
     * 獲取隊尾元素
     * @return
     */
    public E rear() {
        return list.get(list.size() - 1);
    }

    /**
     * 清空佇列元素
     */
    public void clear() {
        list.clear();
    }
}

回圈佇列

概念：

回圈佇列：用陣列實作并且優化之后的佇列

圖示結構：

在這里插入圖片描述

設計：

回圈佇列又叫環形佇列，是基于Java陣列實作的，使用front指標指向的位置是隊頭，設計上，洗掉元素后不會像陣列一樣，挪動元素往前覆寫，而是將值置空，front往后移動，以這樣的機制洗掉元素，洗掉后的位置，當front指標后邊的位置滿了，新元素就可以填補剛剛洗掉的空位，起到環形的作用

回圈介面設計

1、屬性：

private int front; —— 回圈佇列隊頭指標
private int size; —— 佇列元素數量
private E[] elements; —— 使用順序結構陣列存盤
private static final int DEFAULT_CAPACITY = 10; —— 陣列的默認初始化值

2、介面方法：

int size(); —— 查看當前佇列元素的數量
boolean isEmpty(); —— 判斷佇列是否為空
public void enQueue(E element); —— 入隊，從隊尾入隊
public E deQueue(); —— 出隊，洗掉頭部元素
public E front(); —— 添獲取隊頭元素
void clear(); —— 清除佇列元素
private void ensureCapacity(int capacity) —— 保證要有capacity的容量,不足則擴容
private int index(int index); —— 索引映射函式，回傳真實陣列下標

1、出隊操作

在這里插入圖片描述

2、入隊操作

3、再入隊

在這里插入圖片描述

4、注意點：

(1) 入隊

在這里插入圖片描述

(2)入隊

在這里插入圖片描述

(3)出隊

在這里插入圖片描述

(4)擴容

在這里插入圖片描述

編碼：

public class CircleQueue<E> {

    //陣列的默認初始化值
    private static final int DEFAULT_CAPACITY = 10;

    //回圈佇列隊頭指標
    private int front;

    //佇列元素數量
    private int size;

    //使用順序結構陣列存盤
    private E[] elements;

    /**
     * 建構式初始化陣列
     */
    public CircleQueue() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    /**
     * 獲取佇列元素的數量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判斷佇列是否為空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 入隊，從隊尾添加元素
     * @param element
     */
    public void enQueue(E element) {
        ensureCapacity(size + 1);
        //elements[(front + size) % elements.length] = element;

        //呼叫封裝函式
        elements[index(size)] = element;
        size++;
    }

    /**
     * 出隊，從隊頭移除元素
     * @return
     */
    public E deQueue() {
        E element = elements[front];
        elements[front] = null;
        //front = (front + 1) % elements.length;
        //呼叫封裝函式
        front = index(1);
        size--;
        return element;
    }


    /**
     * 獲取隊頭元素
     * @return
     */
    public E front(){
        return elements[front];
    }

    /**
     * 清空佇列元素
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            //elements[(i + front) % elements.length] = null;

            //呼叫封裝函式
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    /**
     * 保證要有capacity的容量,不足則擴容
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;

        // 新容量為舊容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            //newElements[i] = elements[(i + front) % elements.length];

            //呼叫封裝函式
            newElements[i] = elements[index(i)];
        }
        elements = newElements;

        // 重置front
        front = 0;
    }

    /**
     * 索引映射函式，回傳真實陣列下標
     * @param index
     * @return
     */
    private int index(int index){
        return (front + index) % elements.length;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
                .append(" size=").append(size)
                .append(" front=").append(front)
                .append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }
}

回圈雙端佇列

概念：

回圈雙端佇列：可以進行兩端添加、洗掉操作的回圈隊

圖示結構：

在這里插入圖片描述

事實上，在結構上，與回圈佇列是一樣的，沒有必要設定一個last指標指向隊尾，因為我們采用的是陣列這種順序存盤結構，實際上，last = (font + size - 1) % array.length，只是我們在方法上對其功能進行了擴展而已

回圈介面設計

1、屬性：

private int front; —— 回圈佇列隊頭指標
private int size; —— 佇列元素數量
private E[] elements; —— 使用順序結構陣列存盤
private static final int DEFAULT_CAPACITY = 10; —— 陣列的默認初始化值

2、介面方法：

int size(); —— 查看當前佇列元素的數量
boolean isEmpty(); —— 判斷佇列是否為空
public void enQueueRear(E element); —— 入隊，從隊尾入隊
public E deQueueRear(); —— 出隊，從隊尾出隊
public void enQueueFront(E element); —— 入隊，從隊頭入隊
public E enQueueFront(); —— 出隊，從隊頭出隊
public E front(); —— 添獲取隊頭元素
public E rear(); —— 添獲取隊尾元素
void clear(); —— 清除佇列元素
private void ensureCapacity(int capacity) —— 保證要有capacity的容量,不足則擴容
private int index(int index); —— 索引映射函式，回傳真實陣列下標

編碼實作

上面也說到了，在結構上，與回圈佇列是一樣的，所以大多數的方法是一樣了，只是對其功能進行了增強，調整了部分方法邏輯

方法變動：

(1) 新增public void enQueueFront(E element); —— 入隊，從隊頭入隊

/**
 * 入隊，從隊頭入隊
 * @param element
 */
public void enQueueFront(E element) {

    //front指向當前節點前一位置
    front = index(-1);
    //假設虛擬索引，以front指向的位置為0，則向隊頭添加元素時往-1添加
    elements[front] = element;
    size++;
}

(2) 新增public E deQueueRear(); —— 出隊，從隊尾出隊

/**
 * 出隊，從隊尾出隊
 * @return
 */
public E deQueueRear() {
    //找到尾部元素的真實索引
    int last = index(size - 1);
    E element = elements[last];
    elements[last] = null;
    size--;
    return element;
}

(3) 新增public E rear(); —— 添獲取隊尾元素

/**
 * 獲取隊尾元素
 * @return
 */
public E rear() {
    return elements[index(size - 1)];
}

(4) 變動private int index(int index); —— 索引映射函式，回傳真實陣列下標

/**
 * 索引映射函式，回傳真實陣列下標
 * @param index
 * @return
 */
private int index(int index){
    index += front;

    //但真實index為0時，往隊頭添加元素，傳入 -1，小于0
    if (index < 0){
        index += elements.length;
    }
    return index % elements.length;
}

宣告

個人能力有限，有不正確的地方，還請指正

文章為原創，歡迎轉載，注明出處即可

本文的代碼已上傳github,歡迎star

GitHub地址

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/29145.html

標籤：其他

上一篇：洛谷P1712 [NOI2016]區間尺取法+線段樹+離散化

下一篇：目前unity2019不支持 3Dmax中的Skin Morph 蒙皮變形嗎？

（超詳細）動手撰寫 — 堆疊、佇列 ( Java實作 )

前言

堆疊

概念

堆疊的設計

編碼實作

小結

佇列

概念

佇列的設計

編碼實作

雙端佇列

概念

設計

編碼

回圈佇列

回圈佇列

回圈雙端佇列

宣告