特点：先进先出 后进后出

队列是一个有序的列表

  1. 可以通过数组跟列表进行实现（数组实现叫顺序存储，链表实现叫做链式存储）

  2. 遵循先入先出的原则

    数组实现

    分析：

  3. 数组需要记录数组的最大容量

  4. 需要队列的前端与后端标记变量 前端随着数据的输入而改变 后端随着数据的输出而改变

代码实现：(没有优化 数组不是环形对列 一次性对列)

  1. public class ArrayQueueDome {
  3.     public static void main(String[] args) {
  5.         ArrayQueue arr = new ArrayQueue(5);
  6.         arr.addArray(5);
  7.         arr.addArray(4);
  8.         arr.addArray(3);
  9.         arr.addArray(-1);
  10.         arr.addArray(1);
  11.         arr.addArray(1);
  12.         // 看看head数据是啥
  13.         System.out.println(arr.putArray());
  14.         System.out.println(arr.peek());
  15.         for (int i = 0; i < 6; i++)
  16.             System.out.println(arr.putArray());
  17.     }
  18. }
  19. //建立一个数组队列
  21. class ArrayQueue {
  22.     // 定义最大容量
  23.     private int maxSize;
  25.     // 队列的头尾
  26.     private int rear;
  27.     private int front;
  29.     // 创建队列
  30.     private int[] arr;
  32.     public int[] getArr() {
  33.         return arr;
  34.     }
  36.     // 创建队列的构造器
  37.     public ArrayQueue(int arrMaxSize) {
  38.         this.maxSize = arrMaxSize;
  39.         this.arr = new int[maxSize];
  40.         this.front = -1; // 指向头部的前一个位置
  41.         this.rear = -1;// 指向尾部的位置（就是队列的最后一个数据）
  42.     }
  44.     // 判断队列是否已经满了
  45.     public boolean isFull() {
  46.         return maxSize == rear + 1;
  47.     }
  49.     // 判断队列是否为空
  50.     public boolean isEmpty() {
  51.         return front == rear;
  52.     }
  54.     // 添加数据到队列（添加数据时变得只有rear 尾）
  55.     public void addArray(int i) {
  56.         // 添加时要先进行判断
  57.         if (isFull()) {
  58.             System.out.println("full!!!!");
  59.         } else {
  60.             rear++;
  61.             arr[rear] = i;
  62.         }
  63.     }
  65.     // 输出信息 （输出数据时变得只有front 头）
  66.     public int putArray() {
  67.         // 先进行判断队列是否为空
  68.         if (isEmpty()) {
  69.             throw new RuntimeException("empty!!!!");
  70.         } else {
  71.             front++;
  72.             return arr[front];
  73.         }
  74.     }
  76.     // 显示队列的头数据是什么
  77.     public int peek() {
  78.         return arr[front + 1];
  79.     }
  80. }

