博客 / 詳情

返回

線性數據結構

線性表示最常⽤⽽且最為簡單的⼀種數據結構，⼀個線性表示 n 個數據元素的有限序列，有以下特點：

  • 存在唯⼀的第⼀個的數據元素
  • 存在唯⼀被稱為最後⼀個的數據元素
  • 除了第⼀個以外，集合中每⼀個元素均有⼀個前驅
  • 除了最後⼀個元素之外，集合中的每⼀個數據元素都有⼀個後繼元素

線性表包括下⾯⼏種：

  • 數組：查詢 / 更新快，查找/刪除慢
  • 鏈表
  • 隊列
  • 棧

數組

數組簡介

數組（Array） 是一種很常見的數據結構。它由相同類型的元素（element）組成，並且是使用一塊連續的內存來存儲。

在Java 中表示為：

int[] nums = new int[100];
int[] nums = {1,2,3,4,5};
Object[] Objects = new Object[100];

數組是⼀種線性的結構，⼀般在底層是連續的空間，存儲相同類型的數據，由於連續緊湊結構以及天然索引⽀持，查詢數據效率⾼。

假設我們知道數組a 的第 1 個值是 地址是 296，⾥⾯的數據類型佔 2 個 單位，那麼我們如果期望得到第 5 個： 296+（5-1）*2 = 304 , O(1) 的時間複雜度就可以獲取到。更新的本質也是查找，先查找到該元素，就可以動⼿更新了：

但是如果期望插⼊數據的話，需要移動後⾯的數據，⽐如下⾯的數組，插⼊元素6 ，最差的是移動所有的元素，時間複雜度為O(n)

⽽刪除元素則需要把後⾯的數據移動到前⾯，最差的時間複雜度同樣為O(n)

總結：數組的特點是：提供隨機訪問 並且容量有限。

時間複雜度

假如數組的長度為 n。

  • 訪問：O（1）//訪問特定位置的元素
  • 插入：O（n ）//最壞的情況發生在插入發生在數組的首部並需要移動所有元素時
  • 刪除：O（n）//最壞的情況發生在刪除數組的開頭髮生並需要移動第一元素後面所有的元素時

數組的增刪改查實現

import java.util.Arrays;
public class MyArray {
    private int[] data;
    private int elementCount;
    private int length;
    
    public MyArray(int max) {
        length = max;
        data = new int[max];
        elementCount = 0;
    }
    
    public void add(int value) {
        if (elementCount == length) {
            length = 2 * length;
            data = Arrays.copyOf(data, length);
        }
        data[elementCount] = value;
        elementCount++;
    }
    
    public int find(int searchKey) {
        int i;
        for (i = 0; i < elementCount; i++) {
            if (data[i] == searchKey)
            break;
        }
        if (i == elementCount) {
            return -1;
        }
        return i;
    }
    
    public boolean delete(int value) {
        int i = find(value);
        if (i == -1) {
        	return false;
        }
        for (int j = i; j < elementCount - 1; j++) {
        	data[j] = data[j + 1];
        }
        elementCount--;
        return true;
    }
    
    public boolean update(int oldValue, int newValue) {
        int i = find(oldValue);
        if (i == -1) {
        	return false;
        }
        data[i] = newValue;
        return true;
    }
}

// 測試類
public class Test {
    public static void main(String[] args) {
        MyArray myArray = new MyArray(2);
        myArray.add(1);
        myArray.add(2);
        myArray.add(3);
        myArray.delete(2);
        System.out.println(myArray);
    }
}

鏈表

鏈表簡介

鏈表（LinkedList） 雖然是一種線性表，但是並不會按線性的順序存儲數據，使用的不是連續的內存空間來存儲數據。

我們可以看到數組是需要連續的空間，這⾥⾯如果空間⼤⼩只有 2 ，放到第 3 個元素的時候，就不得不擴容，不僅如此，還得拷⻉元素。⼀些刪除，插⼊操作會引起較多的數據移動的操作。

鏈表，也就是鏈式數據結構，由於它不要求邏輯上相鄰的數據元素在物理位置上也相鄰，所以它沒有順序存儲結構所具有的缺點，但是同時也失去了通過索引下標直接查找元素的優點。

