队列是一个有序列表，可以用数组或链表来实现，遵循先入先出的原则

  1. /**
  2.  * 队列
  3.  */
  4. public interface Queue {
  6.     /**
  7.      * 判断队列是否为空
  8.      */
  9.     boolean isEmpty();
  11.     /**
  12.      * 判断队列是否已满
  13.      */
  14.     boolean isFull();
  16.     /**
  17.      * 添加数据
  18.      */
  19.     void add(int o);
  21.     /**
  22.      * 取出数据
  23.      */
  24.     int get();
  26.     /**
  27.      * 队列元素个数
  28.      */
  29.     int size();
  31.     /**
  32.      * 显示队列数据
  33.      */
  34.     void show();
  36.     /**
  37.      * 显示队列头数据
  38.      */
  39.     int showHead();


数组实现队列

  1. /**
  2.  * 数组实现队列
  3.  */
  4. public class ArrayQueue implements Queue {
  6.     /**
  7.      *  队列容量（空余一个空间）
  8.      */
  9.     private int maxSize;
  11.     /**
  12.      * 队列头指针：指向队列的第一个元素
  13.      */
  14.     private int head;
  16.     /**
  17.      * 队列尾指针：指向队列的最后一个元素的后一个位置
  18.      */
  19.     private int tail;
  21.     /**
  22.      * 存放数据
  23.      */
  24.     private int[] arr;
  26.     public ArrayQueue(int size) {
  27.         maxSize = size + 1;
  28.         arr = new int[maxSize];
  29.         head = 0;
  30.         tail = 0;
  31.     }
  33.     /**
  34.      * 判断队列是否为空
  35.      * @return
  36.      */
  37.     @Override
  38.     public boolean isEmpty() {
  39.         return head == tail;
  40.     }
  42.     /**
  43.      * 判断队列是否已满
  44.      * @return
  45.      */
  46.     @Override
  47.     public boolean isFull() {
  48.         return (tail + 1) % maxSize == head;
  49.     }
  51.     /**
  52.      * 添加数据
  53.      * @param o
  54.      */
  55.     @Override
  56.     public void add(int o) {
  57.         if (isFull()) {
  58.             System.out.println("添加失败，队列已满！");
  59.             return;
  60.         }
  61.         arr[tail] = o;
  62.         tail = (tail + 1) % maxSize;
  63.     }
  65.     /**
  66.      * 取出数据
  67.      * @return
  68.      */
  69.     @Override
  70.     public int get() {
  71.         if (isEmpty()) {
  72.             throw new RuntimeException("取出失败，队列已空！");
  73.         }
  74.         int getValue = arr[head];
  75.         head = (head + 1) % maxSize;
  76.         return getValue;
  77.     }
  79.     /**
  80.      * 队列元素个数
  81.      * @return
  82.      */
  83.     @Override
  84.     public int size() {
  85.         return (tail - head + maxSize) % maxSize;
  86.     }
  88.     /**
  89.      * 显示队列数据
  90.      */
  91.     @Override
  92.     public void show() {
  93.         for (int i = head; i< head + size(); i++) {
  94.             System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
  95.         }
  96.     }
  98.     /**
  99.      * 显示队列头数据
  100.      * @return
  101.      */
  102.     @Override
  103.     public int showHead() {
  104.         if (isEmpty()) {
  105.             throw new RuntimeException("队列头为空！");
  106.         }
  107.         return arr[head];
  108.     }
  110.     public static void main(String[] args) {
  111.         ArrayQueue queue = new ArrayQueue(3);
  112.         Scanner scanner = new Scanner(System.in);
  113.         boolean loop = true;
  114.         while (loop) {
  115.             System.out.print("【数组实现队列】显示队列(s)、添加数据(a)、取出数据(g)、队列头数据(h)、队列元素个数(l)、退出(e)：");
  116.             char key = scanner.next().charAt(0);
  117.             switch (key) {
  118.                 case 's': queue.show(); break;
  119.                 case 'a':
  120.                     System.out.print("请输入一个数：");
  121.                     int value = scanner.nextInt();
  122.                     queue.add(value);
  123.                     break;
  124.                 case 'g':
  125.                     try {
  126.                         System.out.println("取出的数据是：" + queue.get());
  127.                     } catch (Exception e) {
  128.                         System.out.println(e.getMessage());
  129.                     }
  130.                     break;
  131.                 case 'h':
  132.                     try {
  133.                         System.out.println("头数据是：" + queue.showHead());
  134.                     } catch (Exception e) {
  135.                         System.out.println(e.getMessage());
  136.                     }
  137.                     break;
  138.                 case 'l': System.out.println("队列元素个数是：" + queue.size()); break;
  139.                 case 'e':
  140.                     scanner.close();
  141.                     loop = false;
  142.                     break;
  143.                 default: break;
  144.             }
  145.         }
  146.         System.out.println("程序退出。。。");
  147.     }
  149. }


链表实现队列

  1. /**
  2.  * 链表实现队列
  3.  */
  4. public class LinkedListQueue implements Queue {
  6.     /**
  7.      * 队列单个节点
  8.      */
  9.     private class Node {
  10.         private int data;
  11.         private Node next;
  13.         public Node(int data) {
  14.             this.data = data;
  15.         }
  17.         @Override
  18.         public String toString() {
  19.             return "Node{" + "data=" + data + '}';
  20.         }
  21.     }
  23.     /**
  24.      *  队列容量
  25.      */
  26.     private int maxSize;
  28.     /**
  29.      * 队列头指针：指向队列的第一个节点
  30.      */
  31.     private Node head;
  33.     /**
  34.      * 队列尾指针：指向队列的最后一个节点
  35.      */
  36.     private Node tail;
  38.     /**
  39.      * 队列元素个数
  40.      */
  41.     private int realSize;
  43.     public LinkedListQueue(int size) {
  44.         this.maxSize = size;
  45.         this.realSize = 0;
  46.         this.head = null;
  47.         this.tail = null;
  48.     }
  50.     /**
  51.      * 判断队列是否为空
  52.      * @return
  53.      */
  54.     @Override
  55.     public boolean isEmpty() {
  56.         return realSize == 0;
  57.     }
  59.     /**
  60.      * 判断队列是否已满
  61.      * @return
  62.      */
  63.     @Override
  64.     public boolean isFull() {
  65.         return realSize == maxSize;
  66.     }
  68.     /**
  69.      * 添加数据
  70.      * @param o
  71.      */
  72.     @Override
  73.     public void add(int o) {
  74.         if (isFull()) {
  75.             System.out.println("添加失败，队列已满！");
  76.             return;
  77.         }
  78.         Node node = new Node(o);
  79.         // 如果队列为空
  80.         if (isEmpty()) {
  81.             head = node;
  82.             tail = node;
  83.         } else {
  84.             tail.next = node;
  85.             tail = node;
  86.         }
  87.         realSize++;
  88.     }
  90.     /**
  91.      * 取出数据
  92.      * @return
  93.      */
  94.     @Override
  95.     public int get() {
  96.         if (isEmpty()) {
  97.             throw new RuntimeException("取出失败，队列已空！");
  98.         }
  99.         int tmp = head.data;
  100.         head = head.next;
  101.         realSize--;
  102.         // 队列为空时，队列尾指针置为null
  103.         if (realSize == 0) {
  104.             tail = null;
  105.         }
  106.         return tmp;
  107.     }
  109.     /**
  110.      * 队列元素个数
  111.      * @return
  112.      */
  113.     @Override
  114.     public int size() {
  115.         return realSize;
  116.     }
  118.     /**
  119.      * 显示队列数据
  120.      */
  121.     @Override
  122.     public void show() {
  123.         if (head == null) {
  124.             System.out.println("队列为空！");
  125.             return;
  126.         }
  127.         for(Node temp = head; temp != null; temp = temp.next) {
  128.             System.out.println(temp);
  129.         }
  130.     }
  132.     /**
  133.      * 显示队列头数据
  134.      * @return
  135.      */
  136.     @Override
  137.     public int showHead() {
  138.         if (isEmpty()) {
  139.             throw new RuntimeException("队列头为空！");
  140.         }
  141.         return head.data;
  142.     }
  144.     public static void main(String[] args) {
  145.         LinkedListQueue queue = new LinkedListQueue(3);
  146.         Scanner scanner = new Scanner(System.in);
  147.         boolean loop = true;
  148.         while (loop) {
  149.             System.out.print("【链表实现队列】显示队列(s)、添加数据(a)、取出数据(g)、队列头数据(h)、队列元素个数(l)、退出(e)：");
  150.             char key = scanner.next().charAt(0);
  151.             switch (key) {
  152.                 case 's': queue.show(); break;
  153.                 case 'a':
  154.                     System.out.print("请输入一个数：");
  155.                     int value = scanner.nextInt();
  156.                     queue.add(value);
  157.                     break;
  158.                 case 'h':
  159.                     try {
  160.                         System.out.println("头数据是：" + queue.showHead());
  161.                     } catch (Exception e) {
  162.                         System.out.println(e.getMessage());
  163.                     }
  164.                     break;
  165.                 case 'g':
  166.                     try {
  167.                         System.out.println("取出的数据是：" + queue.get());
  168.                     } catch (Exception e) {
  169.                         System.out.println(e.getMessage());
  170.                     }
  171.                     break;
  172.                 case 'l': System.out.println("队列元素个数是：" + queue.size()); break;
  173.                 case 'e':
  174.                     scanner.close();
  175.                     loop = false;
  176.                     break;
  177.                 default: break;
  178.             }
  179.         }
  180.         System.out.println("程序退出。。。");
  181.     }
  183. }