环形队列
超强解析环形队列(数组实现)
public class CircleQueueByArray {
private int front;//指向队列首元素的前一个位置
private int rear;//指向队列的最后一个元素
private int[] arr;
private int size;
public CircleQueueByArray(int size){}//构造器初始化数组
public boolean isFull(){}//判断队列是否满
public boolean isEmpty(){}//判断队列是否空
public void add(int data){}//入队
public int delete(){}//出队
public void ergodic(){}遍历环形队列
接下来一一解析各方法实现
构造方法
这里数组能放进的数据数量为size，但数组真实容量为size+1。所空出的一格用来判断数组是否为空。
public CircleQueueByArray(int size){
this.size=size;
arr=new int[this.size+1];
front=0;
rear=0;
}
判断队列是否满
这里以size=3为例，当其为3时，数组实际大小为4，由上图可易知
(rear+1)%(size+1)=0;而front为0，所以可以判断当(rear+1)%(size+1)==front时，队列为满。以后增加或删除元素是此条件仍成立。
public boolean isFull(){
return (rear+1)%(size+1)==front;
}
判断队列是否为空
有上面的图片可易知，队列为初值时或将队列中的元素删减完时，rear==front。
public boolean isEmpty(){
return rear==front;
}
入队
多次入队时环形队列需要rear从起始位置绕到终点位置在绕到起始位置，需要重复利用。故：rear=(rear+1)%(size+1);
//入队
public void add(int data){
if(isFull()){
System.out.println("队列已满，无法入队");
return;
}else{
rear=(rear+1)%(size+1);
arr[rear]=data;
}
}
出队
同rear一样，多次出队时环形队列需要front从起始位置绕到终点位置在绕到起始位置，需要重复利用。故：front=(front+1)%(size+1);
public int delete(){
if(isEmpty()){
throw new RuntimeException("队列为空，无法出列");
}else{
front=(front+1)%(size+1);
return arr[front-1];
}
}
遍历环形队列
front指向队列首元素的前一个位置，所以cur=(front+1)%(size+1)是让cur指向首元素地址。在遍历过程中有可能出现front=3，rear=1类似于这样的情况。所以遍历是需要将cur%=size+1 以保证无论何时cur都能完整的遍历数组。
public void ergodic(){
if(isEmpty()){
System.out.println("队列为空，无法遍历");
return;
}
int cur=(front+1)%(size+1);
while(cur!=rear){
System.out.print(arr[cur]+" ");
cur++;
cur%=size+1;
}
System.out.print(arr[rear]);
System.out.println();
}
单项队列
数组实现单项队列
public class QueueByArray {
private int front=-1;
private int rear=-1;
private int[] arr;
public int size;
//构造函数中初始化数组容量
public QueueByArray(int s){
this.size=s;
arr=new int[this.size];
}
//入队
public void add(int data){
if(rear==this.size-1){
System.out.println("队列已满，无法添加数据");
return;
}else{
arr[++rear]=data;
}
}
//出队
public int delete(){
if(front>=rear){
throw new RuntimeException("队列为空，无法添加数据");
}else{
int tmp=arr[front+1];
for(int i=0;i<rear;i++)
arr[i]=arr[i+1];
rear--;
return tmp;
//return arr[++front];
}
}
//遍历队列
public void ergodic(){
if(front>=rear){
System.out.println("队列为空，无法添加数据");
return;
}
int cur=front+1;
while(true){
System.out.println(arr[cur]);
if(cur==rear)
break;
cur++;
}
}
}
链表实现单项队列
先创建一个节点类
public class Node {
int data;
Node next;
public Node(){}
public Node(int data){
this.data=data;
next=null;
}
}
再创建一个用链表实现的队列类
public class QueueByLink {
private Node front;
private Node rear;
public QueueByLink(){
front=null;
rear=null;
}
//入队
public void add(int data){
Node newNode=new Node(data);
if(rear==null){
front=newNode;
rear=newNode;
}else{
rear.next=newNode;
rear=newNode;
}
}
//出列
public Node delete(){
if(rear==null) {
throw new RuntimeException("队列为空，无法删除数据");
}else if(rear!=front){
Node cur=front.next;
front=front.next;
return cur;
}else{
front=null;
rear=null;
return null;
}
}
//便利队列
public void ergodic(){
if(rear==null){
System.out.println("队列为空，无法遍历");
return;
}
Node cur=front;
while(cur!=null){
System.out.println(cur.data);
cur=cur.next;
}
}
}
双向对列
链表实现双向队列
先创建一个节点类
public class Node {
int data;
Node next;
public Node(){}
public Node(int data){
this.data=data;
next=null;
}
}
再创建一个用链表实现的队列类
public class Deque {
private Node front;
private Node rear;
//判断队列是否为空
public boolean isEmpty(){
return rear==null;
}
//头入队
public void fadd(int data){
Node newNode=new Node(data);
if(isEmpty()){
front=newNode;
rear=newNode;
}else{
newNode.next=front;
front=newNode;
}
}
//尾入队
public void radd(int data){
Node newNode=new Node(data);
if(isEmpty()){
front=newNode;
rear=newNode;
}else{
rear.next=newNode;
rear=newNode;
}
}
//头出队
public Node fdelete(){
if(isEmpty()){
throw new RuntimeException("队列为空，无法删除");
}else{
Node first=front;
front=front.next;
return first;
}
}
//尾出队
public Node rdelete(){
if(isEmpty()){
throw new RuntimeException("队列为空，无法删除");
}else{
Node bef=rear;
Node cur=front;
while(cur.next!=rear)
cur=cur.next;
cur.next=rear.next;
rear=cur;
return bef;
}
}
//遍历队列
public void ergodic(){
Node cur=front;
while(cur!=null){
System.out.print(cur.data+" ");
cur=cur.next;
}
System.out.println();
}
}