2023-11-26
最基本队列：一次性使用的
class Queue01{
//最基本队列，一次性的，数组模拟，先进先出
//功能：入队，出队，判满，判空，显示队头，显示队列
private int[] queue;
private int front=-1;//指向第一个元素前一个位置
private int tail=-1;//指向最后一个元素
private int max;
public Queue01(int max){//构造方法创建队列
this.max=max;
queue=new int[this.max];
}
//判满
public boolean isFull(){
return tail==this.max-1;//其实真正的满，不是这个条件，应该与front有关
}
//判空
public boolean isEmpty(){
return tail==front;
}
//入队
public void pushQueue(int i){
if(isFull()){
System.out.println("队列已满。无法入队");
return;
}
tail++;
queue[tail]=i;
System.out.println("入队成功");
}
//出队
public int popQueue(){
if(isEmpty()){
System.out.println("队列为空，无法出队");
return -999999;
}
front++;
return queue[front];
}
//显示队头
public void showHead(){
if(isEmpty()){
System.out.println("队列为空");
return ;
}
System.out.println(queue[front+1]);
}
//显示队列
public void showQueue(){
if(isEmpty()){
System.out.println("队列为空");
return ;
}
for(int i=front+1;i<=tail;i++){
System.out.print(queue[i]+"\t");
}
System.out.println();
return;
}
}
标准队列：front与tail为-1开始的，难写一点
class Queue02{
//先进先出，数组模拟环形队列
//功能：入队，出队，判满，判空，显示队头，显示队列
//front=tail=-1 后面的代码难写点
private int max;
private int front=-1;
private int tail=-1;
private int[] queue;
public Queue02(int max){
this.max=max+1;
queue=new int[this.max];
}
//判空
public boolean isEmpty(){
return front==tail;
}
//判满
public boolean isFull(){
return (tail-front+1+max)%max==0; //-1 4(不是5，要空出来一个位置防止冲突)
}
//入队
public void pushQueue(int i){
if(isFull()){
System.out.println("队列满，无法入队");
return;
}
tail=(tail+1)%max;
queue[tail]=i;
System.out.println("入队成功");
}
//出队
public int popQueue(){
if(isEmpty()){
System.out.println("队列空，无法出队");
return -9999;
}
front=(front+1)%max;
return queue[front];
}
//显示队头
public void showHead(){
if(isEmpty()){
System.out.println("队列空");
return ;
}
System.out.println(queue[(front+1)%max]);
}
//显示队列
public void showQueue(){
if(isEmpty()){
System.out.println("队列空");
return ;
}
//这里的判断条件还可以根据长度写，，，，
for (int i = (front+1)%max; i != (tail+1)%max; ) {//注意判断条件
System.out.print(queue[i]+"\t");
i=(i+1)%max;
}
System.out.println();
}
}
标准队列：front与tail初值为0，好写一点
class Queue03{
//先进先出，数组模拟环形队列
//功能：入队，出队，判满，判空，显示队头，显示队列
//front=rear=0版
private int max;
private int front=0;
private int tail=0;
private int[] queue;
public Queue03(int max){
this.max=max+1;
queue=new int[this.max];
}
//判空
public boolean isEmpty(){
return front==tail;
}
//判满
public boolean isFull(){
return (tail-front+1+max)%max==0; //-1 4(不是5，要空出来一个位置防止冲突)
}
//入队
public void pushQueue(int i){
if(isFull()){
System.out.println("队列满，无法入队");
return;
}
queue[tail]=i;
tail=(tail+1)%max;
System.out.println("入队成功");
}
//出队
public int popQueue(){
if(isEmpty()){
System.out.println("队列空，无法出队");
return -9999;
}
int i= queue[front];
front=(front+1)%max;
return i;
}
//显示队头
public void showHead(){
if(isEmpty()){
System.out.println("队列空");
return ;
}
System.out.println(queue[front%max]);
}
//显示队列
public void showQueue(){
if(isEmpty()){
System.out.println("队列空");
return ;
}
//这里判断条件还可以根据长度写，，而不是临界条件
for (int i = front; i != tail; ) {//注意判断条件
System.out.print(queue[i]+"\t");
i=(i+1)%max;
}
System.out.println();
}
}
双端队列：
class Queue04{
//两端插入与删除元素
private int front=0;//指向第一个元素，初始赋值是为了判空，判满与操作的方便，否则应该是-1
private int tail=0;
private int[] queue;
private int max;
public Queue04(int max){
this.max=max+1;
queue=new int[max+1];
}
//判空
public boolean isEmpty(){
return front==tail;
}
//判满
public boolean isFull(){
return (tail+1-front+max)%max==0;
}
//队尾正常入队
public void pushQueue(int i){
if(isFull()){
System.out.println("队列已满，队尾无法正常入队");
return;
}
queue[tail]=i;
tail=(tail+1)%max;
System.out.println("正常入队成功");
}
//队头入队
public void pushQueueFromHead(int i){
if(isFull()){
System.out.println("队列已满，无法从队头入队");
return;
}
front=(front+max-1)%max;
queue[front]=i;
System.out.println("队头入队成功");
}
//队头正常出队
public int popQueue(){
if(isEmpty()){
System.out.println("队列为空，队头无法正常出队");
return -99999;
}
int k=queue[front];
front=(front+1)%max;
return k;
}
//队尾出队
public int popQueueFormTail(){
if(isEmpty()){
System.out.println("队列为空，队尾无法出队");
return -99999;
}
tail=(tail-1+max)%max;
return queue[tail];
}
//显示队头
public void showHead(){
if(isEmpty()){
System.out.println("队列为空，无法显示队头");
return;
}
System.out.println(queue[front]);
}
//显示队尾
public void showTail(){
if(isEmpty()){
System.out.println("队列为空，无法显示队尾");
return;
}
System.out.println(queue[ (tail-1+max)%max ]);
}
//显示队列 显示队列没必要从后往前 接收front，tail数据--的循环罢了
public void showQueue(){
if(isEmpty()){
System.out.println("队列为空，无法显示队列");
return;
}
for (int i = front; i !=tail; ) {
System.out.print(queue[i]+"\t");
i=(i+1)%max;
}
System.out.println();
}
}
单调队列标签：队列,双端,System,int,tail,max,front,单调,out From： https://www.cnblogs.com/youye9527/p/17858106.html
具有单调性，而且，队首和队尾都可以进行出队操作，只有队尾可以进行入队操作
改一下双端队列就行了