需要进行环形的更改：
代码如下：

  1. import java.util.Scanner;
  3. public class ArrayQueueDome {
  5.     public static void main(String[] args) {
  7.         // 测试一把
  8.         System.out.println("测试数组模拟环形队列的案例~~~");
  9.         // 创建一个环形队列
  10.         CircleArray queue = new CircleArray(5); // 说明设置 4, 其队列的有效数据最大是 3
  11.         char key = ' '; // 接收用户输入
  12.         Scanner scanner = new Scanner(System.in);//
  13.         boolean loop = true;
  14.         // 输出一个菜单
  15.         while (loop) {
  16.             System.out.println("s(show): 显示队列");
  17.             System.out.println("e(exit): 退出程序");
  18.             System.out.println("a(add): 添加数据到队列");
  19.             System.out.println("g(get): 从队列取出数据");
  20.             System.out.println("h(head): 查看队列头的数据");
  21.             key = scanner.next().charAt(0);// 接收一个字符
  22.             switch (key) {
  23.             case 's':
  24.                 queue.look();
  25.                 break;
  26.             case 'a':
  27.                 System.out.println("输出一个数");
  28.                 int value = scanner.nextInt();
  29.                 queue.addArray(value);
  30.                 break;
  31.             case 'g': // 取出数据
  32.                 try {
  33.                     int res = queue.putArray();
  34.                     System.out.printf("取出的数据是%d\n", res);
  35.                 } catch (Exception e) {
  36.                     // TODO: handle exception
  37.                     System.out.println(e.getMessage());
  38.                 }
  39.                 break;
  40.             case 'h': // 查看队列头的数据
  41.                 try {
  42.                     int res = queue.peek();
  43.                     System.out.printf("队列头的数据是%d\n", res);
  44.                 } catch (Exception e) {
  45.                     // TODO: handle exception
  46.                     System.out.println(e.getMessage());
  47.                 }
  48.                 break;
  49.             case 'e': // 退出
  50.                 scanner.close();
  51.                 loop = false;
  52.                 break;
  53.             default:
  54.                 break;
  55.             }
  56.         }
  57.         System.out.println("程序退出~~");
  58.     }
  60. }
  62. //建立一个数组队列
  64. class CircleArray {
  65.     // 定义最大容量
  66.     private int maxSize;
  67.     // 队列的头尾
  68.     private int rear;
  69.     private int front;
  71.     // 创建队列
  72.     private int[] arr;
  74.     public int[] getArr() {
  75.         return arr;
  76.     }
  78.     // 创建队列的构造器
  79.     public CircleArray(int arrMaxSize) {
  80.         this.maxSize = arrMaxSize;
  81.         this.arr = new int[maxSize];
  82.         this.front = 0; // 指向头部的前一个位置
  83.         this.rear = 0;// 指向尾部的位置（就是队列的最后一个数据）
  84.     }
  86.     // 判断队列是否满
  87.     public boolean isFull() {
  88.         return (rear + 1) % maxSize == front;
  89.     }
  91.     // 判断队列是否为空
  92.     public boolean isEmpty() {
  93.         return front == rear;
  94.     }
  96.     // 添加数据到队列（添加数据时变得只有rear 尾）
  97.     public void addArray(int i) {
  98.         // 添加时要先进行判断
  99.         if (isFull()) {
  100.             System.out.println("full!!!!");
  101.         } else {
  102.             arr[rear] = i;
  103.             // 将 rear 后移, 这里必须考虑取模
  104.             rear = (rear + 1) % maxSize;
  105.         }
  106.     }
  108.     // 输出信息 （输出数据时变得只有front 头）
  109.     public int putArray() {
  110.         // 先进行判断队列是否为空
  111.         if (isEmpty()) {
  112.             throw new RuntimeException("empty!!!!");
  113.         } else {
  114.             int value = arr[front];
  115.             front = (front + 1) % maxSize;
  116.             return value;
  117.         }
  118.     }
  120.     // 显示队列的头数据是什么
  121.     public int peek() {
  122.         return arr[front];
  123.     }
  125.     // 遍历数组
  126.     public void look() {
  127.         // 遍历
  128.         if (isEmpty()) {
  129.             System.out.println("队列空的，没有数据~~");
  130.             return;
  131.         }
  132.         // 思路：从 front 开始遍历，遍历多少个元素
  133.         // 动脑筋
  134.         for (int i = front; i < front + size(); i++) {
  135.             System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
  136.         }
  137.     }
  139.     // 求出当前队列有效数据的个数
  140.     public int size() {
  141.         return (rear + maxSize - front) % maxSize;
  142.     }
  143. }

链表实现