鏈表的插入和刪除操作的複雜度為 O(1) ，只需要知道目標位置元素的上一個元素即可。但是，在查找一個節點或者訪問特定位置的節點的時候複雜度為 O(n) 。

使用鏈表結構可以克服數組需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間,實現靈活的內存動態管理。但鏈表不會節省空間，相比於數組會佔用更多的空間，因為鏈表中每個節點存放的還有指向其他節點的指針。除此之外，鏈表不具有數組隨機讀取的優點。

時間複雜度

  • 查詢： O(n)，需要遍歷鏈表
  • 插⼊： O(1) ，修改前後指針即可
  • 刪除： O(1) ，同樣是修改前後指針即可
  • 修改：不需要查詢則為O(1) ，需要查詢則為O(n)

鏈表分類

常見鏈表分類：

  1. 單鏈表：鏈表中的每⼀個結點，都有且只有⼀個指針指向下⼀個結點，並且最後⼀個節點指向空。
  2. 雙向鏈表：每個節點都有兩個指針（為⽅便，我們稱之為前指針，後指針），分別指向上⼀個節點和下⼀個節點，第⼀個節點的前指針指向NULL ，最後⼀個節點的後指針指向NULL
  3. 循環鏈表：每⼀個節點的指針指向下⼀個節點，並且最後⼀個節點的指針指向第⼀個節點（雖然是循環鏈表，但是必要的時候還需要標識頭結點或者尾節點，避免死循環）
  4. 雙向循環鏈表：同時滿足雙向鏈表和循環鏈表的能力

單鏈表

單鏈表 單向鏈表只有一個方向，結點只有一個後繼指針 next 指向後面的節點。因此，鏈表這種數據結構通常在物理內存上是不連續的。我們習慣性地把第一個結點叫作頭結點，鏈表通常有一個不保存任何值的 head 節點(頭結點)，通過頭結點我們可以遍歷整個鏈表。尾結點通常指向 null。

單向鏈表的查找更新⽐較簡單，我們看看插⼊新節點的具體過程（這⾥只展示中間位置的插⼊，頭尾插⼊⽐較簡單）：

那如何刪除⼀箇中間的節點呢？下⾯是具體的過程：

或許你會好奇， a5 節點只是指針沒有了，那它去哪⾥了？

如果是Java 程序，垃圾回收器會收集這種沒有被引⽤的節點，幫我們回收掉了這部分內存，但是為了加快垃圾回收的速度，⼀般不需要的節點我們會置空，⽐如 node = null , 如果在C++ 程序中，那麼就需要⼿動回收了，否則容易造成內存泄漏等問題。

循環鏈表

循環鏈表 其實是一種特殊的單鏈表，和單鏈表不同的是循環鏈表的尾結點不是指向 null，而是指向鏈表的頭結點。

雙向鏈表

雙向鏈表 包含兩個指針，一個 prev 指向前一個節點，一個 next 指向後一個節點。

雙向循環鏈表

雙向循環鏈表 最後一個節點的 next 指向 head，而 head 的 prev 指向最後一個節點，構成一個環。

應用場景

  • 如果需要支持隨機訪問的話，鏈表沒辦法做到。
  • 如果需要存儲的數據元素的個數不確定，並且需要經常添加和刪除數據的話，使用鏈表比較合適。
  • 如果需要存儲的數據元素的個數確定，並且不需要經常添加和刪除數據的話，使用數組比較合適。

數組 vs 鏈表

  • 數組支持隨機訪問，而鏈表不支持。
  • 數組使用的是連續內存空間對 CPU 的緩存機制友好，鏈表則相反。
  • 數組的大小固定，而鏈表則天然支持動態擴容。如果聲明的數組過小，需要另外申請一個更大的內存空間存放數組元素，然後將原數組拷貝進去，這個操作是比較耗時的！

單向鏈表的增刪改查實現

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
    	this.val = val;
    }
}

public class MyList<T> {
    private ListNode<T> head;
    private ListNode<T> tail;
    private int size;
    
    public MyList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    public void add(T element) {
    	add(size, element);
    }
    
