队列知识

1.队列的接口表示

 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  * @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 }

点击+复制代码

2.Node节点

 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=data;
14         this.next=node;
15     }
16 }

点击复制代码

 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=data;
14         this.next=node;
15     }
16 }

点击+复制代码

3.链队列主类(连式结构表示队列)

 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     @Override
14     public void clear() {
15         // TODO 置空
16         front=rear=null;
17     }
18     @Override
19     public boolean isEmpty() {
20         // TODO 判空
21         return front==null;
22     }
23     @Override
24     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     @Override
36     public Object peek() {
37         // TODO 查看对头元素
38         if (front!=null) {
39             return front.data;
40         }else{
41             return null;
42         }
43     }
44     @Override
45     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     @Override
59     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     @Override
70     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 LinkQueue implements IQueue{
 7     private Node front;//队头指针
 8     private Node rear;//队尾指针
 9     public LinkQueue() {
10         // TODO 初始化链队列
11         front=rear=null;
12     }
13     @Override
14     public void clear() {
15         // TODO 置空
16         front=rear=null;
17     }
18     @Override
19     public boolean isEmpty() {
20         // TODO 判空
21         return front==null;
22     }
23     @Override
24     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     @Override
36     public Object peek() {
37         // TODO 查看对头元素
38         if (front!=null) {
39             return front.data;
40         }else{
41             return null;
42         }
43     }
44     @Override
45     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     @Override
59     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     @Override
70     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 }

点击+复制代码

4.测试链队列

 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 /**
 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 }

点击+复制代码

测试代码：

5.使用循环单链表表示循环队列

5.1需要使用循环链表类

  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     @Override
109     public int remove(Object i) {
110         // TODO Auto-generated method stub
111         return 0;
112     }
113 
114 }

点击可复制

  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     @Override
109     public int remove(Object i) {
110         // TODO Auto-generated method stub
111         return 0;
112     }
113 
114 }

点击+可复制代码

5.2循环链队列

 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     @Override
15     public void clear() {
16         // TODO 置空
17         rear=cList.head;
18     }
19     @Override
20     public boolean isEmpty() {
21         // TODO 判空
22         return rear==cList.head;
23     }
24     @Override
25     public int length() {
26         // TODO 长度
27         return cList.length();
28     }
29 
30     @Override
31     public Object peek() {
32         // TODO 查看对头元素
33         if (!isEmpty()) {
34             return cList.get(0);
35         }
36         return null;
37     }
38     @Override
39     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     @Override
50     public void push(Object o) {
51         // TODO 入队
52         cList.insert(length(), o);
53         rear=new Node(cList.get(length()-1));
54     }
55     @Override
56     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 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     @Override
15     public void clear() {
16         // TODO 置空
17         rear=cList.head;
18     }
19     @Override
20     public boolean isEmpty() {
21         // TODO 判空
22         return rear==cList.head;
23     }
24     @Override
25     public int length() {
26         // TODO 长度
27         return cList.length();
28     }
29 
30     @Override
31     public Object peek() {
32         // TODO 查看对头元素
33         if (!isEmpty()) {
34             return cList.get(0);
35         }
36         return null;
37     }
38     @Override
39     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     @Override
50     public void push(Object o) {
51         // TODO 入队
52         cList.insert(length(), o);
53         rear=new Node(cList.get(length()-1));
54     }
55     @Override
56     public void display() {
57         // TODO 显示
58         if (!isEmpty()) {
59             cList.display();
60         }else {
61             System.out.println("此队列为空~");
62         }
63     }
64 
65 }

点击+复制代码

5.3 循环链队列的测试

 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 }

点击可复制代码

 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 }

点击+复制代码

5.4 测试

END! 缺少顺序表表示队列的情形