队列
队列性质
-
队列（Queue）也是一种特殊的线性表
-
在超市、食堂需要排队一样，我们总是排成一列，先到的人就排在前面，后来的人就排在后面，越前面的人越先完成任务，这就是队列，队列有队头和队尾：
秉承先来后到的原则，队列中的元素只能从队尾进入，只能从队首出去，也就是说，入队顺序为1、2、3、4，那么出队顺序也一定是1、2、3、4，所以队列是一种先进先出（FIFO，First In, First Out）的数据结构。
队列也可以使用链表和顺序表来实现，只不过使用链表的话就不需要关心容量之类的问题了，会更加灵活一些：
需要同时保存队首和队尾两个指针，因为是单链表，所以队首需要存放指向头结点的指针，因为需要的是前驱结点，而队尾则直接是指向尾结点的指针即可，后面只需要直接在后面拼接就行。
队列的属性
private final Node<E> head = new Node<>(null);队列头首位- 以下是一个队列节点
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
队列的插入
-
入队思路
-
入队代码
Node<E> last = head;当一开始队列毫无元素时, 队首和队尾就是一样的while (last.next != null)入队直接丢到最后一个结点的屁股后面就行了;当目前节点有值时就不断指向下一个last.next = new Node<>(element);创建一个新节点, 插入队尾
public void offer(E element) { //入队操作
Node<E> last = head;
while (last.next != null) //入队直接丢到最后一个结点的屁股后面就行了
last = last.next;
last.next = new Node<>(element);
}
队列的出队
-
出队思路
-
出队代码
E e = head.next.element;因为队列的出队和入队都各有一个方向
public E poll() { //出队操作
if (head.next == null) //如果队列已经没有元素了，那么肯定是没办法取的
throw new NoSuchElementException("队列为空");
E e = head.next.element;
head.next = head.next.next; //直接从队首取出
return e;
}
总代码
-
Main代码
import ClassStudy.LinkQueue;
public class Main {
public static void main(String[] args) {
LinkQueue<String> stack = new LinkQueue<>();
stack.offer("AA22");//队首
stack.offer("BB31");
stack.offer("CC22");//队尾
System.out.println(stack.poll());
System.out.println(stack.poll());
System.out.println(stack.poll());
}
}
-
LinkQueue类
package DataStructure;
import java.util.NoSuchElementException;
public class LinkQueue<E> {
private final Node<E> head = new Node<>(null);
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
public void offer(E element) { //入队操作
Node<E> last = head;
while (last.next != null) //入队直接丢到最后一个结点的屁股后面就行了
last = last.next;
last.next = new Node<>(element);
}
public E poll() { //出队操作
if (head.next == null) //如果队列已经没有元素了，那么肯定是没办法取的
throw new NoSuchElementException("队列为空");
E e = head.next.element;
head.next = head.next.next; //直接从队首取出
return e;
}
}