    public void add(int index, T element) {
        if (index < 0 || index > size) {
        	throw new IndexOutOfBoundsException("超出鏈表⻓度範圍");
        }
        ListNode current = new ListNode(element);
        if (index == 0) {
        	if (head == null) {
            	head = current;
        		tail = current;
        	} else {
                current.next = head;
                head = current;
            }
        } else if (index == size) {
            tail.next = current;
            tail = current;
        } else {
            ListNode preNode = get(index - 1);
            current.next = preNode.next;
            preNode.next = current;
        }
        size++;
    }
    
    public ListNode get(int index) {
        if (index < 0 || index >= size) {
        	throw new IndexOutOfBoundsException("超出鏈表⻓度");
        }
        ListNode temp = head;
        for (int i = 0; i < index; i++) {
        	temp = temp.next;
        }
        return temp;
    }
    
    public ListNode delete(int index) {
        if (index < 0 || index >= size) {
        	throw new IndexOutOfBoundsException("超出鏈表節點範圍");
        }
        ListNode node = null;
        if (index == 0) {
            node = head;
            head = head.next;
        } else if (index == size - 1) {
            ListNode preNode = get(index - 1);
            node = tail;
            preNode.next = null;
            tail = preNode;
        } else {
            ListNode pre = get(index - 1);
            pre.next = pre.next.next;
            node = pre.next;
        }
        size--;
        return node;
    }
    
    public void update(int index, T element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出鏈表節點範圍");
        }
        ListNode node = get(index);
        node.val = element;
    }
    
    public void display() {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " -> ");
            temp = temp.next;
        }
        System.out.println("");
    }
}

擴展：跳錶

鏈表如果搜索，是很麻煩的，如果這個節點在最後，需要遍歷所有的節點，才能找到，查找效率實在太低，有沒有什麼好的辦法呢？

辦法總⽐問題多，但是想要絕對的” 多快好省“是不存在的，有舍有得，計算機的世界⾥，充滿哲學的味道。既然搜索效率有問題，那麼我們不如給鏈表排個序。排序後的鏈表，還是隻能知道頭尾節點，知道中間的範圍，但是要找到中間的節點，還是得⾛遍歷的⽼路。如果我們把中間節點存儲起來呢？存起來，確實我們就知道數據在前⼀半，還是在後⼀半。⽐如找7 ，肯定就從中間節點開始找。如果查找4 ,就得從頭開始找，最差到中間節點，就停⽌查找。

但是如此，還是沒有徹底解決問題，因為鏈表很⻓的情況，只能通過前後兩部分查找。不如回到原則：空間和時間，我們選擇時間，那就要捨棄⼀部分空間,我們每個節點再加⼀個指針，現在有 2 層指針（注意：節點只有⼀份，都是同⼀個節點，只是為了好看，弄了兩份，實際上是同⼀個節點，有兩個指針，⽐如 1 ，既指向2，也指向5）：

兩層指針，問題依然存在，那就不斷加層，⽐如每兩個節點，就加⼀層：

這就是跳錶了，跳錶的定義如下：

跳錶(SkipList，全稱跳躍表)是⽤於有序元素序列快速搜索查找的⼀個數據結構，跳錶是⼀個隨機化的數據結構，實質就是⼀種可以進⾏⼆分查找的有序鏈表。跳錶在原有的有序鏈表上⾯增加了多級索引，通過索引來實現快速查找。跳錶不僅能提⾼搜索性能，同時也可以提⾼插⼊和刪除操作的性能。它在性能上和紅⿊樹，AVL樹不相上下，但是跳錶的原理⾮常簡單，實現也⽐紅⿊樹簡單很多。

主要的原理是⽤空間換時間，可以實現近乎⼆分查找的效率，實際上消耗的空間，假設每兩個加⼀層，1 + 2 + 4 + ... + n = 2n-1 ,多出了差不多⼀倍的空間。你看它像不像書的⽬錄，⼀級⽬錄，⼆級，三級 ...

如果我們不斷往跳錶中插⼊數據，可能出現某⼀段節點會特別多的情況，這個時候就需要動態更新索引，除了插⼊數據，還要插⼊到上⼀層的鏈表中，保證查詢效率。redis 中使⽤了跳錶來實現zset , redis 中使⽤⼀個隨機算法來計算層級，計算出每個節點到底多少層索引，雖然不能絕對保證⽐較平衡，但是基本保證了效率，實現起來⽐那些平衡樹，紅⿊樹的算法簡單⼀點。

