1 package com.neusoft.Queue; 2 /** 3  * @author zhao-chj 4  * 队列的接口 5  */ 6 public interface IQueue { 7     public void clear(); 8     public boolean isEmpty(); 9     public int length();10     //查看队列的头而不移除11     public Object peek();12     //出队，移除队列的头元素13     public Object poll();14     //入队，把元素压入队列15     public void push(Object o);16     public void display();17 }

 1 package com.neusoft.Queue; 2  3 public class Node { 4     public Object data;// 数据域 5     public Node next;// 指针域 6     public Node() { //构造空节点 7         this(null,null); 8     } 9     public Node(Object data){//构造有一个参数的数据域10         this(data,null);11     }12     public Node(Object data,Node node){//构造数据域和指针域13         this.data=http://www.mamicode.com/data;14         this.next=node;15     }16 }

 1 package com.neusoft.Queue; 2 /** 3  * @author zhao-chj 4  *    链队列 5  */ 6 public class LinkQueue implements IQueue{ 7     private Node front;//队头指针 8     private Node rear;//队尾指针 9     public LinkQueue() {10         // TODO 初始化链队列11         front=rear=null;12     }13     @Override14     public void clear() {15         // TODO 置空16         front=rear=null;17     }18     @Override19     public boolean isEmpty() {20         // TODO 判空21         return front==null;22     }23     @Override24     public int length() {25         // TODO 长度26         Node p=front;27         int length=0;28         while(p!=null){//一直查询到队尾为止29             p=p.next;30             length++;31         }32         return length;33     }34 35     @Override36     public Object peek() {37         // TODO 查看对头元素38         if (front!=null) {39             return front.data;40         }else{41             return null;42         }43     }44     @Override45     public Object poll() {46         // TODO 出队,并返回出队数据元素47         if (front !=null) {48             Node p=front;49             front=front.next;50             if (p==rear) {51                 rear=null;52             }53             return p.data;54         }else {55             return null;56         }57     }58     @Override59     public void push(Object o) {60         // TODO 入队61         Node p=new Node(o);62         if (front !=null) {63             rear.next=p;64             rear=p;65         }else {66             front=rear=p;67         }68     }69     @Override70     public void display() {71         // TODO 显示72         if (!isEmpty()) {73             Node p= front;74             while(p!=rear.next){//从队头到队尾75                 System.out.print(p.data.toString()+" ");76                 p=p.next;77             }78         }else {79             System.out.println("次队列为空~");80         }81         82     }83 84 }

 1 package com.neusoft.Queue; 2 /** 3  * @author zhao-chj 4  * 测试连队列 5  */ 6 public class DebugLinkQueue { 7     public static void main(String[] args) { 8          LinkQueue Q = new LinkQueue(); 9          for (int i = 0; i < 10; i++) {10             Q.push(i);11         }12          System.out.println("队列中的各元素为");13          Q.display();14          System.out.println("查看队列是否为空！");15          if (!Q.isEmpty()) {16             System.out.println("非空");17         }18          System.out.println("队列长度为~"+Q.length());19          System.out.println("队头元素为~"+Q.peek());20          System.out.println("测试出队~");21          Q.poll();22          System.out.println("队头元素出队后的值为");23          Q.display();24          System.out.println("清除队列中所有元素~");25          Q.clear();26          if (Q.isEmpty()) {27             System.out.println("队列为空~");28         }29     }30 }

  1 package com.neusoft.Queue;  2 import com.neusoft.List.IList;  3 /**  4  * @author zhao-chj  5  * 循环单链表  6  */  7 public class CircleLinkList implements IList{  8     public Node head;  9     public CircleLinkList() { 10         // TODO 初始化 11         head=new Node();//初始化头结点 12         head.next=head; 13     } 14     @Override 15     public void clear() { 16         // TODO 清空 17         head.next=head; 18     } 19     @Override 20     public boolean isEmpty() { 21         // TODO 判空 22         return head.next.equals(head); 23     } 24     @Override 25     public int length() { 26         // TODO 长度 27         Node p =head.next; 28         int length=0; 29         while (!p.equals(head)) { 30             p=p.next; 31             length++; 32         } 33         return length; 34     } 35     @Override 36     public Object get(int i) { 37         // TODO 读取带头结点的循环链表中第i个数据元素 38         Node p=head.next; 39         int j=0; 40         while (!p.equals(head)&&j<i) { 41             p=p.next; 42             j++; 43         } 44         if (j>i||p.equals(head)) { 45             System.out.println("第"+i+"个元素不存在！"); 46         } 47         return p.data; 48     } 49  50     @Override 51     public void insert(int i, Object x) { 52         // TODO 带头结点的循环链表中第i个节点之前插入一个值为x的元素 53         Node p = head; 54         int j=-1;//第i个节点前驱位置 55         while ((!p.equals(head)||j==-1)&&j<i-1) { 56             p=p.next; 57             j++; 58         } 59         if (j>i-1||(p.equals(head)&&j!=-1)) { 60             System.out.println("插入位置不合法！"); 61         } 62         Node s =new Node(x); 63         s.next=p.next; 64         p.next=s; 65     } 66  67     @Override 68     public void remove(int i) { 69         // TODO 移除循环单链表中第i个元素的节点，注意i的范围 70         Node p=head;//p指向要删除节点的前驱节点 71         int j=-1; 72         while ((!p.next.equals(head)||j==-1)&&j<i-1) {//找前驱元素 73             p=p.next; 74             j++; 75         } 76         if (j>i-1||(p.next.equals(head)&&j!=-1)) { 77             System.out.println("删除位置不合法！"); 78         } 79         p.next=p.next.next; 80     } 81  82     @Override 83     public int indexOf(Object x) { 84         // TODO 查找值为x的元素，返回位置 85         Node p =head.next;//p指向首节点 86         int j=0; 87         while ((!p.equals(head))&&(!p.data.equals(x))) { 88             p=p.next; 89             j++; 90         } 91         if (!p.equals(head)) { 92             return j; 93         }else { 94             return -1; 95         } 96     } 97     @Override 98     public void display() { 99         // TODO 输出元素100         Node p =head.next;101         while (!p.equals(head)) {102             System.out.print(p.data+" ");103             p=p.next;104         }105         System.out.println();106     }107 108     @Override109     public int remove(Object i) {110         // TODO Auto-generated method stub111         return 0;112     }113 114 }

 1 package com.neusoft.Queue; 2 /** 3  * @author zhao-chj 4  *    循环链队列(采用带头结点的循链表表示) 5  */ 6 public class CircleLinkQueue implements IQueue{ 7     private Node rear;//队尾指针，指向队尾元素 8     private CircleLinkList cList; 9     public CircleLinkQueue() {10         // TODO 初始化链队列11         cList=new CircleLinkList();12         rear=cList.head;13     }14     @Override15     public void clear() {16         // TODO 置空17         rear=cList.head;18     }19     @Override20     public boolean isEmpty() {21         // TODO 判空22         return rear==cList.head;23     }24     @Override25     public int length() {26         // TODO 长度27         return cList.length();28     }29 30     @Override31     public Object peek() {32         // TODO 查看对头元素33         if (!isEmpty()) {34             return cList.get(0);35         }36         return null;37     }38     @Override39     public Object poll() {40         // TODO 出队,并返回出队数据元素41         if (!isEmpty()) {42             Object t=cList.get(0);43             cList.remove(0);44             return t;45         }46         return null;47         48     }49     @Override50     public void push(Object o) {51         // TODO 入队52         cList.insert(length(), o);53         rear=new Node(cList.get(length()-1));54     }55     @Override56     public void display() {57         // TODO 显示58         if (!isEmpty()) {59             cList.display();60         }else {61             System.out.println("此队列为空~");62         }63     }64 65 }

 1 package com.neusoft.Queue; 2 /** 3  * @author zhao-chj 4  * 测试循环链队列 5  */ 6 public class DebugCircleLinkQueue { 7     public static void main(String[] args) { 8          CircleLinkQueue Q = new CircleLinkQueue(); 9          for (int i = 0; i < 10; i++) {10             Q.push(i);11         }12          System.out.println("队列中的各元素为");13          Q.display();14          System.out.println("查看队列是否为空！");15          if (!Q.isEmpty()) {16             System.out.println("非空");17         }18          System.out.println("队列长度为~"+Q.length());19          System.out.println("队头元素为~"+Q.peek());20          System.out.println("测试出队~");21          Q.poll();22          System.out.println("队头元素出队后的值为");23          Q.display();24          System.out.println("清除队列中所有元素~");25          Q.clear();26          if (Q.isEmpty()) {27             System.out.println("队列为空~");28         }29     }30 }