队列的创建Java实现

不念不忘少年蓝@ 2022-03-25 05:17 213阅读 0赞

**关键词：**结点类、队列类、队头队尾指针

**1.结点类的设计**

class QueueNode {
    	int data;
    	QueueNode next;
    	
    	QueueNode(){
    		data = 0;
    		next = null;
    	}
    	QueueNode(int d, QueueNode n){
    		data = 0;
    		next = n;
    	}
    }

**2.链式队列类的设计（基于链表实现） **

class LinQueue {
    	private QueueNode front;//队头指针
    	private QueueNode rear;//队尾指针
    	
    	public LinQueue(){
    		front = rear = null;
    	}
    	public boolean isEmpty(){
    		return front == null;
    	}
    	public int getHead(){
    		if(isEmpty()){
    			System.out.println("当前队列为空");
    			return -1;
    		}
    		return front.data;
    	}
    	public void enQueue(QueueNode node){
    		if(front == null){//如果队列为空
    			front = rear = node；
    		}
    		else{
    			rear = rear.next = node;
    		}
    	}
    	public int deQueue(){
    		if(isEmpty){
    			System.out.println("当前队列为空");
    			return -1;
    		}
    		int data = front.data;
    		front = front.next;
    		return data;
    	}
    }

**3.顺序队列类的设计（基于数组实现）**

class SeqQueue {
    	private QueueNode[] array;
    	private int front;
    	private int rear;
    	
    	public SeqQueue(){
    		array = new QueueNode[10];//默认队列大小为10
    		front = rear = 0;
    	}
    	public SeqQueue(int size){
    		array = new QueueNode[size];
    		front = rear = 0;
    	}
    	public boolean isEmpty(){
    		return front == rear;
    	}
    	public boolean isFull(){
    		return rear == array.length;
    	}
    	public int getHead(){
    		if(isEmpty()){
    			System.out.println("当前队列为空");
    			return -1;//负数表示空
    		}
    		return array[front].data;
    	}
    	public void enQueue(QueueNode node){
    		if(isEmpty()){//如果队列为空
    			array[front]=array[rear]=node；
    		}
    		else{
    			if(isFull())
    				System.out.println("队满，无法入队");
    			else
    				array[++rear]=node;
    		}
    	}
    	public int deQueue(){
    		if(isEmpty())
    			System.out.println("当前队列是空的");
    		else{
    			int data = array[front];//队头front=0
    			for(int i=0; i<rear; i++){
    				array[i] = array[i+1];
    			}
    			rear--;
    			return data;
    		}
    	}
    }

基于数组的顺序队列会产生假溢出的问题， 解决解决假溢出问题通常有两种方法：

（1）每次出队时，剩余元素都往前移（时间复杂度大，上面代码就是此种方法）

（2）使用循环队列（请看下面的代码）

** 4.循环队列类的设计（基于数组实现）**

循环队列要点：

1.队列空条件：front == rear

2.队列满条件：(rear+1)%MaxSize == front

3.元素进队：data\[rear\] = e;    rear = (rear+1)%MaxSize（是不是很神奇）

4.元素出队：e = data\[front\];    front = (front+1)%MaxSize

class CirQueue {
    	private static final int maxSize = 10;
    	private int front;
    	private int rear;
    	private QueueNode[] array;
    	
    	public CirQueue(){
    		array = new QueueNode[maxSize];
    		rear = front = 0;
    	}
    	public void clear(){
    		front = rear = 0;
    	}
    	public boolean isEmpty(){
    		return front==rear;
    	}
    	public boolean isFull(){
    		return (rear+1) % array.length == front;
    	}
    	public int getSize(){
    		return (rear - front + array.length) % array.length;
    	}
    	public Type getFront( ){
    		if(isEmpty())
    			throw new NoSuchElementException();
    		return array[(front+1)%element.length];    
    	}
    	public void enQueue(Type item){
    		if(isFull())
    			throw new OutOfQueueException();
    		rear = (rear+1) % array.length;
    		array[rear] = item;    
    	}
    	public Type deQueue( ){
    		if(isEmpty())
    			throw new NoSuchElementException();
    		front = (front+1) % array.length;
    		return array[front];    
    	}
    }