在跳錶中，每個節點包含以下幾個組成部分：

  • 值（value）：節點存儲的數據
  • 前進指針數組（forward array）：指向不同層級的後繼節點
  • 層高（level）：該節點的最大層級

跳錶核心特性：

  1. 多層結構：由最底層的原始有序鏈表，以及若干層索引組成
  2. 概率平衡：通過隨機函數決定節點的層數，無需複雜的平衡操作
  3. 快速查找：能夠跳過大量節點，實現對數級別的查找效率
  4. 有序性：所有節點按關鍵字排序
  5. 空間換時間：使用額外的索引指針提高查詢速度

基本操作

  • 查找（Search）：查找過程從最高層開始，沿着當前層前進，直到遇到大於或等於目標值的節點：

    1. 如果找到目標值，返回該節點
    2. 如果當前節點的下一個值大於目標值，則降至下一層繼續查找
    3. 如果到達最底層仍未找到，則目標值不存在

  • 插入（Insert）

    1. 查找新值的插入位置，同時記錄每一層的"插入點"
    2. 隨機生成新節點的層高
    3. 從底層到該節點的最高層，逐層調整指針，將新節點插入到每層鏈表中

  • 刪除（Delete）

    1. 查找待刪除節點的位置，同時記錄每一層的前驅節點
    2. 如果找到該節點，從該節點的最高層到底層，逐層調整前驅節點的指針，繞過待刪除節點

基礎實現

import java.util.Random;

public class SkipList<T extends Comparable<T>> {
    private static final int MAX_LEVEL = 16; // 最大層數
    private static final double P = 0.5;     // 提升層級的概率
    private int level;                       // 當前跳錶的最大層數
    private final Node<T> header;            // 頭節點
    private final Random random;             // 用於隨機層數的生成

    // 節點定義
    private static class Node<T extends Comparable<T>> {
        T value;                  // 節點值
        Node<T>[] forward;        // 前進指針數組

        @SuppressWarnings("unchecked")
        Node(T value, int level) {
            this.value = value;
            this.forward = new Node[level + 1];
        }
    }

    // 構造函數
    public SkipList() {
        this.level = 0;
        this.header = new Node<>(null, MAX_LEVEL);
        this.random = new Random();
    }

    // 隨機生成層數
    private int randomLevel() {
        int lvl = 0;
        while (lvl < MAX_LEVEL && random.nextDouble() < P) {
            lvl++;
        }
        return lvl;
    }

    // 查找操作
    public Node<T> search(T value) {
        Node<T> current = header;
        
        // 從最高層開始查找
        for (int i = level; i >= 0; i--) {
            // 在當前層向前移動，直到找到大於等於目標值的節點
            while (current.forward[i] != null && 
                   current.forward[i].value.compareTo(value) < 0) {
                current = current.forward[i];
            }
        }
        
        // 現在我們在第0層，並且current是目標值的前一個節點
        current = current.forward[0];
        
        // 檢查是否找到目標值
        if (current != null && current.value.compareTo(value) == 0) {
            return current;
        } else {
            return null;
        }
    }

    // 插入操作
    public void insert(T value) {
        @SuppressWarnings("unchecked")
        Node<T>[] update = new Node[MAX_LEVEL + 1];
        Node<T> current = header;

        // 查找插入位置並記錄每層的前驅節點
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].value.compareTo(value) < 0) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        
        // 獲取新節點的隨機層數
        int newLevel = randomLevel();
        
        // 如果新層數比當前跳錶的最大層數大，更新跳錶層數
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = header;
            }
            level = newLevel;
        }
        
        // 創建新節點
        Node<T> newNode = new Node<>(value, newLevel);
        
        // 插入節點到各層鏈表中
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    // 刪除操作
    public void delete(T value) {
        @SuppressWarnings("unchecked")
        Node<T>[] update = new Node[MAX_LEVEL + 1];
        Node<T> current = header;

        // 查找刪除位置並記錄每層的前驅節點
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].value.compareTo(value) < 0) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        
        current = current.forward[0];
        
        // 如果找到節點，進行刪除
        if (current != null && current.value.compareTo(value) == 0) {
            for (int i = 0; i <= level; i++) {
                // 如果當前層的前驅節點指向要刪除的節點，則修改指針
                if (update[i].forward[i] == current) {
                    update[i].forward[i] = current.forward[i];
                }
            }
            
            // 更新跳錶的最大層數
            while (level > 0 && header.forward[level] == null) {
                level--;
            }
        }
    }

    // 打印跳錶內容（用於調試）
    public void printSkipList() {
        System.out.println("Skip List Structure:");
        for (int i = level; i >= 0; i--) {
            System.out.print("Level " + i + ": ");
            Node<T> node = header.forward[i];
            while (node != null) {
                System.out.print(node.value + " ");
                node = node.forward[i];
            }
            System.out.println();
        }
    }
}

