队列：顺序表

布满荆棘的人生 2021-11-09 06:30 297阅读 0赞

#### 队列是什么？ ####

队列是有序列表，有顺序表和链表，遵循先进先出的规则

#### 顺序表 ####

顺序表即为数组队列；

1.  创建一个ArryQueue class
2.  增加maxSize属性，表示队列能容纳的最大数据
3.  增加front队头，rear队尾 rear所指是没有数据的
4.  增加length，代表当前队列中国元素个数
5.  增加array\[\]数组存放队列数据
6.  初始化队列
7.  增加入队、出队、显示队头元素、判断队列是否已满、判断队列是否为空、打印队列等方法

##### 图示 #####

![顺序表][20190803153556967.jpg]  
由图可以发现数组队列的缺陷：  
等rear = maxSize - 1时，就无法存储数据，front之前的空间会造成浪费

由于顺序表比较简单  
就不写思路了

##### code #####

package com.lemon.arrayqueue;
    
    import java.lang.reflect.Array;
    import java.util.Arrays;
    
    public class ArrayQueue {
        
    	private int maxSize;		//队列存储最大值
    	private int front;		//队列的头
    	private int rear;		//队列的尾
    	private int length;		//队列的长度
    	private int[] array;			//存放队列的数组
    
    	//初始化队列
    	public ArrayQueue(int maxSize) {
        
    		front = -1;
    		rear = -1;
    		length = 0;
    		this.maxSize = maxSize;
    		array = new int[this.maxSize];
    	}
    	
    	//判断队列是否为空
    	public boolean isEmpty() {
        
    		return front == rear;
    	}
    	
    	//判断队列是否已满
    	public boolean isFull() {
        
    		return rear == maxSize - 1;
    	}
    	
    	//入队列
    	public void inQueue(int data) {
        
    		if(isFull()) {
        
    			throw new RuntimeException("队列已满");
    		}
    		array[++rear] = data;
    		length++;
    	}
    	
    	//出队列
    	public void outQueue() {
        
    		if(isEmpty()) {
        
    			//throw完了会终止方法运行
    			throw new RuntimeException("队列为空");
    		}
    		front++;
    		length--;
    	}
    	
    	//队头
    	public int frontQueue() {
        
    		if(isEmpty()) {
        
    			throw new RuntimeException("队列为空");
    		}
    		return array[front + 1];
    	}
    	
    	//打印队列
    	public void printArryQueue() {
        
    		if(isEmpty()) {
        
    			throw new RuntimeException("队列为空");
    		}
    		for(int i = front + 1; i <= rear; i++) {
        
    			System.out.printf("%d\t", array[i]);
    		}
    	}
    	
    	//队列长度	
    	public int lengthArrayQueue() {
        
    		return length;
    	}
    }

package com.lemon.arrayqueue;
    
    import java.util.Scanner;
    
    public class Test01 {
        
    	public static void main(String[] args) {
        
    		ArrayQueue arrayQueue = new ArrayQueue(4);
    		Scanner sca = new Scanner(System.in);
    		
    		System.out.println("1. 入队列");
    		System.out.println("2. 出队列");
    		System.out.println("3. 显示队头");
    		System.out.println("4. 打印队列");
    		System.out.println("5. 队列长度");
    		System.out.println("0. 退出队列");
    		
    		int data;
    		int n;
    		boolean flag = true;
    		while(flag) {
        
    			n = sca.nextInt();
    			switch(n) {
        
    			case 1:
    				try {
        
    					data = sca.nextInt();
    					arrayQueue.inQueue(data);
    				} catch (Exception e) {
        
    					System.out.println(e.getMessage());
    				}
    				flag = true;
    				break;
    			case 2:
    				try {
        
    					arrayQueue.outQueue();
    				} catch (Exception e) {
        
    					System.err.println(e.getMessage());
    				}
    				flag = true;
    				break;
    			case 3:
    				try {
        
    					System.out.println(arrayQueue.frontQueue());
    				} catch (Exception e) {
        
    					System.out.println(e.getMessage());
    				}
    				flag = true;
    				break;
    			case 4:
    				try {
        
    					arrayQueue.printArryQueue();
    				} catch (Exception e) {
        
    					System.err.println(e.getMessage());
    				}	
    				flag = true;
    				break;
    			case 5:
    				System.out.println(arrayQueue.lengthArrayQueue());
    				break;
    			case 0:
    				flag = false;
    				break;
    			}
    		}
    	}
    }

