目录

1：普通队列的代码实现

1. 概念

2 .队列的使用

3 .队列模拟实现

2.循环队列

1.环形队列通常使用数组实现。

 2.模拟实现

3.双端队列

1：普通队列的代码实现

1. 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）

2 .队列的使用

3 .队列模拟实现

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public interface MyQueue <E>{//入队列void offer(E val);//出队列E poll();//查看队列头元素E peek();}

import java.util.NoSuchElementException;public class LinkedQueue <E> implements MyQueue<E>{private Node head;private Node tail;private int size;class Node{//E val;Node next;public Node(E val) {this.val = val;}}@Overridepublic String toString() {return super.toString();}@Overridepublic void offer(E val) {Node node = new Node(val);if(head == null){head = tail = node;}else {tail.next = node;tail = tail.next;}size++;}@Overridepublic E poll() {if(size == 0){throw new NoSuchElementException("没有元素哦~");}E val = head.val;head = head.next;size--;return val;}@Overridepublic E peek() {if(size == 0){throw new NoSuchElementException("没有元素哦~");}return head.val;}
}

2.循环队列

1.环形队列通常使用数组实现。

 2.模拟实现

import practice_3_22.MyQueue;import java.util.NoSuchElementException;public class LoopQueue <E> implements MyQueue<E> {//存放元素的数组private Object [] data;//指向队列的头部，是最先出队列的元素private int head;//指向队尾元素的下一个位置private int tail;//
//    private int size;public LoopQueue(int capacity) {this.data = new Object[capacity+1];}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("[");//int index = tail == 0?data.length-1:tail-1;for (int i = head; i != tail;) {sb.append(data[i]);if(i!= index){sb.append(",");}i = (i+1) % data.length;}sb.append("]");return sb.toString();}@Overridepublic void offer(E val) {if(ifFull()){throw new IllegalStateException("元素满了哦~");}data[tail] = val;tail = (tail + 1) % data.length;
//        size++;}@Overridepublic E poll() {if(isEmpty()){throw new NoSuchElementException("没有元素哦~");}E val = (E) data[head];head = (head+1) % data.length;
//        size--;return val;}public int size(){return (tail - head + data.length) % data.length;//        if(isEmpty()){
//            return 0;
//        }else if(tail > head){
//            return tail-head;
//        }else {
//            return tail+data.length - head;
//        }}private boolean isEmpty(){if (head == tail) {return true;}return false;}private boolean ifFull() {return (tail+ 1)% data.length == head;}@Overridepublic E peek() {if(isEmpty()){throw new NoSuchElementException("没有元素哦~");}return (E) data[head];}
}

3.双端队列

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现