// 跳錶節點
class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.forward = new Array(level + 1).fill(null);
  }
}

// 使用示例
SkipList skipList = new SkipList();
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
console.log(skipList.search(6)); // true
skipList.insert(9);
skipList.delete(6);
console.log(skipList.search(6)); // false

棧

棧簡介

棧 (Stack) 只允許在有序的線性數據集合的一端（稱為棧頂 top）進行加入數據（push）和移除數據（pop）。因而按照 後進先出（LIFO, Last In First Out） 的原理運作。在棧中，push 和 pop 的操作都發生在棧頂。就像是⼀個桶，只能不斷的放在上⾯，取出來的時候，也只能不斷的取出最上⾯的數據。要想取出底層的數據，只有等到上⾯的數據都取出來，才能做到。當然，如果有這種需求，我們⼀般會使⽤雙向隊列。

棧常用一維數組或鏈表來實現，用數組實現的棧叫作 順序棧 ，用鏈表實現的棧叫作 鏈式棧 。JDK 底層的棧，是⽤數組實現的，封裝之後，通過API 操作的永遠都只能是最後⼀個元素，棧經常⽤來實現遞歸的功能。

元素加⼊稱之為⼊棧（壓棧），取出元素，稱之為出棧，棧頂元素則是最後⼀次放進去的元素。使⽤數組實現簡單的棧(注意僅供參考測試，實際會有線程安全等問題)

時間複雜度

假設堆棧中有n個元素。

  • 訪問：O（n）//最壞情況
  • 插入刪除：O（1）//頂端插入和刪除元素

棧的常見應用場景

當我們我們要處理的數據只涉及在一端插入和刪除數據，並且滿足 後進先出（LIFO, Last In First Out） 的特性時，我們就可以使用棧這個數據結構。

實現瀏覽器的回退和前進功能

我們只需要使用兩個棧(Stack1 和 Stack2)和就能實現這個功能。比如你按順序查看了 1,2,3,4 這四個頁面，我們依次把 1,2,3,4 這四個頁面壓入 Stack1 中。當你想回頭看 2 這個頁面的時候，你點擊回退按鈕，我們依次把 4,3 這兩個頁面從 Stack1 彈出，然後壓入 Stack2 中。假如你又想回到頁面 3，你點擊前進按鈕，我們將 3 頁面從 Stack2 彈出，然後壓入到 Stack1 中。

檢查符號是否成對出現

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷該字符串是否有效。

有效字符串需滿足：

  1. 左括號必須用相同類型的右括號閉合。
  2. 左括號必須以正確的順序閉合。

比如 "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]"、"([)]" 則不是。

這個問題實際是 Leetcode 的一道題目，我們可以利用棧 Stack 來解決這個問題。

  1. 首先我們將括號間的對應規則存放在 Map 中，這一點應該毋容置疑；
  2. 創建一個棧。遍歷字符串，如果字符是左括號就直接加入stack中，否則將stack 的棧頂元素與這個括號做比較，如果不相等就直接返回 false。遍歷結束，如果stack為空，返回 true。
public boolean isValid(String s){
    // 括號之間的對應規則
    HashMap<Character, Character> mappings = new HashMap<Character, Character>();
    mappings.put(')', '(');
    mappings.put('}', '{');
    mappings.put(']', '[');
    Stack<Character> stack = new Stack<Character>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if (mappings.containsKey(chars[i])) {
            char topElement = stack.empty() ? '#' : stack.pop();
            if (topElement != mappings.get(chars[i])) {
                return false;
            }
        } else {
            stack.push(chars[i]);
        }
    }
    return stack.isEmpty();
}

