java.队列的实现

第一种方法：单链表实现队列

源码：

class Node { public int val; public Node next; public Node(int val) { this.val = val; } } public class Myqueue { //普通的单链表实现队列 //head 对应到队首元素 private Node head = null; private Node tail = null; //tail 对应到队尾元素 //这个 size 用来记录队列的长度，这样就不用每次遍历找队尾元素了 private int size = 0; //队列的基本操作 //1. 入队列 public void offer(int x) { Node newNode = new Node(x); //插入到链表的尾部 //1. 如果是空链表 if (head == null) { head = newNode; tail = newNode; size++; return; } //2. 非空链表 tail.next = newNode; tail = tail.next; size++; return; } //2. 出队列,被出队列的元素的值通过返回值来表示 public Integer poll() { //1. 空队列，无法出队列了 if (head == null) { return null; } //2. 非空队列 Integer ret = head.val; head = head.next; if (head == null) { //如果当前队列就一个元素，删除这个元素的同时 //也要修改 tail 的指向 tail = null; } size--; return ret; } //3.取队首元素 public Integer peek() { if (head == null) { return null; } return head.val; } //4. 判定队列为空 public boolean isEmpty() { return head == null; } //5. 取队列中元素的个数 public int size() { return size; } public static void main(String[] args) { Myqueue myqueue = new Myqueue(); myqueue.offer(1); myqueue.offer(2); myqueue.offer(3); myqueue.offer(4); myqueue.offer(5); while (!myqueue.isEmpty()) { int curFront = myqueue.peek(); System.out.println(curFront); myqueue.poll(); } } }

第二种方法：数组实现队列

（1）关键：头或者尾部已经达到数组的最后一个元素，接下来再进行入队列或者出队列，就让这样的标记来到数组的开头

（2）队列为空： head 和 tail 相等，队列为空 队列满了： head 和 tail 相等 ，那就需要将 tail 重新设置为 0

源码：

public class MyQueue2 { private int[] data = new int[100]; // [head,tail） // 初始情况下， head 和 tail 都为 0 ，但是队列中无元素 private int head = 0;// 队首元素的下标 private int tail = 0;// 队尾的元素的下标 private int size = 0; //1. 入队列,如果插入成功，返回 true 否则返回 false // 如果队列满了，再插入就会失败 public boolean offer(int x) { if (size == data.length) { return false; } //把新元素放再 tail 的位置上 data[tail] = x; tail++; if (tail == data.length) { tail = 0; } size++; return true; } //2. 出队列 public Integer poll() { if (size == 0) { return null; } Integer ret = data[head]; head++; if (head == data.length) { head = 0; } size--; return ret; } //3. 取队首元素 public Integer peek() { if (size == 0) { return null; } return data[head]; } //4. 判定为空 public boolean isEmpty() { return size == 0; } //5. 取长度 public int size() { return size; } }