AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

《恋上数据结构第1季》二叉树代码实现

2022-05-25 74
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 《恋上数据结构第1季》二叉树代码实现
数据结构与算法笔记目录： 《恋上数据结构》 笔记目录

想加深 Java 基础推荐看这个： Java 强化笔记目录

我的《恋上数据结构》源码（第1季 + 第2季）： https://github.com/szluyu99/Data_Structure_Note

我们实现一个 通用二叉树（BinaryTree.java），里面包含所有二叉树类通用的代码。后面学到的 二叉搜索树、AVL树、红黑树 都需要继承这个 通用二叉树。

这一篇是代码实现，先了解 二叉树基础知识；

BinaryTree 基础

package com.mj.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树
 */
@SuppressWarnings("unchecked")
public class BinaryTree<E> {
    protected int size; // 元素数量
    protected Node<E> root; // 根节点

    /**
     * 访问器接口 ——> 访问器抽象类
     * 增强遍历接口
     */
    /*public static interface Visitor<E>{
        void visit(E element);
    }*/
    public static abstract class Visitor<E> {
        boolean stop;
        // 如果返回true，就代表停止遍历
        public abstract boolean visit(E element);
    }

    /**
     * 内部类，节点类
     */
    public static class Node<E> {
        E element;      // 元素值
        Node<E> left;   // 左节点
        Node<E> right;  // 右节点
        Node<E> parent; // 父节点

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() { // 是否叶子节点
            return left == null && right == null;
        }

        public boolean hasTwoChildren() { // 是否有两个子节点
            return left != null && right != null;
        }

        public boolean isLeftChild(){ // 判断自己是不是左子树
            return parent!=null && this==parent.left;
        }
        public boolean isRightChild(){ // 判断自己是不是右子树
            return parent!=null && this==parent.right;
        }
        /*
         * 返回兄弟节点
         */
         public Node<E> sibling() { // 红黑树中用到, 返回兄弟节点
            if (isLeftChild()) {
                return parent.right;
            }
            
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }    
    }
    
    /**
     * 元素的数量
     */
    public int size() {
        return size;
    }

    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空所有的元素
     */
    public void clear() {
        root = null;
        size = 0;
    }
    
    /**
     * 创建节点的方法，用于给AVL树创建节点
     */
    protected Node<E> createNode(E element, Node<E> parent){
        return new Node<>(element, parent); // 默认返回一个通用节点
    }
    
}

遍历（先序、中序、后序、层次遍历）

先序遍历: preorder()

/**
 * 前序遍历(递归)
 */
public void preorder(Visitor<E> visitor) {
    if (visitor == null) return;
    preorder(root, visitor);
}
public void preorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor.stop) return;
    // 根
    visitor.stop = visitor.visit(node.element);
    // 左
    preorder(node.left, visitor);
    // 右
    preorder(node.right, visitor);
}

中序遍历: inorder()

/**
 * 中序遍历(递归)
 */
public void inorder(Visitor<E> visitor) {
    if (visitor == null) return;
    inorder(root, visitor);
}
public void inorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor.stop) return;
    // 左
    inorder(node.left, visitor);
    // 根
    if (visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
    // 右
    inorder(node.right, visitor);
}

后序遍历: postorder()

/**
 * 后序遍历(递归)
 */
public void postorder(Visitor<E> visitor) {
    if (visitor == null) return;
    postorder(root, visitor);
}
public void postorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor.stop) return;
    // 左
    postorder(node.left, visitor);
    // 右
    postorder(node.right, visitor);
    // 根
    if (visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
}

层次遍历: levelOrder()

/**
 * 层次遍历(队列)
 */
public void levelOrder(Visitor<E> visitor){
    if(root == null || visitor.stop) return;
    Queue<Node<E>> queue = new LinkedList<>(); // 队列
    queue.offer(root);
    
    while(!queue.isEmpty()){
        Node<E> node = queue.poll();
        if(visitor.visit(node.element)) return;
        
        if(node.left != null) {
            queue.offer(node.left);
        }
        if(node.right != null) {
            queue.offer(node.right);
        }
    }
}