反轉字符串

將字符串中的每個字符先入棧再出棧就可以了。

維護函數調用

最後一個被調用的函數必須先完成執行，符合棧的 後進先出（LIFO, Last In First Out） 特性。
例如遞歸函數調用可以通過棧來實現，每次遞歸調用都會將參數和返回地址壓棧。

深度優先遍歷（DFS）

在深度優先搜索過程中，棧被用來保存搜索路徑，以便回溯到上一層。

棧的實現

棧既可以通過數組實現，也可以通過鏈表來實現。不管基於數組還是鏈表，入棧、出棧的時間複雜度都為 O(1)。

下面我們使用數組來實現一個棧，並且這個棧具有push()、pop()（返回棧頂元素並出棧）、peek() （返回棧頂元素不出棧）、isEmpty()、size()這些基本的方法。

提示：每次入棧之前先判斷棧的容量是否夠用，如果不夠用就用Arrays.copyOf()進行擴容；

public class MyStack {
    private int[] storage;//存放棧中元素的數組
    private int capacity;//棧的容量
    private int count;//棧中元素數量
    private static final int GROW_FACTOR = 2;

    //不帶初始容量的構造方法。默認容量為8
    public MyStack() {
        this.capacity = 8;
        this.storage=new int[8];
        this.count = 0;
    }

    //帶初始容量的構造方法
    public MyStack(int initialCapacity) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException("Capacity too small.");

        this.capacity = initialCapacity;
        this.storage = new int[initialCapacity];
        this.count = 0;
    }

    //入棧
    public void push(int value) {
        if (count == capacity) {
            ensureCapacity();
        }
        storage[count++] = value;
    }

    //確保容量大小
    private void ensureCapacity() {
        int newCapacity = capacity * GROW_FACTOR;
        storage = Arrays.copyOf(storage, newCapacity);
        capacity = newCapacity;
    }

    //返回棧頂元素並出棧
    private int pop() {
        if (count == 0)
            throw new IllegalArgumentException("Stack is empty.");
        count--;
        return storage[count];
    }

    //返回棧頂元素不出棧
    private int peek() {
        if (count == 0){
            throw new IllegalArgumentException("Stack is empty.");
        }else {
            return storage[count-1];
        }
    }

    //判斷棧是否為空
    private boolean isEmpty() {
        return count == 0;
    }

    //返回棧中元素的個數
    private int size() {
        return count;
    }

}

驗證

MyStack myStack = new MyStack(3);
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
myStack.push(7);
myStack.push(8);
System.out.println(myStack.peek());//8
System.out.println(myStack.size());//8
for (int i = 0; i < 8; i++) {
    System.out.println(myStack.pop());
}
System.out.println(myStack.isEmpty());//true
myStack.pop();//報錯：java.lang.IllegalArgumentException: Stack is empty.

隊列

隊列簡介

隊列（Queue） 是 先進先出 (FIFO，First In, First Out) 的線性表。在具體應用中通常用鏈表或者數組來實現，用數組實現的隊列叫作 順序隊列 ，用鏈表實現的隊列叫作 鏈式隊列 。隊列只允許在後端（rear）進行插入操作也就是入隊 enqueue，在前端（front）進行刪除操作也就是出隊 dequeue

隊列的操作方式和堆棧類似，唯一的區別在於隊列只允許新數據在後端進行添加。

⼀般只要説到先進先出（ FIFO ）,全稱First In First Out ,就會想到隊列，但是如果你想擁有隊列即可以從隊頭取出元素，⼜可以從隊尾取出元素，那就需要⽤到特殊的隊列（雙向隊列），雙向隊列⼀般使⽤雙向鏈表實現會簡單⼀點。

時間複雜度

假設隊列中有n個元素。

  • 訪問：O（n）//最壞情況
  • 插入刪除：O（1）//後端插入前端刪除元素

隊列分類

單隊列

單隊列就是常見的隊列, 每次添加元素時，都是添加到隊尾。單隊列又分為 順序隊列（數組實現） 和 鏈式隊列（鏈表實現）。

