目录

1.概念

2.应用

3.核心操作

①offer()：入队

②poll()：出队

③peek()：查看队首元素

4.分类

①基于数组的队列：循环队列（每次出队都要进行数组元素搬移，效率低）

②基于链表的队列：结构更优。

5.接口实现

6.方法实现

6.1.入队操作

6.2.出队操作

6.3.查看队首元素

6.4.toString()方法

7.总代码实现

8.测试实现

1.概念 

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

队列具有先进先出FIFO原则。

• 入队列：进行插入操作的一端称队尾(Tail/Rear)
• 出队列：进行删除操作的一端称对头(Head/Front)

2.应用

排队买饭。

3.核心操作

①offer()：入队

②poll()：出队

③peek()：查看队首元素

4.分类

①基于数组的队列：循环队列（每次出队都要进行数组元素搬移，效率低）

②基于链表的队列：结构更优。

5.接口实现

不管哪种队列，操作方法都一样：入，出，查。故抽象为一个接口。

public interface Queue {//入队操作void offer(int value);//出队操作int poll();//查看队首元素int peek();
}

6.方法实现

public class LinkedQueue implements Queue{private Node head;private Node tail;private int size;private class Node{private int data;private Node next;public Node(int data) {this.data = data;}}//具体方法实现//...
}

6.1.入队操作

/* 入队操作* @param value*/
@Override
public void offer(int value) {//新元素Node node = new Node(value);if(head == null) {head = tail = node;} else {tail.next = node;tail = node;}size++;
}

6.2.出队操作

/* 出队操作* @return*/
@Override
public int poll() {if(size == 0) {throw new NoSuchElementException("队列为空！");}int oldValue = head.data;Node tmpHead = head;head = head.next;tmpHead.next = null;size--;return oldValue;
}

6.3.查看队首元素

/* 查看队首元素* @return*/
@Override
public int peek() {if(size == 0) {throw new NoSuchElementException("队列为空！");}return head.data;
}

6.4.toString()方法

public String toString() {StringBuilder sb = new StringBuilder();sb.append("front[");Node node = head;while(node != null) {sb.append(node.data);if(node.next != null) {sb.append(",");}node = node.next;}sb.append("]tail");return sb.toString();
}

7.总代码实现

import java.util.NoSuchElementException;public class LinkedQueue implements Queue{private Node head;private Node tail;private int size;private class Node{private int data;private Node next;public Node(int data) {this.data = data;}}/* 入队操作* @param value*/@Overridepublic void offer(int value) {//新元素Node node = new Node(value);if(head == null) {head = tail = node;} else {tail.next = node;tail = node;}size++;}/* 出队操作* @return*/@Overridepublic int poll() {if(size == 0) {throw new NoSuchElementException("队列为空！");}int oldValue = head.data;Node tmpHead = head;head = head.next;tmpHead.next = null;size--;return oldValue;}/* 查看队首元素* @return*/@Overridepublic int peek() {if(size == 0) {throw new NoSuchElementException("队列为空！");}return head.data;}public String toString() {StringBuilder sb = new StringBuilder();sb.append("front[");Node node = head;while(node != null) {sb.append(node.data);if(node.next != null) {sb.append(",");}node = node.next;}sb.append("]tail");return sb.toString();}
}

8.测试实现

public class QueueTest {public static void main(String[] args) {Queue queue = new LinkedQueue();queue.offer(1);queue.offer(3);queue.offer(5);System.out.println(queue); //front[1,3,5]tailqueue.poll();System.out.println(queue); //front[3,5]tail}
}