【Java】 大话数据结构(7) 循环队列和链队列

时间:2022-03-31 10:24:15

 

本文根据《大话数据结构》一书,实现了Java版的循环队列、链队列

队列:只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

【Java】 大话数据结构(7) 循环队列和链队列

 

1.循环队列

  队列的顺序储存结构:用数组存储队列,引入front指针指向队头元素,rear指针指向队尾元素的下一个位置,当front=rear时,为空队列,结构如下图所示。

 【Java】 大话数据结构(7) 循环队列和链队列

 

  当执行入队操作时,若数组尾部已满,而数组前部因有元素出队而有空位时,我们把新插入的元素从头开始入队,这样就类似于头尾相接的结构。

  队列的这种头尾相接的顺序存储结构称为循环队列,如下图所示。

【Java】 大话数据结构(7) 循环队列和链队列

  上面队列的定义中提到,当front=rear时,为空队列,而在循环队列中,队列满时,front也等于rear,将无法判断队满和空的情况。

    一种办法是设置一个标志变量flag,当front=rear时,通过判断flag是0还是1来确定队列满空情况;

    另一种方法是,在数组中只剩一个空闲单位时,定义为队列满,如下图所示。(本文程序采用这种办法)

【Java】 大话数据结构(7) 循环队列和链队列

   因为rear可能比front大,也可能比front小,所以队列满的条件应该为:(rear+1)%maxSize==front;同理,队列长度的计算公式为:(rear-front+maxSize)%maxSize

  实现程序:

/**
 * <循环队列>
 * 
 * 注意点:表长的表示、队列满的判断、front和rear的改变
 * 
 * @author Lai
 *
 */
public class SqQueue<E> {
	private E[] data;
	private int front;
	private int rear;
	private int maxSize;
	private static final int DEFAULT_SIZE= 10;
	
	/*
	 * 初始化
	 */
	public SqQueue(){
		this(DEFAULT_SIZE);
	}
	public SqQueue(int maxSize){
		data=(E[]) new Object[maxSize];
		this.maxSize=maxSize;
		front=0;
		rear=0;
	}
	
	/*
	 * 求循环队列长度
	 */
	public int getLength() {
		return (rear-front+maxSize)%maxSize;
	}
	
	/*
	 * 入队操作
	 */
	public void enQueue(E e) {
		if((rear+1)%maxSize==front)
			throw new RuntimeException("队列已满,无法入队!");
		data[rear]=e;
		rear=(rear+1)%maxSize;
		//不是rear=rear+1,当rear在数组尾部时,后移一位会转到数组头部
	}
	
	/*
	 * 出队操作
	 */
	public E deQueue() {
		if(rear==front) 
			throw new RuntimeException("队列为空!");
		E e=data[front];
		front=(front+1)%maxSize;
		//不是front++,理由同rear
		return e;
	}
	
	/*
	 * 打印操作
	 */
	public void printQueue() {
		int k=front;
		for(int i=0;i<getLength();i++) {
			System.out.print(data[k]+" ");
			k=(k+1)%maxSize;
		}
		System.out.println();
	}
	
	/*
	 * 测试代码
	 */
	public static void main(String[] args) {
		SqQueue<String> aQueue=new SqQueue<>(5);	
		aQueue.enQueue("a");
		aQueue.enQueue("b");
		aQueue.enQueue("c");
		aQueue.enQueue("d");
		aQueue.printQueue();
		System.out.println("-----");
		aQueue.getLength();
		aQueue.deQueue();
		aQueue.deQueue();
		aQueue.enQueue("e");
		aQueue.printQueue();
	}
	
}

  

【Java】 大话数据结构(7) 循环队列和链队列【Java】 大话数据结构(7) 循环队列和链队列
a b c d 
-----
c d e 
SqQueue

 

2.队列的链式存储结构

  用单链表存储队列,称为链队列

  定义front指针指向头结点,rear指针指向终端结点,空队列时,front和rear都指向头结点。

  【Java】 大话数据结构(7) 循环队列和链队列  【Java】 大话数据结构(7) 循环队列和链队列

  实现程序:

/**
 * 链队列
 * 
 * 注意点:出队操作时,若队头是队尾(即队中仅有一个结点),则删除后要将rear指向头结点。
 * 
 * @author Yongh
 *
 * @param <E>
 */
public class LinkQueue<E> {
	private QNode front,rear;
	private int count;
	
	class QNode{
		E data;
		QNode next;
		public QNode(E data,QNode next) {
			this.data=data;
			this.next=next;
		}
	}
	
	public LinkQueue() {
		front=new QNode(null, null);
		rear=front;
		count=0;
	}
	
	/*
	 * 入队操作
	 */
	public void enQueue(E e) { 
		QNode node=new QNode(e, null);
		rear.next=node;
		rear=node;
		count++;
	}
	
	/*
	 * 出队操作
	 */
	public E deQueue() {
		if(rear==front)
			throw new RuntimeException("队列为空!");
		QNode node=front.next;
		E e=node.data;
		front.next=node.next;
		//若队头是队尾,则删除后要将rear指向头结点。
		if(rear==node)
			rear=front;
		node=null;
		count--;
		//通过count来判断,可能更容易理解
		//if(count==0)
		//	rear=front;
		return e;
	}
	
	/*
	 * 获取队列长度
	 */
	public int getLength() {
		return count;
	}
	
	/*
	 * 打印输出队列
	 */
	public void printQueue() {
		if(count==0) {
			System.out.println("空队列");	
		}else {
			QNode node=front;
			for(int i=0;i<count;i++) {
				node=node.next;
				System.out.print(node.data+" ");
			}
			System.out.println();
		}
	}
	
	/*
	 * 测试代码
	 */
	public static void main(String[] args) {
		LinkQueue<String> lQueue =new LinkQueue<>();
		lQueue.printQueue();
		lQueue.enQueue("A");
		lQueue.enQueue("B");
		lQueue.enQueue("c");
		lQueue.enQueue("D");
		lQueue.printQueue();
lQueue.deQueue(); lQueue.deQueue(); lQueue.enQueue("E"); lQueue.printQueue(); } }

  

【Java】 大话数据结构(7) 循环队列和链队列【Java】 大话数据结构(7) 循环队列和链队列
空队列
A B c D 
c D E 
LinkQueue

 

3.循环队列和链队列的选择

  基本操作时间都为O(1)。但链队列每次申请和释放结点会存在一点时间开销,且其需要存储一个指针域;而循环队列必须固定空间长度,存在空间浪费问题,且没链队列灵活。

  综上,在可以确定队列长度最大值的情况下,建议用循环队列;当无法预估队列的长度时,使用链队列