順序隊列存在“假溢出”的問題也就是明明有位置卻不能添加的情況。

假設下圖是一個順序隊列，我們將前兩個元素 1,2 出隊，併入隊兩個元素 7,8。當進行入隊、出隊操作的時候，front 和 rear 都會持續往後移動，當 rear 移動到最後的時候,我們無法再往隊列中添加數據，即使數組中還有空餘空間，這種現象就是 ”假溢出“ 。除了假溢出問題之外，如下圖所示，當添加元素 8 的時候，rear 指針移動到數組之外（越界）。

為了避免當只有一個元素的時候，隊頭和隊尾重合使處理變得麻煩，所以引入兩個指針，front 指針指向對頭元素，rear 指針指向隊列最後一個元素的下一個位置，這樣當 front 等於 rear 時，此隊列不是還剩一個元素，而是空隊列。——From 《大話數據結構》

循環隊列

循環隊列可以解決順序隊列的假溢出和越界問題。解決辦法就是：從頭開始，這樣也就會形成頭尾相接的循環，這也就是循環隊列名字的由來。

順序隊列中，我們説 front==rear 的時候隊列為空，循環隊列中則不一樣，也可能為滿，如上圖所示。解決辦法有兩種：

  1. 可以設置一個標誌變量 flag,當 front==rear 並且 flag=0 的時候隊列為空，當front==rear 並且 flag=1 的時候隊列為滿。
  2. 隊列為空的時候就是 front==rear ，隊列滿的時候，我們保證數組還有一個空閒的位置，rear 就指向這個空閒位置，如下圖所示，那麼現在判斷隊列是否為滿的條件就是：(rear+1) % QueueSize==front 。

雙端隊列

雙端隊列 (Deque) 是一種在隊列的兩端都可以進行插入和刪除操作的隊列，相比單隊列來説更加靈活。

一般來説，我們可以對雙端隊列進行 addFirst、addLast、removeFirst 和 removeLast 操作。

優先隊列

優先隊列 (Priority Queue) 從底層結構上來講並非線性的數據結構，它一般是由堆來實現的。

  1. 在每個元素入隊時，優先隊列會將新元素其插入堆中並調整堆。
  2. 在隊頭出隊時，優先隊列會返回堆頂元素並調整堆。

關於堆的具體實現可以看堆這一節。

總而言之，不論我們進行什麼操作，優先隊列都能按照某種排序方式進行一系列堆的相關操作，從而保證整個集合的有序性。

雖然優先隊列的底層並非嚴格的線性結構，但是在我們使用的過程中，我們是感知不到堆的，從使用者的眼中優先隊列可以被認為是一種線性的數據結構：一種會自動排序的線性隊列。

隊列的常見應用場景

當我們需要按照一定順序來處理數據的時候可以考慮使用隊列這個數據結構。

  • 阻塞隊列： 阻塞隊列可以看成在隊列基礎上加了阻塞操作的隊列。當隊列為空的時候，出隊操作阻塞，當隊列滿的時候，入隊操作阻塞。使用阻塞隊列我們可以很容易實現“生產者 - 消費者“模型。
  • 線程池中的請求/任務隊列： 線程池中沒有空閒線程時，新的任務請求線程資源時，線程池該如何處理呢？答案是將這些請求放在隊列中，當有空閒線程的時候，會循環中反覆從隊列中獲取任務來執行。隊列分為無界隊列(基於鏈表)和有界隊列(基於數組)。無界隊列的特點就是可以一直入列，除非系統資源耗盡，比如：FixedThreadPool 使用無界隊列 LinkedBlockingQueue。但是有界隊列就不一樣了，當隊列滿的話後面再有任務/請求就會拒絕，在 Java 中的體現就是會拋出java.util.concurrent.RejectedExecutionException 異常。
  • 棧：雙端隊列天生便可以實現棧的全部功能（push、pop 和 peek），並且在 Deque 接口中已經實現了相關方法。Stack 類已經和 Vector 一樣被遺棄，現在在 Java 中普遍使用雙端隊列（Deque）來實現棧。
  • 廣度優先搜索（BFS），在圖的廣度優先搜索過程中，隊列被用於存儲待訪問的節點，保證按照層次順序遍歷圖的節點。
  • Linux 內核進程隊列（按優先級排隊）
  • 現實生活中的派對，播放器上的播放列表;
  • 消息隊列
  • 等等……

