数据结构——java实现队列
顺序队列：
概念：
队列是一种先进先出的线性表，只允许在一端插入，另一端删除。允许插入的一端称为队尾，允许删除的一端称为队头
顺序队列的实现：
1 import org.junit.jupiter.api.Test;
2
3 /**
4 * 顺序队列
5 * @author wydream
6 *
7 */
8
9 public class QueueSequence {
10
11 private String[] arr;//队列数组
12 private int end=0;//队尾标志
13
14 //向队列中添加元素
15 public void push(String[] arr,String value) {
16 if(end<arr.length) {
17 arr[end]=value;
18 end++;
19 return;
20 }else {
21 System.out.println("队列已经满了");
22 return;
23 }
24
25 }
26
27 //取出队列元素
28 public String pop(String[] arr) {
29 String rs;
30 if(arr[0]==null) {
31 System.out.println("队列为空,请先向队列中添加元素");
32 return null;
33 }else {
34 rs=arr[0];
35 arr[0]=null;
36 move(arr);
37 return rs;
38 }
39 }
40
41 //队列元素向前移动
42 public void move(String[] arr) {
43 for(int i=0;i<arr.length-1;i++) {
44 if(arr[i+1]!=null) {
45 arr[i]=arr[i+1];
46 }else{
47 arr[i]=null;
48 break;
49 }
50 }
51 }
52
53
54
55
56 @Test
57 public void test() {
58 String[] arr=new String[10];
59 push(arr,"北京");
60 push(arr,"上海");
61 push(arr,"广东");
62 push(arr,"杭州");
63 push(arr,"苏州");
64 push(arr,"扬州");
65 pop(arr);
66 pop(arr);
67 pop(arr);
68 pop(arr);
69 }
70
71 }循环队列：
概念：
- 顺序队列的不足：顺序队列在进行插入操作时，直接在队尾插入就可以，此时时间复杂度为O(1)，但是在出列是在队头，即下标为0的位置，也就意味着队列中所有的元素都得向前移动，此时时间复杂度为0(n)，效率较低。
- 队列出列时不需要所有的元素都移动，引入两个指针即可，一个头指针front指向队头元素，一个尾指针rear指向队尾元素，此时队列出列只需移动指针即可。但是此种情况下会出现一种溢出情况（如下图），此时队列中任然是有空间的可以存放元素的，但是尾指针已经溢出，于是就有了循环队列。
- front指向队头，rear指向队尾的下一个位置；队为空的判断：front==rear；队为满的判断：(rear+1)%MAXSIZE==front
实现循环队列：
1 /**
2 * java实现循环队列
3 * @author wydream
4 *
5 */
6
7 import org.junit.jupiter.api.Test;
8
9 public class QueueArray {
10
11 Object[] arr=new Object[10];;//对象数组，队列最多存储a.length-1个对象
12 int front=0;//队首下标
13 int rear=0;//队尾下标
14
15 /**
16 * 将一个对象追加到队列尾部
17 */
18 public boolean enqueue(Object obj) {
19 if((rear+1)%arr.length==front) {
20 return false;
21 }
22 arr[rear]=obj;
23 rear=(rear+1)%arr.length;
24 return true;
25
26 }
27
28 //出队列
29 public Object dequeue() {
30 if(rear==front) {
31 return null;
32 }
33 Object obj=arr[front];
34 front=(front+1)%arr.length;
35 return obj;
36 }
37
38 @Test
39 public void test() {
40 QueueArray q=new QueueArray();
41 System.out.println(q.enqueue("北京"));
42 System.out.println(q.enqueue("上海"));
43 System.out.println(q.enqueue("广东"));
44 System.out.println(q.enqueue("深圳"));
45 for(int i=0;i<4;i++){
46 System.out.println(q.dequeue());
47 }
48 }
49
50
51 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录