• 算法3：链表实现双端队列

    • 我们在算法2中已经使用Node实现了链表的功能。此时，我们进一步对链表进行延伸。题目：“使用单链表实现队列，实现先进先出的功能”。
    • 解题思路： 既然是链表，那么必然有一个头节点和尾结点。先进先出，那就是从头节点取数据，从尾节点添加数据 
      1. package code.code_02;
      2.  
      3. /**
      4.  * 使用单链表设计出队列
      5.  */
      6. public class SingleNodeQueue {
      7.  
      8.     private Node head; //当前队列的头
      9.     private Node tail;   //当前队列的尾
      10.     private int size;
      11.  
      12.     public SingleNodeQueue () {
      13.         head = null;
      14.         tail = null;
      15.         size = 0;
      16.     }
      17.     //用于单链表的节点
      18.     private class Node {
      19.         public V data;
      20.         public Node next;
      21.  
      22.         Node (V _data){
      23.             this.data = _data;
      24.         }
      25.         public V getData() {
      26.             return data;
      27.         }
      28.     }
      29.  
      30.     public boolean isEmpty () {
      31.         return size == 0 ? true : false;
      32.     }
      33.  
      34.     public int size () {
      35.         return size;
      36.     }
      37.  
      38.     //获取链表的头
      39.     public V peek ()
      40.     {
      41.         Node node = null;
      42.         Node next = null;
      43.         if (head == null) {
      44.             System.out.println("当前队列还没有设置元素");
      45.             tail = null;
      46.             return null;
      47.         }
      48.         else {
      49.             //提前记录下头节点和头节点的持有的下一个节点的引用
      50.             node = head;
      51.             next = head.next;
      52.             //将头节持有的下一个节点引用释放掉
      53.             head.next = null;
      54.             //因为头节点的下一个节点之前被记录过
      55.             //此时，头节点head会释放掉原始的内存对象
      56.             // 并且来到新的头节点位置（也就是之前的第二个节点）
      57.             head = next;
      58.             size--;
      59.         }
      60.         //因为node是局部变量，方法调用完成以后，node所对应的内存对象会被回收
      61.         return node.getData();
      62.     }
      63.  
      64.     //获取链表的头, 此方法是对peek进行的优化
      65.     public V peek1 ()
      66.     {
      67.         V value = null;
      68.         if (head == null) {
      69.             System.out.println("当前队列还没有设置元素");
      70.             tail = null;
      71.             return null;
      72.         }
      73.         else {
      74.             value = head.getData();
      75.             /**
      76.              * 此处优化非常的美妙, 一句话抵得上peek()方法中的4句
      77.              *  node = head;
      78.              *  next = head.next;
      79.              *  head.next = null;
      80.              *  head = next;
      81.              */
      82.             head = head.next;
      83.             size--;
      84.         }
      85.         return value;
      86.     }
      87.  
      88.     //设置链表元素
      89.     public void offer (V data) {
      90.         Node node = new Node(data);
      91.         if (tail == null) {
      92.             head = node;
      93.             tail = node;
      94.         }
      95.         else {
      96.             tail.next = node;
      97.             tail = node;
      98.         }
      99.         size++;
      100.     }
      101.  
      102.     public static void main(String[] args) {
      103.         SingleNodeQueue queue = new SingleNodeQueue<>();
      104.         queue.offer(1);
      105.         queue.offer(2);
      106.         queue.offer(3);
      107.         System.out.println(queue.size());
      108.  
      109.         do {
      110.             System.out.println("获取单向队列的元素： " + (queue.peek()));
      111.             System.out.println("测试当前队列长度" + queue.size());
      112.         }while(queue.size() > 0);
      113.  
      114.  
      115.         System.out.println("================测试泛型，优化后的peek================================");
      116.  
      117.         SingleNodeQueue queue1 = new SingleNodeQueue<>();
      118.         queue1.offer("test 1");
      119.         queue1.offer("test 2");
      120.         queue1.offer("test 3");
      121.         System.out.println(queue1.size());
      122.  
      123.         do {
      124.             System.out.println("获取单向队列的元素： " + (queue1.peek1()));
      125.             System.out.println("测试当前队列长度" + queue1.size());
      126.         }while(queue1.size() > 0);
      127.  
      128.  
      129.     }
      130. }

      打印信息如下：


      3
      获取单向队列的元素： 1
      测试当前队列长度2
      获取单向队列的元素： 2
      测试当前队列长度1
      获取单向队列的元素： 3
      测试当前队列长度0
      ================测试泛型，优化后的peek================================
      3
      获取单向队列的元素： test 1
      测试当前队列长度2
      获取单向队列的元素： test 2
      测试当前队列长度1
      获取单向队列的元素： test 3
      测试当前队列长度0

      Process finished with exit code 0
       

    • 下面继续延伸。题目 “使用双向链表的知识，设计一个双向队列。要求是队列的头和队列的尾，都可以添加数据并且取数据” 
      1. package code1.code_02;
      2.  
      3. /**
      4.  * 使用双链表设计一个双向队列，使对象的头节点和尾节点都可以
      5.  * 添加/弹出节点元素
      6.  */
      7. public class DoubleNodeQueue04 {
      8.  
      9.     private Node head; //当前队列的头
      10.     private Node tail;   //当前队列的尾
      11.     private int size;
      12.  
      13.     public DoubleNodeQueue04() {
      14.         head = null;
      15.         tail = null;
      16.         size = 0;
      17.     }
      18.  
      19.     //双链表
      20.     private static class Node {
      21.         public V data;
      22.         public Node last;
      23.         public Node next;
      24.  
      25.         Node (V _data){
      26.             this.data = _data;
      27.         }
      28.         public V getData() {
      29.             return data;
      30.         }
      31.     }
      32.  
      33.     public boolean isEmpty () {
      34.         return size == 0;
      35.     }
      36.  
      37.     public int size () {
      38.         return size;
      39.     }
      40.  
      41.     //从队列头部取元素
      42.     public V peekHead ()
      43.     {
      44.         V value = null;
      45.         if (head == null) {
      46.             System.out.println("当前队列还没有设置元素");
      47.             return value;
      48.         }
      49.  
      50.         value = head.getData();
      51.         if (head == tail) {
      52.             head = null;
      53.             tail = null;
      54.         }
      55.         else {
      56.             //此时, 队列的第二个元素成为新的
      57.             //头节点head
      58.             head = head.next;
      59.         }
      60.         size--;
      61.         return value;
      62.     }
      63.  
      64.     //从队列尾部取元素
      65.     public V peekTail ()
      66.     {
      67.         V value = null;
      68.         if (tail == null) {
      69.             System.out.println("当前队列还没有设置元素");
      70.             return value;
      71.         }
      72.  
      73.         value = tail.getData();
      74.             //如果头和尾相等，说明队列只有一个元素等价与tail.last == null;
      75.         if (head == tail) {
      76.                 head = null;
      77.                 tail = null;
      78.         } else {
      79.                 tail = tail.last;
      80.                 tail.next = null;
      81.         }
      82.         size--;
      83.         return value;
      84.     }
      85.  
      86.     //从尾节点添加队列元素
      87.     public void pushTail (V data) {
      88.         Node node = new Node<>(data);
      89.         if (head == null) {
      90.             head = node;
      91.             tail = node;
      92.         }
      93.         else {
      94.             tail.next = node;
      95.             //双向链表组成的队列新增部分
      96.             //当前节点需要持有之前的尾结点对象引用
      97.             node.last = tail;
      98.             //添加完成以后, 尾节点需要移动到新添加的节点node处，
      99.             //此时，新添加的node成为尾节点tail
      100.             tail = node;
      101.         }
      102.         size++;
      103.     }
      104.  
      105.     //从头节点添加队列元素
      106.     public void pushHead (V data) {
      107.         Node node = new Node<>(data);
      108.         if (head == null) {
      109.             head = node;
      110.             tail = node;
      111.         }
      112.         else {
      113.             /**
      114.              * 从头结点添加队列新元素，那么之前的头节点变成第二个元素
      115.              * 因此，之前的头结点head.last需要持有新节点对象引用node
      116.              * 新节点node.next需要持有之间的头结点
      117.              */
      118.             head.last = node;
      119.             node.next = head;
      120.             //添加完成以后, 头节点需要移动到新添加的节点node处，
      121.             //此时，新添加的node成为头节点head
      122.             head = node;
      123.         }
      124.         size++;
      125.     }
      126.  
      127.     public static void main(String[] args) {
      128.         DoubleNodeQueue04 queue = new DoubleNodeQueue04<>();
      129.         //demo1, 测试从尾部添加元素，头部获取元素。 先进先出
      130.         queue.pushTail(1);
      131.         queue.pushTail(2);
      132.         queue.pushTail(3);
      133.  
      134.         System.out.println("=============测试双向队列尾部添加元素，头部取元素—----先进先出==========================");
      135.         do {
      136.             System.out.println("获取单向队列的元素： " + (queue.peekHead()));
      137.         }while(queue.size > 0);
      138.  
      139.         //demo2, 测试从尾部添加元素，从尾部获取元素
      140.         queue.pushTail(-1);
      141.         queue.pushTail(-2);
      142.         queue.pushTail(-3);
      143.  
      144.         System.out.println("=============测试双向队列尾部添加元素，尾部获取元素—----后进先出==========================");
      145.         do {
      146.             System.out.println("获取单向队列的元素： " + (queue.peekTail()));
      147.         }while(queue.size > 0);
      148.  
      149.         //demo3, 测试从头部添加元素，头部取元素
      150.         queue.pushHead(11);
      151.         queue.pushHead(12);
      152.         queue.pushHead(13);
      153.         System.out.println("=============测试双向队列头部添加元素，头部获取元素—----后进先出==================");
      154.         do {
      155.             System.out.println("获取单向队列的元素： " + (queue.peekHead()));
      156.         }while(queue.size > 0);
      157.  
      158.         //demo4, 测试从头部添加元素, 尾部取元素
      159.         queue.pushHead(21);
      160.         queue.pushHead(22);
      161.         queue.pushHead(23);
      162.         System.out.println("=============测试双向队列头部添加元素，尾部获取元素—----先进先出==========================");
      163.         do {
      164.             System.out.println("获取单向队列的元素： " + (queue.peekTail()));
      165.         }while(queue.size > 0);
      166.     }
      167. }

      打印信息如下：

     
    =============测试双向队列尾部添加元素，头部取元素—----先进先出==========================
    获取单向队列的元素： 1
    获取单向队列的元素： 2
    获取单向队列的元素： 3
    =============测试双向队列尾部添加元素，尾部获取元素—----后进先出==========================
    获取单向队列的元素： -3
    获取单向队列的元素： -2
    获取单向队列的元素： -1
    =============测试双向队列头部添加元素，头部获取元素—----后进先出==================
    获取单向队列的元素： 13
    获取单向队列的元素： 12
    获取单向队列的元素： 11
    =============测试双向队列头部添加元素，尾部获取元素—----先进先出==========================
    获取单向队列的元素： 21
    获取单向队列的元素： 22
    获取单向队列的元素： 23

    Process finished with exit code 0
     

  • 相关阅读:
    【工具】电脑网络连接正常，但是有些页面无法登录，如何解决？
    【LeetCode】Day177-统计一致字符串的数目
    通过内网穿透，在Windows 10系统下搭建个人《我的世界》服务器公网联机
    图Graph的存储、图的广度优先搜索和深度优先搜索（待更新）
    【C++】C++职工信息管理系统
    [LeetCode]剑指 Offer 48. 最长不含重复字符的子字符串
    前端人员不要只知道KFC，你应该了解 BFC、IFC、GFC 和 FFC
    【数据集的制作】VOC2007数据集格式的转换(voc2yolo)与划分
    node.js+室内装修风格选择系统 毕业设计-附源码211552
    【Spring Cloud】多数据源配置
  • 原文地址：https://blog.csdn.net/chen_yao_kerr/article/details/127955694