单：

  1. package cn.corgy.queue;
  3. public class LinkedListQueueDome {
  5.     public static void main(String[] args) {
  6.         HeroNode hero1 = new HeroNode(1, "王超", "hehehe");
  7.         HeroNode hero2 = new HeroNode(2, "1超", "2222");
  8.         HeroNode hero3 = new HeroNode(3, "2超", "11111");
  9.         HeroNode hero5 = new HeroNode(3, "2超", "修改的");
  10.         HeroNode hero4 = new HeroNode(4, "3超", "333333");
  11.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  12.         singleLinkedList.addByOrder(hero1);
  13.         singleLinkedList.addByOrder(hero3);
  14.         singleLinkedList.addByOrder(hero2);
  15.         singleLinkedList.addByOrder(hero2);
  16.         singleLinkedList.show();
  17.         System.out.println("************************************");
  18.         singleLinkedList.updateNode(hero5);
  19.         singleLinkedList.show();
  20.         System.out.println("************************************");
  21.         singleLinkedList.deleteNode(2);
  22.         singleLinkedList.show();
  23.     }
  24. }
  26. //创建单向链表
  27. class SingleLinkedList {
  28.     // 创建单向列表的头部 不进行数据的储存
  29.     private HeroNode head = new HeroNode(0, "", "");
  31.     /**
  32.      * 无序添加 与添加的顺序有关
  33.      * 
  34.      * @param heroNode 添加的节点
  35.      */
  36.     public void add(HeroNode heroNode) {
  37.         // 添加一个临时变量到辅助遍历全部的链表
  38.         HeroNode temp = head;
  39.         while (true) {
  40.             // 如果遍历到最后一个节点 next就会显示null
  41.             if (temp.next == null) {
  42.                 break;
  43.             }
  44.             // 没有找到向后移动进行索引
  45.             temp = temp.next;
  46.         }
  47.         // 跳出后进行赋值
  48.         temp.next = heroNode;
  49.     }
  51.     /**
  52.      * 有序添加 根据数据编号进行排序
  53.      * 
  54.      * @param heroNode 需要添加的节点
  55.      */
  56.     public void addByOrder(HeroNode heroNode) {
  57.         HeroNode temp = head;
  58.         while (true) {
  59.             // 如果添加的数据已经存在 打印信息 直接退出
  60.             if (temp.no == heroNode.no) {
  61.                 System.out.println("需要添加的节点" + heroNode.no + "已经存在");
  62.                 return;
  63.             }
  64.             if (temp.next == null) {
  65.                 break;
  66.             }
  67.             // 遍历 满足temp.no < heroNode.no && heroNode.no <temp.next.no
  68.             // 进行添加操作
  69.             if ((temp.no < heroNode.no && heroNode.no < temp.next.no)) {
  70.                 HeroNode temp2 = temp.next;
  71.                 temp.next = heroNode;
  72.                 heroNode.next = temp2;
  73.                 return;
  74.             }
  75.             // 加一进位
  76.             temp = temp.next;
  77.         }
  78.         temp.next = heroNode;
  79.     }
  81.     /**
  82.      * 修改节点信息
  83.      */
  84.     public void updateNode(HeroNode heroNode) {
  85.         // 判断是否空
  86.         if (head.next == null) {
  87.             System.out.println("链表为空~");
  88.             return;
  89.         }
  90.         // 通过遍历全部找到相同的编号值
  91.         HeroNode temp = head;
  92.         while (true) {
  93.             if (temp.next == null) {
  94.                 System.out.println("沒有你要修改的节点");
  95.                 return;
  96.             }
  97.             if (temp.next.no == heroNode.no) {
  98.                 temp.next.name = heroNode.name;
  99.                 temp.next.nickname = heroNode.nickname;
  100.                 return;
  101.             }
  102.             // 进位
  103.             temp = temp.next;
  104.         }
  105.     }
  107.     /**
  108.      * 根据编号删除某个节点
  109.      */
  110.     public void deleteNode(int no) {
  111.         HeroNode temp = head;
  112.         while (true) {
  113.             if (temp.next == null) {
  114.                 break;
  115.             }
  116.             // 删除的条件
  117.             if (no == temp.next.no) {
  118.                 if (temp.next.next == null) {
  119.                     temp.next = null;
  120.                     return;
  121.                 } else {
  122.                     // 跳过中间那个直接指向下一个
  123.                     temp.next = temp.next.next;
  124.                     return;
  125.                 }
  126.             }
  127.             temp = temp.next;
  128.         }
  129.         System.out.println("没有这个节点");
  130.     }
  132.     /**
  133.      * 链表的展示
  134.      */
  135.     public void show() {
  136.         // 先判断列表是否为空
  137.         if (head.next == null) {
  138.             System.out.println("队列为空");
  139.             return;
  140.         }
  141.         HeroNode temp = head.next;
  142.         while (true) {
  143.             // 如果遍历到最后一个节点 next就会显示null
  144.             if (temp == null) {
  145.                 break;
  146.             }
  147.             System.out.println(temp);
  148.             // 没有找到向后移动进行索引
  149.             temp = temp.next;
  150.         }
  151.     }
  152. }
  154. // 定义 HeroNode,每个 HeroNode 对象就是一个节点
  155. class HeroNode {
  156.     public int no;
  157.     public String name;
  158.     public String nickname;
  159.     public HeroNode next; // 指向下一个节点
  161.     // 构造器
  162.     public HeroNode(int no, String name, String nickname) {
  163.         this.no = no;
  164.         this.name = name;
  165.         this.nickname = nickname;
  166.     }
  168.     // 为了显示方法，我们重新 toString
  169.     @Override
  170.     public String toString() {
  171.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  172.     }
  173. }

  1. 求单链表的有效节点：

    1.  /**
    2.   * 统计链表的有效个数 有头的话要去头
    3.   * 
    4.   * @param head 头节点
    5.   * @return 返回有效的个数
    6.   */
    7.  public static int getLength(HeroNode head) {
    8.      if (head.next == null)
    9.          System.out.println("empty!!");
    10.      HeroNode temp = head.next;
    11.      int index = 0;
    12.      while (true) {
    13.          index++;
    14.          if (temp.next == null)
    15.              break;
    16.          temp = temp.next;
    17.      }
    18.      return index;
    19.  }
    20. }

  2. 查找单链表中倒数第K个节点

    1.  /**
    2.   * 查找单链表中倒数第K个节点 调用了前面的获取有效个数的方法
    3.   * 
    4.   * @param head   头节点
    5.   * @param lastNo 倒数的第K个值
    6.   * @return 返回节点信息
    7.   */
    8.  public static HeroNode findLastIndexNode(HeroNode head, int lastNo) {
    9.      if (head.next == null) {
    10.          System.out.println("链表为空");
    11.          return null;
    12.      }
    14.      // 先获取所需链表的有效长度
    15.      int size = getLength(head);
    16.      // 获取要查询的节点信息（size-lastNo）
    17.      int index = size - lastNo;
    18.      if (lastNo <= 0 || lastNo > size) {
    19.          return null;
    20.      }
    21.      // 获取
    22.      HeroNode cur = head.next;
    23.      for (int i = 0; i < index; i++) {
    24.          cur = cur.next;
    25.      }
    26.      return cur;
    27.  }

  3. 单链表的反转

    2.  /**
    3.   * 但链表进行翻转 <br>
    4.   * 思路:<br>
    5.   * 1.创建一个新的头做新的对象 <br>
    6.   * 2.将原本的链表依次向新的头进行插入<br>
    7.   * 3.将老的头的next替代新的头的next
    8.   *
    9.   * @param head 头节点
    10.   */
    11.  public static void reverseQueue(HeroNode head) {
    12.      // 其中空链表跟单节点列表不用进行翻转
    13.      if (head.next == null || head.next.next == null)
    14.          return;
    15.      HeroNode reverseNode = new HeroNode(0, "", "");
    16.      HeroNode cur = head.next;
    17.      HeroNode next = null;
    18.      // 遍历需要反转的列表进行定位
    19.      while (cur != null) {
    20.          next = cur.next;
    21.          cur.next = reverseNode.next;
    22.          reverseNode.next=cur;
    23.          cur = next;
    24.      }
    25.      head.next = reverseNode.next;
    26.  }
    27. }

  4. 从尾到头打印单链表

  5. 合并两个单链表 合并后依旧要有序


