队列：只允许在一端进行插入的操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的原则！！
进行插入操作的一端称为对胃！
进行删除操作的一端称为对头！
经过上面的一些讲解，那么我们可以来用单链表来实现一个队列了吧！！
入 |
头插法O(1) |
出 |
删除链表最后一个元素O(N) |
入 |
尾插法O(N) |
出 |
删除头部元素O(1) |
因此，有着一些局限：只能从尾巴插入，头部删除！（找到尾巴节点，头部节点）
有着上述分析，开始用单链表实现链式队列吧！！
单链表实现队列
public class MyQueue { //用单链表实现链式队列 static class Node{ //单链表 public int val; public Node next; //构造方法 public Node(int val){ this.val=val; } } public Node head;//头 public Node last;//尾 public int usedSize; //入队 public void offer(int val){ Node node=new Node(val); if (head==null){ head=node; last=node; }else { last.next=node; last=node; } usedSize++; } //出队 public int poll(){ if (empty()){//判断是否为空 throw new EmptyException("队列为空"); } int ret=head.val;//想要出队的值 head=head.next;//头节点，走一步，删除原来的节点 if (head==null){ //只有一个节点 last=null; } usedSize--; return ret; } //判断是否为空 public boolean empty(){ return usedSize==0; } //偷看头节点 public int peek(){ if (empty()){ throw new EmptyException("对列为空"); } return head.val; } public int getUsedSize(){ return usedSize; } }
在这个代码中，用链表来实现的队列，基本上都是链表的基础知识，没有多大的新意！
首先定义链表的头，尾，节点的个数，从入队列开始实现，因为队列是先进先出的模式，那么，我们在链表中，就可以进行尾插，每次插入的时候，都将数据插入到链表的后面，并且每次插入都得记录一下此时的链表长度（usedSize++)！在出队列的过程中，由于队列的先进先出模式，所以在单向链表实现的过程中，我们也要遵循这个先进先出的模式，那么，这就要求我们，每次进行出链表的时候，都得出掉链表的头部（头删），同时usedSize--;头节点往后走一步！在进行偷看头节点的操作的时候，这就显得很简单了！但是，这个需要注意一个大前提：链表不能为空！如果链表不为空，之间返回链表的头节点即可！
抛异常的代码为：
public class EmptyException extends RuntimeException { public EmptyException() { } public EmptyException(String message) { super(message); } }
抛异常的操作，有一个不带参数的构造方法，也有一个带有一个参数的构造方法！
Main方法的代码为：
public class Test { public static void main(String[] args) { MyQueue myQueue=new MyQueue(); myQueue.offer(12); myQueue.offer(23); myQueue.offer(34); myQueue.offer(45); myQueue.offer(45); System.out.println(myQueue.peek()); System.out.println(myQueue.poll()); System.out.println(myQueue.poll()); System.out.println(myQueue.poll()); } }
代码的运行结果为：
双向链表实现队列
用双向链表来实现一个栈的前提，是我们需要知道栈的底层是一个双向链表！！
public class Queue { //用双向链表实现一个队列 public static class ListNoode{ //双向链表的各个节点 ListNoode next;//下一个 ListNoode prev;//上一个 int val; } ListNoode first;//对头 ListNoode last;//队尾 int size=0; //入队列，向双向链表位置插入新的节点 public void offer(int e){ ListNoode newNode=new ListNoode(); if (first==null){ first=newNode; last=newNode; }else { last.next=newNode; newNode.prev=last; last=newNode; } size++; } //出队列，将双向链表的第一个节点删除掉 public int poll(){ //1.队列为空 //2，队列只有一个元素——》链表中只有一个节点——》直接删除 //3，队列中有多个元素——》链表中有多个节点——》将第一个节点删除 int value=0; if (first==null){ return null; }else if (first==last){ last=null; first=null; }else { value=first.val; first=first.next; first.prev.next=null; first.prev=null; } --size; return value; } //获取对头元素——》获取链表中第一个节点的值域 public int peek(){ if (first==null){ return null; } return first.val; } public int size(){ return size; } public boolean isEmpty(){ return first==null; } }
在用双向链表实现队列的时候，其实跟单向链表实现队列差不多！！主要还是双向链表比单向链表多了一个域：用来记录前一个节点的地址！！这个就导致我们在进行插入/删除数据的时候，就得多思考一下了！！但是，由于：栈的底层是一个双向链表，那么，我们就得学好双向链表了！！
