JavaScript鏈表如何實現棧和隊列

JavaScript鏈表如何實現棧和隊列

在JavaScript中，鏈表是一種常見的數據結構，它由一系列節點組成，每個節點包含數據和指向下一個節點的指針。鏈表可以用來實現棧和隊列這兩種常見的數據結構。本文將介紹如何使用JavaScript中的鏈表來實現棧和隊列。

1. 鏈表的基本結構

首先，我們需要定義一個鏈表節點的類。每個節點包含兩個屬性：data 用于存儲數據，next 用于指向下一個節點。

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

接下來，我們可以定義一個鏈表類，它包含一個指向鏈表頭部的指針 head。

class LinkedList {
    constructor() {
        this.head = null;
    }
}

2. 使用鏈表實現棧

棧是一種后進先出（LIFO）的數據結構。我們可以使用鏈表的頭部來表示棧的頂部。棧的基本操作包括 push（入棧）、pop（出棧）和 peek（查看棧頂元素）。

2.1 入棧操作

在鏈表中，入棧操作相當于在鏈表的頭部插入一個新節點。

class Stack {
    constructor() {
        this.list = new LinkedList();
    }

    push(data) {
        const newNode = new Node(data);
        newNode.next = this.list.head;
        this.list.head = newNode;
    }
}

2.2 出棧操作

出棧操作相當于刪除鏈表的頭部節點，并返回該節點的數據。

class Stack {
    // ... 其他代碼

    pop() {
        if (this.list.head === null) {
            throw new Error("Stack is empty");
        }
        const data = this.list.head.data;
        this.list.head = this.list.head.next;
        return data;
    }
}

2.3 查看棧頂元素

查看棧頂元素相當于返回鏈表頭部節點的數據。

class Stack {
    // ... 其他代碼

    peek() {
        if (this.list.head === null) {
            throw new Error("Stack is empty");
        }
        return this.list.head.data;
    }
}

3. 使用鏈表實現隊列

隊列是一種先進先出（FIFO）的數據結構。我們可以使用鏈表的頭部來表示隊列的頭部，鏈表的尾部來表示隊列的尾部。隊列的基本操作包括 enqueue（入隊）、dequeue（出隊）和 peek（查看隊頭元素）。

3.1 入隊操作

在鏈表中，入隊操作相當于在鏈表的尾部插入一個新節點。

class Queue {
    constructor() {
        this.list = new LinkedList();
        this.tail = null;
    }

    enqueue(data) {
        const newNode = new Node(data);
        if (this.tail === null) {
            this.list.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
    }
}

3.2 出隊操作

出隊操作相當于刪除鏈表的頭部節點，并返回該節點的數據。

class Queue {
    // ... 其他代碼

    dequeue() {
        if (this.list.head === null) {
            throw new Error("Queue is empty");
        }
        const data = this.list.head.data;
        this.list.head = this.list.head.next;
        if (this.list.head === null) {
            this.tail = null;
        }
        return data;
    }
}

3.3 查看隊頭元素

查看隊頭元素相當于返回鏈表頭部節點的數據。

class Queue {
    // ... 其他代碼

    peek() {
        if (this.list.head === null) {
            throw new Error("Queue is empty");
        }
        return this.list.head.data;
    }
}

4. 總結

通過使用鏈表，我們可以輕松地實現棧和隊列這兩種常見的數據結構。棧和隊列的操作在鏈表中都可以通過簡單的指針操作來完成，這使得鏈表的實現非常高效。在實際開發中，鏈表、棧和隊列都是非常有用的數據結構，掌握它們的實現和使用方法對于編寫高效的JavaScript代碼非常重要。

希望本文對你理解如何使用JavaScript鏈表實現棧和隊列有所幫助！