双**：

根据单列表进行了简单的修改 即可变成双向的列表 

  1. package cn.corgy.queue;
  3. public class DoubleLinkedQueueDome {
  5.     public static void main(String[] args) {
  6.         DoubleHeroNode hero1 = new DoubleHeroNode(1, "王超", "hehehe");
  7.         DoubleHeroNode hero2 = new DoubleHeroNode(2, "1超", "2222");
  8.         DoubleHeroNode hero3 = new DoubleHeroNode(3, "2超", "11111");
  9.         DoubleHeroNode hero5 = new DoubleHeroNode(3, "2超", "修改的");
  10.         DoubleHeroNode hero4 = new DoubleHeroNode(4, "3超", "333333");
  11.         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  12.         doubleLinkedList.addByOrder(hero1);
  13.         doubleLinkedList.addByOrder(hero3);
  14.         doubleLinkedList.addByOrder(hero4);
  15.         doubleLinkedList.addByOrder(hero2);
  16.         doubleLinkedList.show();
  17.         System.out.println("************************************");
  18.         doubleLinkedList.updateNode(hero5);
  19.         doubleLinkedList.show();
  20.         System.out.println("************************************");
  21.         doubleLinkedList.deleteNode(4);
  22.         doubleLinkedList.show();
  23.     }
  25. }
  27. //创建双向链表
  28. class DoubleLinkedList {
  29.     // 创建单向列表的头部 不进行数据的储存
  30.     private DoubleHeroNode head = new DoubleHeroNode(0, "", "");
  32.     public DoubleHeroNode getHead() {
  33.         return head;
  34.     }
  36.     /**
  37.      * 遍历双向链表
  38.      */
  39.     public void show() {
  40.         // 先判断列表是否为空
  41.         if (head.next == null) {
  42.             System.out.println("队列为空");
  43.             return;
  44.         }
  45.         DoubleHeroNode temp = head.next;
  46.         while (true) {
  47.             // 如果遍历到最后一个节点 next就会显示null
  48.             if (temp == null) {
  49.                 break;
  50.             }
  51.             System.out.println(temp);
  52.             // 没有找到向后移动进行索引
  53.             temp = temp.next;
  54.         }
  55.     }
  57.     /**
  58.      * 无序添加到列表的最后 与添加的顺序有关
  59.      * 
  60.      * @param heroNode 添加的节点
  61.      */
  62.     public void add(DoubleHeroNode heroNode) {
  63.         // 添加一个临时变量到辅助遍历全部的链表
  64.         DoubleHeroNode temp = head;
  65.         while (true) {
  66.             // 如果遍历到最后一个节点 next就会显示null
  67.             if (temp.next == null) {
  68.                 break;
  69.             }
  70.             // 没有找到向后移动进行索引
  71.             temp = temp.next;
  72.         }
  73.         // 跳出后进行赋值
  74.         temp.next = heroNode;
  75.         heroNode.pre = temp; // 双向的精髓
  76.     }
  78.     /**
  79.      * 有序添加 根据数据编号进行排序
  80.      * 
  81.      * @param heroNode 需要添加的节点
  82.      */
  83.     public void addByOrder(DoubleHeroNode heroNode) {
  84.         DoubleHeroNode temp = head;
  85.         while (true) {
  86.             // 如果添加的数据已经存在 打印信息 直接退出
  87.             if (temp.no == heroNode.no) {
  88.                 System.out.println("需要添加的节点" + heroNode.no + "已经存在");
  89.                 return;
  90.             }
  91.             if (temp.next == null) {
  92.                 break;
  93.             }
  94.             // 遍历 满足temp.no < heroNode.no && heroNode.no <temp.next.no
  95.             // 进行添加操作
  96.             if ((temp.no < heroNode.no && heroNode.no < temp.next.no)) {
  97.                 DoubleHeroNode temp2 = temp.next;
  98.                 // 前一个的下一节点为插入
  99.                 temp.next = heroNode;
  100.                 // 插入节点的下一个位为后一个
  101.                 heroNode.next = temp2;
  102.                 // 插入节点的前一个节点为前一个
  103.                 heroNode.pre = temp;
  104.                 // 插入节点的后一个的前一个节点为插入
  105.                 temp2.pre = heroNode;
  106.                 return;
  107.             }
  108.             // 加一进位
  109.             temp = temp.next;
  110.         }
  111.         temp.next = heroNode;
  112.     }
  114.     /**
  115.      * 修改节点信息
  116.      */
  117.     public void updateNode(DoubleHeroNode heroNode) {
  118.         // 判断是否空
  119.         if (head.next == null) {
  120.             System.out.println("链表为空~");
  121.             return;
  122.         }
  123.         // 通过遍历全部找到相同的编号值
  124.         DoubleHeroNode temp = head;
  125.         while (true) {
  126.             if (temp.next == null) {
  127.                 System.out.println("沒有你要修改的节点");
  128.                 return;
  129.             }
  130.             if (temp.next.no == heroNode.no) {
  131.                 temp.next.name = heroNode.name;
  132.                 temp.next.nickname = heroNode.nickname;
  133.                 return;
  134.             }
  135.             // 进位
  136.             temp = temp.next;
  137.         }
  138.     }
  140.     /**
  141.      * 根据编号删除某个节点
  142.      */
  143.     public void deleteNode(int no) {
  144.         DoubleHeroNode temp = head;
  145.         while (true) {
  146.             if (temp.next == null) {
  147.                 break;
  148.             }
  149.             // 删除的条件
  150.             if (no == temp.next.no) {
  151.                 if (temp.next.next == null) {// 如果是最后一各节点话直接进行删除
  152.                     temp.next = null;
  153.                     return;
  154.                 } else {
  155.                     // 跳过中间那个直接指向下一个
  156.                     temp.next = temp.next.next;
  157.                     temp.next.next.pre = temp;
  158.                     return;
  159.                 }
  160.             }
  161.             temp = temp.next;
  162.         }
  163.         System.out.println("没有这个节点");
  164.     }
  166. }
  168. //定义 HeroNode,每个 HeroNode 对象就是一个节点  （定义双向的链表）
  169. class DoubleHeroNode {
  170.     public int no;
  171.     public String name;
  172.     public String nickname;
  173.     public DoubleHeroNode next; // 指向下一个节点
  174.     public DoubleHeroNode pre; // 指向前一个节点
  176.     // 构造器
  177.     public DoubleHeroNode(int no, String name, String nickname) {
  178.         this.no = no;
  179.         this.name = name;
  180.         this.nickname = nickname;
  181.     }
  183.     // 为了显示方法，我们重新 toString
  184.     @Override
  185.     public String toString() {
  186.         return "DoubleHeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  187.     }
  188. }