一、写在前面
数据结构中的队列应该是比较熟悉的了,就是先进先出,因为有序故得名队列,就如同排队嘛,在对尾插入新的节点,在对首删除节点.jdk集合框架也是提供也一个Queue的接口.这个接口代表一个队列.顺序队列:ArrayBlockingQueue,LinkedBlockingQueue.(上面两种是足色队列)还有一种是ConcurentLinkedQueue。
底层的实现由数组合链表两种的,数组的实现会有个弊端的,会造成假满的现象,开始的时候,队列为空的时候,对首引用变量个对尾的引用变量都为null,随着删除队列的元素,就会发生front+1,rear等于底层数组的容量了.在顺序的存储结构中,front总是保存这着队列中即将出队列的元素的索引,rear总是保存着即将进入队列的元素的索引.队列中的元素的个数就是rear-front的.在顺序的队列中,底层是数组,所以保存 的数据元素是不会改变的,改变的只有rear和front这两个引用变量.
这里采用链式存储可以有效的利用空间的,就是引用变量要占用额外的空间的.
队列的常用的操作:
1:初始化
2:返回队列的长度
3:添加元素
4:删除元素
5:访问对首的元素
6:访问队列的对尾的元素
7:判断队列是否为空
8:清空队列
二、自定义的实现
源码展示的比较清楚,就不用再多做介绍
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
public class LinkedQueue<T>{//自定义链队列--采用非静态内部类来表示链队列的数据节点private class Node{//表示链队列的数据节点 private T data;//指向下一个节点的引用private Node next; @SuppressWarnings("unused") public Node(){ }public Node(T data,Node next){ this.data=data; this.next=next; }}//定义链队列的对首和对尾的引用 private Node front; private Node rear; //定义链栈的大小private int size; //创建一个空的链对列public LinkedQueue(){ front=null; rear=null;}//以确定的元素来创建一个链对列,只有一个节点的public LinkedQueue(T element){front=new Node(element,null);//指向同一个元素rear=front;size++;}//返回链队列的大小public int length(){return size;}//返回链队列得对首的元素,不删除对首的元素public T elementFront(){if(!empty()){ return front.data;}else{ return null; }}//访问队列的最后一个元素public T elementRear(){if(!empty()){ return rear.data; }else{ return null; } }//返回当前的链对队列是否为空public boolean empty(){ return size==0; }//清空一个链队列public void clear(){ front=null; rear=null; size=0;}//插入链队列一个节点--对尾public void add(T element){ //如果链对列为空,就新建一个节点 if(front==null){ rear=new Node(element,null); front=rear; }else{ //动态创建新节点 Node newRear=new Node(element,null); rear.next=newRear; rear=newRear; }size++;}//删除链队列一个节点,返回删除后的节点public T remove(){ Node oldFront=front; front=front.next; oldFront.next=null; size--; return oldFront.data;}//返回队列public String toString(){ //如果链队列为空链队列是 if(empty()){ return "[]"; }else{ StringBuilder sBuilder=new StringBuilder("["); for(Node current=front;current!=null;current=current.next){ sBuilder.append(current.data.toString()+",");} int len=sBuilder.length();return sBuilder.delete(len-1, len).append("]").toString();}}public static void main(String[] args) { LinkedQueue<String> lQueue=new LinkedQueue<String>(); lQueue.add("aaa"); lQueue.add("bbb"); lQueue.add("ccc"); lQueue.add("ddd");System.out.println("返回队列的头结点的数值:"+lQueue.elementFront());System.out.println("返回队列的尾节点的数值:"+lQueue.elementRear());System.out.println(lQueue.length());System.out.println(lQueue);}} |
运行结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/HcJsJqJSSM/article/details/78503504