求二叉树的高度: height()

递归实现

/**
 * 求树的高度(递归)
 */
public int height() {
    return height(root);
}
public int height(Node<E> node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

迭代实现

/**
 * 求树的高度高度(迭代)
 */
public int height() {
    if (root == null) return 0;
    // 存储每一层的元素数量, root!=null, 则首层必然有1个元素
    int levelSize = 1;
    int height = 0; // 树的高度
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        levelSize--;
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
        if (levelSize == 0) { // 即将要访问下一层
            levelSize = queue.size(); // 下一层的元素数量
            height++;
        }
    }
    return height;
}

是否为完全二叉树: isComplaete()

/**
 * 是否是完全二叉树
 */
public boolean isComplete() {
    if (root == null) return false;

    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    // leaf代表是否要求后面都是叶子节点
    // 比如遍历到一个节点 left == null && right == null
    //  或者是 left != null && right == null
    // 则要求这个节点后面的节点都是叶子节点
    boolean leaf = false;
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        // 要求是叶子结点，但是当前节点不是叶子结点
        if (leaf && !node.isLeaf()) {
            return false;
        }
        if (node.left != null) {
            queue.offer(node.left);
        } else if (node.right != null) {
            // node.left == null && node.right != null
            return false;
        }
        if (node.right != null) {
            queue.offer(node.right);
        } else {
            // node.left == null && node.right == null
            // node.left != null && node.right == null
            leaf = true; // 要求后面都是叶子节点
        }
    }
    return true;
}

求二叉树的节点

前驱节点: predecessor()

在这里插入图片描述

/**
 * 前驱节点: 中序遍历时的前一个节点
 * 求前驱节点
 */
