概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
当head==tail时
情况1：队列为空
情况2：队列为满
用链表的方式形成队列
代码语言：javascript复制public class MyQueueByLinkedList {
//Node 这个类叫做内部类
static class Node{
public int val;
Node next = null;
public Node(int val){
this.val = val;
}
}
//创建一个链表就得有头节点 此处的head不是傀儡节点
private Node head = null;
private Node tail = null;
//入队列
//此处尾部入队列，头部出队列的方式实现
public void offer(int val){
Node newNode = new Node(val);
if (head == null){
head = newNode;
tail = newNode;
return;
}
//如果当前不是空链表
tail.next = newNode;
tail = tail.next;
}
//出队列
public Integer poll(){
if (head == null){
return null;
}
int ret = head.val;
head = head.next;
if (head == null){
tail = null;
}
return ret;
}
//取队首元素
public Integer peek(){
if (head == null){
return null;
}
return head.val;
}
}用数组的方式形成队列
代码语言：javascript复制public class MyQueueByArray {
private int[] array = new int[100];
private int head = 0;
private int tail = 0;
private int size = 0;
public void offer(int val){
if (size == array.length){
return;
}
array[tail] = val;
tail ;
//如果超出了有效范围，就从头开始
if (tail > array.length){
tail = 0;
}
size ;
}
public Integer poll(){
if (size == 0){
return null;
}
Integer ret = array[head];
head ;
if (head >= array.length){
head = 0;
}
size--;
return ret;
}
public Integer peek(){
if (size == 0){
return null;
}
return array[head];
}
}具体实现
错误处理 | 抛出异常 | 返回特殊值 |
|---|---|---|
入队列 | add(e) | offer(e) |
出队列 | remove() | poll() |
入队列 | element() | peek() |
