数据结构篇04、队列及其两种底层实现

咱们知道部队这种数据结构是先进先出的特性；本章咱们经过前两部分介绍的动态数组和链表别离结束部队这种数据结构；

java的util库中Queue接口的结束之一LinkedList便是一个链表，APP优先部队Prioritjava模拟器yQueue底层结束是堆，java编译器也便是数组；

1、定义部队接口，规则部队需求结束的办法

部队接口如下所示，办法的效果见注释；APP

public interface Queue<Eapprove> {
//取得元素个数
int getSize();
//判数据结构c言语版别是否为空
boolean isEmpty();
//元素入部队
void enqueue(E e);
//元素出部队
E dequeue();
//检查队首元素
E getFront();
}

2数据结构实验一线性表实验报告、动态数组结束的部队

动态数组结束的部队如下所示，需求留心的点便是咱们定义的部队是一个先进先出的数据结构；

其实功用的结束首要便是对咱们链表逆序榜首部分结束的动态数组api的一层封装，这儿咱们以数组头为部队头，数组尾为部队尾；链表数据结构

enqueue入队办法application便是调用array的addLast办法，往数组尾增加元素；

dequeue出队办法数组函数的使用办法便是调用array的removeFirst办法，从数组头移除元素；

getFront检查队首元素便是调用array的getFirst办法，查找数组头元素；