單向隊列的實現

class Node<T> {
    public T data;
    public Node next;
    
    public Node(T data) {
    	this.data = data;
    }
}

public class MyQueue<T> {
    private Node<T> head;
    private Node<T> rear;
    private int size;
    
    public MyQueue() {
    	size = 0;
    }
    
    public void pushBack(T element) {
        Node newNode = new Node(element);
        if (isEmpty()) {
        	head = newNode;
        } else {
        	rear.next = newNode;
        }
        rear = newNode;
        size++;
    }
    
    public boolean isEmpty() {
    	return head == null;
    }
    
    public T popFront() {
        if (isEmpty()) {
        	throw new NullPointerException("隊列沒有數據");
        } else {
            Node<T> node = head;
            head = head.next;
            size--;
            return node.data;
    	}
	}
    
    public void dispaly() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data +" -> ");
            temp = temp.next;
        }
        System.out.println("");
    }
}

用棧實現隊列以及隊列實現棧

棧實現隊列

  • 棧的特性是先進後出
  • 隊列的特性是先進先出

有兩個棧 stack1 , stack2 ；

  • 如果有新的數據進⼊，那麼我們可以直接 push 到 stack1 ；
  • 如果需要取出數據，那麼我們優先取出 stack2 的數據，如果 stack2 ⾥⾯數據是空的，那麼我們需要把所有的 stack1 的數據倒⼊ stack2 。再從 stack2 取數據。

例如：

  1. push 1 --> push 2

  1. pop 1

image-20250316170844217

  1. push 3 --> push 4

  1. pop 2

算法實現如下：

class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    /** Initialize your data structure here. */
    public MyQueue() {
        stackIn = new Stack<>(); // 負責進棧
        stackOut = new Stack<>(); // 負責出棧
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stackIn.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {    
        dumpstackIn();
        return stackOut.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    // 如果stackOut為空，那麼將stackIn中的元素全部放到stackOut中
    private void dumpstackIn(){
        if (!stackOut.isEmpty()) return; 
        while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
        }
    }
}
  • 時間複雜度: push和empty為O(1), pop和peek為O(n)
  • 空間複雜度: O(n)

隊列實現棧

隊列是先進先出的規則，把一個隊列中的數據導入另一個隊列中，數據的順序並沒有變，並沒有變成先進後出的順序。

所以用棧實現隊列， 和用隊列實現棧的思路還是不一樣的，這取決於這兩個數據結構的性質。

但是依然還是要用兩個隊列來模擬棧，只不過沒有輸入和輸出的關係，而是另一個隊列完全用來備份的！

class MyStack {

    Queue<Integer> queue1; // 和棧中保持一樣元素的隊列
    Queue<Integer> queue2; // 輔助隊列

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x); // 先放在輔助隊列中
        while (!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> queueTemp;
        queueTemp = queue1;
        queue1 = queue2;
        queue2 = queueTemp; // 最後交換queue1和queue2，將元素都放到queue1中
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll(); // 因為queue1中的元素和棧中的保持一致，所以這個和下面兩個的操作只看queue1即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}
  • 時間複雜度: pop為O(n)，其他為O(1)
  • 空間複雜度: O(n)

優化：

其實這道題目就是用一個隊列就夠了。

一個隊列在模擬棧彈出元素的時候只要將隊列頭部的元素（除了最後一個元素外） 重新添加到隊列尾部，此時再去彈出元素就是棧的順序了。

class MyStack {
    Queue<Integer> queue;
    
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        queue.add(x);
    }
    
    public int pop() {
        rePosition();
        return queue.poll();
    }
    
    public int top() {
        rePosition();
        int result = queue.poll();
        queue.add(result);
        return result;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }

    public void rePosition(){
        int size = queue.size();
        size--;
        while(size-->0)
            queue.add(queue.poll());
    }
}
  • 時間複雜度: pop為O(n)，其他為O(1)
  • 空間複雜度: O(n)
後端
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.