protected Node<E> predecessor(Node<E> node) {
    if (node == null) return null;

    // 前驱节点在左子树中(left.right.right.right....)
    Node<E> p = node.left;
    if (p != null) {
        // 左子树不为空,则找到它的最右节点
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    // 能来到这里说明左子树为空, 则从父节点、祖父节点中寻找前驱节点
    // 当父节点不为空, 且某节点为父节点的左子节点
    // 则顺着父节点找, 直到找到【某结点为父节点或祖父节点的右子树中】时
    while (node.parent != null && node.parent.left == node) {
        node = node.parent;
    }

    // 来到这里有以下两种情况:
    // node.parent == null    无前驱, 说明是根结点
    // node.parent...right == node 找到【某结点为父节点或祖父节点的右子树中】
    // 那么父节点就是某节点的前驱节点
    return node.parent;
}

后继节点: successor()

在这里插入图片描述

/**
 * 后继节点: 中序遍历时的后一个节点
 * 求后继节点
 */
protected Node<E> successor(Node<E> node) {
    if (node == null) return null;
    // 后继节点与前驱节点正好相反

    // 后继节点在右子树中（node.right.left.left...）
    if (node.right != null) {
        Node<E> p = node.right;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    // 来到这里说明没有右节点, 则从父节点、祖父节点中寻找后继节点
    // 当父节点不为空, 且某节点为父节点的右子节点
    // 则顺着父节点找, 直到找到【某结点在父节点或祖父节点的左子树中】时
    while (node.parent != null && node.parent.right == node) {
        node = node.parent;
    }

    // 来到这里有以下两种情况:
    // node.parent == null 无前驱，说明是根结点
    // node.parent.left == node 找到【某结点在父节点或祖父节点的左子树中】
    // 那么父节点就是某节点的后继节点
    return node.parent;
}

BinaryTreeInfo 工具

这是 MJ 老师自己写的一款工具，可以方便的打印二叉树，git 地址如下：https://github.com/CoderMJLee/BinaryTrees。

/**
 * BinaryTreeInfo 工具，用来打印二叉树
 */
@Override
public Object root() {
    return root;
}
@Override
public Object left(Object node) {
    return ((Node<E>)node).left;
}
@Override
public Object right(Object node) {
    return ((Node<E>)node).right;
}
@Override
public Object string(Object node) {
    Node<E> myNode = (Node<E>)node;
    String parentStr = "null";
    if(myNode.parent != null){
        parentStr = myNode.parent.element.toString();
    }
    return myNode.element + "_p(" + parentStr + ")";
}

二叉树完整源码

package com.mj.tree;

import java.util.LinkedList;
import java.util.Queue;
import com.mj.printer.BinaryTreeInfo;

/**
 * 二叉树(通用)
 */
@SuppressWarnings("unchecked")
// 实现BinaryTreeInfo接口是为了使用打印二叉树的工具，非必须
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size; // 元素数量
    protected Node<E> root; // 根节点

    /**
     * 访问器接口 ——> 访问器抽象类
     * 增强遍历接口
     */
    /*public static interface Visitor<E>{
        void visit(E element);
    }*/
    public static abstract class Visitor<E> {
        boolean stop;
        // 如果返回true，就代表停止遍历
        public abstract boolean visit(E element);
    }

    /**
     * 内部类，节点类
     */
    public static class Node<E> {
        E element;      // 元素值
        Node<E> left;   // 左节点
        Node<E> right;  // 右节点
        Node<E> parent; // 父节点

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() { // 是否叶子节点
            return left == null && right == null;
        }

        public boolean hasTwoChildren() { // 是否有两个子节点
            return left != null && right != null;
        }
        public boolean isLeftChild(){ // 判断自己是不是左子树
            return parent!=null && this==parent.left;
        }
        public boolean isRightChild(){ // 判断自己是不是右子树
            return parent!=null && this==parent.right;
        }
        /*
         * 返回兄弟节点
         */
         public Node<E> sibling() { // 红黑树中用到, 返回兄弟节点
            if (isLeftChild()) {
                return parent.right;
            }
            
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }
    }


    /**
     * 元素的数量
     */
    public int size() {
        return size;
    }

    /**
     * 是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空所有的元素
     */
    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * 前序遍历
     */
    public void preorder(Visitor<E> visitor) {
        if (visitor == null) return;
        preorder(root, visitor);
    }
    public void preorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        // 根
        visitor.stop = visitor.visit(node.element);
        // 左
        preorder(node.left, visitor);
        // 右
        preorder(node.right, visitor);
    }

    /**
     * 中序遍历
     */
    public void inorder(Visitor<E> visitor) {
        if (visitor == null) return;
        inorder(root, visitor);
    }
    public void inorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        // 左
        inorder(node.left, visitor);
        // 根
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        // 右
        inorder(node.right, visitor);
    }

    /**
     * 后序遍历
     */
    public void postorder(Visitor<E> visitor) {
        if (visitor == null) return;
        postorder(root, visitor);
    }
    public void postorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        // 左
        postorder(node.left, visitor);
        // 右
        postorder(node.right, visitor);
        // 根
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * 层次遍历
     */
    public void levelOrder(Visitor<E> visitor) {
        if (root == null || visitor.stop) return;
        Queue<Node<E>> queue = new LinkedList<>(); // 队列
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) return;

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 求树的高度(递归)
     */
    public int height1() {
        return height1(root);
    }
    public int height1(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height1(node.left), height1(node.right));
    }

    /**
     * 求树的高度高度(迭代)
     */
    public int height() {
        if (root == null) return 0;
        int levelSize = 1; // 存储每一层的元素数量
        int height = 0; // 树的高度
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (levelSize == 0) { // 即将要访问下一层
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    /**
     * 是否是完全二叉树
     */
    public boolean isComplete() {
        if (root == null) return false;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        // leaf代表是否要求后面都是叶子节点
        // 比如遍历到一个节点 left == null && right == null
        //  或者是 left != null && right == null
        // 则要求这个节点后面的节点都是叶子节点
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            // 要求是叶子结点，但是当前节点不是叶子结点
            if (leaf && !node.isLeaf()) {
                return false;
            }
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                // node.left == null && node.right != null
                return false;
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                // node.left == null && node.right == null
                // node.left != null && node.right == null
                leaf = true; // 要求后面都是叶子节点
            }
        }
        return true;
    }

    /**
     * 前驱节点: 中序遍历时的前一个节点
     * 求前驱节点
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;

        // 前驱节点在左子树中(left.right.right.right....)
        Node<E> p = node.left;
        if (p != null) {
            // 左子树不为空,则找到它的最右节点
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }

        // 能来到这里说明左子树为空, 则从父节点、祖父节点中寻找前驱节点
        // 当父节点不为空, 且某节点为父节点的左子节点
        // 则顺着父节点找, 直到找到【某结点为父节点或祖父节点的右子树中】时
        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }

        // 来到这里有以下两种情况:
        // node.parent == null 无前驱, 说明是根结点
        // node.parent...right == node 找到【某结点为父节点或祖父节点的右子树中】
        // 那么父节点就是某节点的前驱节点
        return node.parent;
    }

    /**
     * 后继节点: 中序遍历时的后一个节点
     * 求后继节点
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;
        // 后继节点与前驱节点正好相反

        // 后继节点在右子树中（node.right.left.left...）
        if (node.right != null) {
            Node<E> p = node.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        // 来到这里说明没有右节点, 则从父节点、祖父节点中寻找后继节点
        // 当父节点不为空, 且某节点为父节点的右子节点
        // 则顺着父节点找, 直到找到【某结点在父节点或祖父节点的左子树中】时
        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }

        // 来到这里有以下两种情况:
        // node.parent == null 无前驱，说明是根结点
        // node.parent.left == node 找到【某结点在父节点或祖父节点的左子树中】
        // 那么父节点就是某节点的后继节点
        return node.parent;
    }
    
    /**
     * 创建节点的方法，用于给AVL树创建节点
     */
    protected Node<E> createNode(E element, Node<E> parent){
        return new Node<>(element, parent); // 默认返回一个通用节点
    }

    /**
     * BinaryTreeInfo 工具，用来打印二叉树
     */
    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>) node;
        String parentStr = "null";
        if (myNode.parent != null) {
            parentStr = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentStr + ")";
    }
}
文章标签：
Java
开发工具
git
算法
关键词：
数据结构代码
数据结构二叉树
数据结构代码实现
数据结构二叉树代码
恋上数据结构代码
萌宅鹿同学
目录
相关文章
2的n次方_
|
14天前
|
存储 机器学习/深度学习
【数据结构】二叉树全攻略，从实现到应用详解
本文介绍了树形结构及其重要类型——二叉树。树由若干节点组成，具有层次关系。二叉树每个节点最多有两个子树，分为左子树和右子树。文中详细描述了二叉树的不同类型，如完全二叉树、满二叉树、平衡二叉树及搜索二叉树，并阐述了二叉树的基本性质与存储方式。此外，还介绍了二叉树的实现方法，包括节点定义、遍历方式（前序、中序、后序、层序遍历），并提供了多个示例代码，帮助理解二叉树的基本操作。
2的n次方_
38 13
【数据结构】二叉树全攻略，从实现到应用详解
小徐在进步
|
11天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
25 6
小徐在进步
|
11天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识，涵盖单链表的定义、优点与缺点，并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现，并提供了尾插法和头插法建立单链表的方法，帮助读者深入理解单链表的基本原理与应用技巧。
小徐在进步
33 6
小徐在进步
|
11天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表：顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表，使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作，并提供了具体代码示例。静态分配方式下顺序表的长度固定，而动态分配则可根据需求调整大小。此外，还总结了顺序表的优点，如随机访问效率高、存储密度大，以及缺点，如扩展不便和插入删除操作成本高等特点。
小徐在进步
43 5
小徐在进步
|
11天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
14 3
小徐在进步
|
11天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
46 3
小徐在进步
|
11天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
17 2
小徐在进步
|
11天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现，涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例，展示了如何高效地处理顺序表数据结构的各种问题。
小徐在进步
13 1
小徐在进步
|
9天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
28 8
2的n次方_
|
13天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
14 0
【数据结构】栈和队列的深度探索，从实现到应用详解