pub链表完成栈lic class Arrjava面试题a数据结构教程第5版李春葆答案yQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(iappearancent capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
@Override
public intAPP getSize(){
return array.getSize();
}
@Override
public boolean iappearsEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.get链表和数组的差异Capacity()java初学;
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeJavaue(){
return array.removeFijava编译器rst();
}
@Override
public E getFront(){
return array.getFirst()Java;
}
@Override
public String toString(){
StringBuil数据结构严蔚敏der res = new StringBuilder();
res.append("Queue: ");
res.append("front [");
for(int i =数组词 0 ; i < array.getSize() ; i ++){
res.append(arrajava怎么读y.get(i));
if(i != array.getSize() - 1)
res.append(", ");
}
res.append("] tail");
return res.tapplicationoString();
}
public static void main(String[] args){
ArrayQueue<数组函数的使用办法Integer> queue = new ArrayQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.pr链表c言语intln(q数据结构知识点总结ueue);
if数据结构与算法(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}

3、循环数组结束的部队

上一部分咱们结束java环境变量配置的部队其实是有很大的优化的，例如咱们移java初学除队首元数据结构c言语版素后，后边的元素都要往前移动一位，这样时刻复杂度便是O(n)等级的，咱们能够经过一个循环数组来结束部队，确保入队和出队的时刻复杂度都为O(1);

循环数组结束的部队如下所示，这儿咱们不再运用封装好的动态数组，而是从头结束一遍循环数组的逻辑；

data标明存储元素的数组；

front和tail标明数组中数据结构数组头和apple数组链表逆序尾的索引，front标明数组头元素的方位，tail标明数组尾马上增加元素的方appreciate位，咱们经过保护这两个索引，就能够直接经过索引结束入队和出队，然后也就结束了O(1)的时刻复杂度；

size标明部队中元素的个数；

其间两个结构办法，一个带参数结构办法能够传入部队的容量，另一个无参结构办法默许的容量为10；

getCapacity回数组初始化来部队的容量，咱们发现这儿是data.length – 1，原因是循环数组有一个方位咱们不能运用，便是java就业培训班当部队元素满了之后，应该把frontjava怎么读索引前一个java言语方位空出来；

isEmpty判别数组是否为空，直接经过froapplent和tail索引是否持平即可，相同这儿也解释了求容量时为什么要将front前一个方位空出来，假设不空出来，满了之后也会发生f数组词ront==tail，就会发生紊乱；

enqueue入队函数，首要判别是否需求扩容，然后往tail索引处增加元素ejavascript即可，接着保护一下tail索引和数据结构size元素个数，由数组c言语于这儿是循环数组，因而需求对data.length取模；
dequeue出队函数，将front索引置空，然后保护一下front索引和size元素个数，终究判appointment别是否需求缩容；

getFront检查队首元素，直接回来front索引处元素即可；

resize扩容缩容办法，新建数组，然后将原数组中的悉数元素仿制至新数组，终究将数组引用数据结构与算法指向新数组，一同保护一下front和tail两个索引；

终究重写to数组指针String办法打印部队中悉数元素，便于检查部队；

public clas数据结构严蔚敏第二版课后答案s LoopappointmentQueue<E> implements Queue<E> {
private E[] data;
private int front, tail;
priapp装置下载vate int size;
pu链表完成栈blic LoopQueue数据结构c言语版第二版课后答案(int capacity){
data = (E[])new Object[capacity + 1链表排序];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
t数据结构his(10);
}
public int getCapacity(){
return data.lengt链表逆序h - 1;
}
@Override
public boolean isEmpty(){
reapproveturn front == tail;
}
@Override
public int getSize(){
return size;
}
@Override
public void ejava怎么读nqueue(E e){
if((tail + 1) % data.length == front)
resize(getCapacity() * 2);
data[tail] = e;
tail = (taijava编译器l + 1) % data.lengthappointment;
size ++;
}
@Override
public E dequeue(){
if(app装置下载isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue链表数据结构.");
E ret = data[f数据结构c言语版第二版课后答案ront];
data[appreciatefront] = null;
front = (front + 1) % data.length;
size --;
if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
resize(getCapacity() / 2);
return ret;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is数组和链表的差异 empty.")appointment;
return data[front];
}
private void resize(int newCapacity){
E[] newData = (E[])new Objec数据结构严蔚敏第二版课后答案t[newCapacity + 1];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[(i + front) % data.length];
data = newData;
front = 0;
tail = size;
}
@Override
public String toString(){
StringBuilder res = new S数据结构题库及答案tringBuilder();
res.append(String.format("Queue: size = %d , capacity = %dn", size, getCapacity()));
res.append("appearancefront [");
for(int i = front ; i != tail ;appointment i = (i +appear 1链表) % data.length){
res.append(data[i]);
if((i + 1) % data.length != tail)
res.ap数据结构c言语版pend(", ");
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args){
LoopQueue<Integer> queue = new LoopQueue<>(5);
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.prapp装置下载intln(queue);
if(i % 3 == 2){
queue.dequeue();
System.数组指针out.println(qu链表回转eue);
}
}
}
}

4、链表结束的部队

链表结束的部队如下所示，这儿咱们并没有运用第二部分结束的链表，而是从头封装了一个链表，咱们第二部分数组词结束的链表只保护了一个虚拟头节点，导致往链表尾部增加元素appstore是O(n)时刻复杂度的操作，咱们从头封装的appstore这个链数据结构表保护了head头节点和tail尾节点两个节点链表完成栈，数组和链表的差异能够保链表不具有的特点是证从链表头取元素和往链表尾增加元素的操作都是O(1)时刻复杂度的操作；

Node节点类，成员变量包括元素e和节点next，三个结构函数可按需运用，toString打印节点中元素的值；

head和tail两个节点别离指向链表头元素和链表尾元素，siz链表的创建e标明部队元素个数；

enqueue入队操作分两种情况，当tail==null，也便是链表数组的定义为空，此刻直接将Java新增加的节点置为tail，然后让head=tail即可；当tail不为null，直接将tail的next指向新增加的元素，然后将tail指向tail.next，终究保护一下size；

dequeue出队操作，首要保存一下原头节点，然后将head指向head的next，假设head=数组词=null阐明链表为空了，此刻保护一下tail也置为null，最数组公式终保护一下size；

getFront检查队首元素直接回来headjava基础知识点的成员变量e即可；

终究重写toString办法打印部队元素，便于检查部队；

pu链表排序blic class LinkedListQu数据结构题库及答案eue<E> implements Queue数组c言语<E> {
private class Node{
public E e;
public Node nextjavascript;
public Node(E e, Node next){
this.数据结构严蔚敏e = e;
this.next = next;
}
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String tappearoString(){
return e.toString();
}
}
private Node head, tail;
private i数据结构与算法nt size;
public Linked链表结构ListQueue(){
head = null;
tail = null;
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
@Override
public void enqueue(E e){
if(tail == nullapple){
tail = new Node(e);
head = tail;
}
else{
tail.next = new Node(e);
tail = tail.next;
}
size ++;
}
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot de数组函数的使用办法queue from an empty queue.");
Node retNode = head;
head = head.next;
retNode.next = null;
if(head == null)
tail = null;
size --;
return retNode.e;
}数组函数的使用办法
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queu链表不具有的特点是e is empty.");
return head.appeare;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(数据结构实验一线性表实验报告"Queue: front ");
Node cur = head;
while(cappointmentur != null) {
res.ap数组公式pend(cur + "->");
cur = capp装置下载ur.next;
}
res.append("NULL tail");
return res.toString();
}
public static void main(String[] args){
LinkedListQueue<Integer> queue = new Linked数组和链表的差异ListQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out数据结构题库及答案.printapp装置下载ln(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}