#### 数组模拟环形队列 ####

1.  创建CircularQueue.class
2.  属性和以上一样
3.  初始化环形队列注意
    
    1.  front = 0;
    2.  rear = 0;
4.  判断队列是否已满的条件(关键小算法)：`(rear + 1) % maxSize == front`
5.  其它一样

这个公式的关键是% 它能使数组循环利用

###### code ######

package com.lemon.circularqueue;
    
    public class CircularQueue {
        
    	private int front;
    	private int rear;
    	private int length;
    	private int maxSize;
    	private int[] array;
    	
    	//初始化环形队列
    	public CircularQueue(int maxSize) {
        
    		front = 0;
    		rear = 0;
    		length = 0;
    		this.maxSize = maxSize;
    		array = new int[maxSize];
    	}
    	
    	//判断环形队列是否已满
    	public boolean isFull() {
        
    		return (rear + 1) % maxSize == front;
    	}
    	
    	//判断环形队列是否为空
    	public boolean isEmpty() {
        
    		return front == rear;
    	}
    	
    	//入队列
    	public void inQueue(int data) {
        
    		if(isFull()) {
        
    			throw new RuntimeException("队列已满");
    		}
    		array[rear] = data;
    		rear = (rear + 1) % maxSize;
    		length++;
    	}
    	
    	//出队列
    	public void outQueue() {
        
    		if(isEmpty()) {
        
    			throw new RuntimeException("队列为空");
    		}
    		front = (front + 1) % maxSize;
    		length--;
    	}
    	
    	//显示队头
    	public int frontQueue() {
        
    		if(isEmpty()) {
        
    			throw new RuntimeException("队列为空");
    		}
    		return array[front];
    	}
    	
    	//打印队列
    	public void printQueue() {
        
    		int n = length;
    		int m = front;
    		if(isEmpty()) {
        
    			throw new RuntimeException("队列为空");
    		}
    		while(true) {
        
    			System.out.println(array[m]);
    			m = (m + 1) % maxSize;
    			n--;
    			if(n == 0) {
        
    				break;
    				
    			}
    		}
    	}
    	
    	//长度
    	public int lengthCircularQueue() {
        
    		return length;
    	}
    }

package com.lemon.circularqueue;
    
    import java.util.Scanner;
    
    import com.lemon.arrayqueue.ArrayQueue;
    
    public class Test01 {
        
    	public static void main(String[] args) {
        
    		CircularQueue circularQueue = new CircularQueue(3);
    		Scanner sca = new Scanner(System.in);
    		
    		System.out.println("1. 入队列");
    		System.out.println("2. 出队列");
    		System.out.println("3. 显示队头");
    		System.out.println("4. 打印队列");
    		System.out.println("5. 队列长度");
    		System.out.println("0. 退出队列");
    		
    		int data;
    		int n;
    		boolean flag = true;
    		while(flag) {
        
    			n = sca.nextInt();
    			switch(n) {
        
    			case 1:
    				try {
        
    					data = sca.nextInt();
    					circularQueue.inQueue(data);
    				} catch (Exception e) {
        
    					System.out.println(e.getMessage());
    				}
    				flag = true;
    				break;
    			case 2:
    				try {
        
    					circularQueue.outQueue();
    				} catch (Exception e) {
        
    					System.err.println(e.getMessage());
    				}
    				flag = true;
    				break;
    			case 3:
    				try {
        
    					System.out.println(circularQueue.frontQueue());
    				} catch (Exception e) {
        
    					System.out.println(e.getMessage());
    				}
    				flag = true;
    				break;
    			case 4:
    				try {
        
    					circularQueue.printQueue();
    				} catch (Exception e) {
        
    					System.err.println(e.getMessage());
    				}	
    				flag = true;
    				break;
    			case 5:
    				System.out.println(circularQueue.lengthCircularQueue());
    				break;
    			case 0:
    				flag = false;
    				break;
    			}
    		}
    	}
    }

[20190803153556967.jpg]: /images/20211109/69d6ee3dcc9d488bb0387cb3b2d9b4fe.png