第十三章：实战三：链表操作与栈队列算法-PHP程序员面试算法宝典

当前位置:　首页>> 技术小册>> PHP程序员面试算法宝典

第十三章：实战三：链表操作与栈队列算法

在编程面试中，链表、栈和队列作为基本的数据结构，不仅考察着候选人的理论基础，更考验其实践能力和算法思维。本章将深入剖析链表的基本操作、栈与队列的实现及其应用算法，旨在帮助PHP程序员在面试中从容应对相关考题，提升问题解决能力。

1. 链表基础

链表（Linked List）是一种常见的数据结构，由一系列节点（Node）组成，每个节点包含数据部分和指向列表中下一个节点的指针（或引用）。与数组相比，链表在插入和删除操作上更加高效，但访问任意位置元素的效率较低。

1.1 单链表

单链表是最简单的链表形式，每个节点只包含一个指向下一个节点的指针。

节点定义：

class ListNode {
    public $val;
    public $next;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

基本操作：
- 插入节点：在链表头部、尾部或指定位置插入新节点。
- 删除节点：删除链表中的指定节点，包括头节点和中间节点。
- 遍历链表：打印链表中的所有元素或执行其他遍历操作。

1.2 双向链表

双向链表（Doubly Linked List）在单链表的基础上，为每个节点增加了一个指向前一个节点的指针，使得节点可以双向遍历。

节点定义：

class DoublyListNode {
    public $val;
    public $prev;
    public $next;
    function __construct($val = 0, $prev = null, $next = null) {
        $this->val = $val;
        $this->prev = $prev;
        $this->next = $next;
    }
}

基本操作：与单链表类似，但插入和删除节点时需同时更新prev和next指针。

2. 栈与队列

栈（Stack）和队列（Queue）是两种特殊的线性表，它们在操作上有严格的限制。

2.1 栈

栈是一种后进先出（LIFO, Last In First Out）的数据结构。只能在一端（称为栈顶）进行插入（push）和删除（pop）操作。

实现方式：
- 使用数组：通过维护一个栈顶指针来实现。
- 使用链表：链表的头部或尾部作为栈顶，根据实现选择。

PHP实现（使用数组）：

class Stack {
    private $elements;
    function __construct() {
        $this->elements = [];
    }
    function push($element) {
        array_push($this->elements, $element);
    }
    function pop() {
        return array_pop($this->elements);
    }
    function isEmpty() {
        return empty($this->elements);
    }
    // 其他方法...
}

2.2 队列

队列是一种先进先出（FIFO, First In First Out）的数据结构。在队尾进行插入操作，在队头进行删除操作。

实现方式：
- 使用数组：通过维护队首和队尾两个指针来实现。
- 使用链表：链表头部作为队头，尾部作为队尾。

PHP实现（使用数组）：

class Queue {
    private $elements;
    private $front;
    private $rear;
    function __construct() {
        $this->elements = [];
        $this->front = 0;
        $this->rear = 0;
    }
    function enqueue($element) {
        array_push($this->elements, $element);
        $this->rear++;
    }
    function dequeue() {
        if ($this->isEmpty()) {
            throw new Exception("Queue is empty");
        }
        $this->front++;
        return array_shift($this->elements);
        // 注意：实际中可能需要更复杂的逻辑来保持数组连续，这里简化处理
    }
    function isEmpty() {
        return $this->front == $this->rear;
    }
    // 其他方法...
}

3. 链表操作算法

3.1 反转链表

反转单链表是链表操作中的基础问题，要求改变链表中节点的指向顺序，使得原本指向末尾的节点现在指向头部。

算法思路：使用迭代或递归方法，逐个改变节点指针的指向。

3.2 合并两个有序链表

给定两个已排序的链表，合并成一个新的有序链表并返回。

算法思路：使用迭代或递归，比较两个链表头部节点的值，选择较小的节点加入到新链表中，并移动对应链表的头指针。

3.3 删除链表中的节点（给定值）

删除链表中所有等于给定值的节点。

算法思路：遍历链表，当遇到等于给定值的节点时，通过修改前一个节点的next指针来跳过该节点。

4. 栈与队列算法

4.1 栈的使用：括号匹配

检查一个字符串中的括号是否有效并正确嵌套。

算法思路：使用栈来跟踪尚未匹配的左括号，遇到右括号时检查栈顶元素是否匹配。

4.2 队列的使用：层序遍历二叉树

利用队列实现二叉树的层序遍历。

算法思路：将根节点加入队列，然后不断从队列中取出节点，并依次将其左右子节点（如果存在）加入队列，直到队列为空。

5. 实战练习

问题一：反转一个单链表。
问题二：合并两个已排序的链表。
问题三：使用栈实现一个中缀表达式求值器。
问题四：使用队列实现一个广度优先搜索（BFS）算法，用于解决图的遍历问题。

6. 总结

链表、栈和队列作为基础的数据结构，在算法设计和编程面试中扮演着重要角色。通过本章的学习，你应该能够熟练掌握这些数据结构的基本操作及其常见算法的实现，从而在面试中展现出扎实的编程功底和问题解决能力。未来，你还可以继续探索这些数据结构在复杂算法和数据结构（如图、树等）中的应用，不断提升自己的编程技能。