­

（超詳細）動手編寫 — 棧、隊列 ( Java實現 )

目錄

前言

棧

概念

什麼是棧？

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

入棧：往棧中添加元素的操作，一般叫做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地址

Tags:

VirMach 便宜 VPS

QNews

QNews