队列

目录

 

一、队列结点

二、顺序队

三、链队

---

一、队列结点

package Queue;
class multipleNode{		//多项式结点
	multipleNode(){
		next=null;
	}
	multipleNode(int c,int e){
		coef=c;
		exp=e;
		next=null;
	}
	int coef;	//系数
	int exp;	//指数
	multipleNode next;	
}
public class Node{
	Node(char data){
		this.data=data;
		next=null;
		pre=null;
	}
	Node(){
		next=null;
		pre=null;
	}
	char data;
	Node next;
	Node pre;
}

二、顺序队

package Queue;
/*
 * 顺序队：使用循环队列实现
 * 思想：flag(true:end指向下一元素时（start和end指向同一元素时），置为true表示队满)
 * 		   (flase:start指向下一元素时（start和end指向同一元素时），置为false表示队空)
 *      start:指向下一个要出队的元素(已入队)
 *      end：指向下一个要入队的元素的位置(未入队)
 */
public class OrderQueue {
	Object[] objects;	
	int max;		//数组空间的大小
	int start=0;	//队首
	int end=0;		//队尾
	boolean flag=false;	//标志位：协助区分判断队空或队满（true为满，false为空）
	OrderQueue() {	//默认空间大小为4
		max=4;
		objects=new Object[max];
	}
	OrderQueue(int max) {	//自己设置空间大小
		this.max=max;
		objects=new Object[max];
	}
	public void entry(Object o) {	//入队
		if (end==start&&flag==true) {	//假如不带flag会导致一开始就出现start==end无法入队
			return;
		}
		if((end+1)%max==start) {
			flag=true;					//此处不返回return原因：当前start还有元素，只是
										//下一个元素与end重合时队才为空
		}
		objects[end]=o;
		end=(end+1)%max;
	}
	public Object exit() {			//出队
		if (start==end&&flag==false) {
			return null;
		}
		if((start+1)%max==end) {
			flag=false;
		}
		Object temp=objects[start];
		objects[start]=null;
		start=(start+1)%max;
		return temp;
	}
	public Object getStart() {	//取队首元素
		if (start==end&&flag==false) {
			return null;
		}
		return objects[start];	//start指向的是已入队最开始的元素，直接返回
	}
	public Object getEnd() {	//取队尾元素
		if (start==end&&flag==false) {
			return null;
		}
		return objects[(end+max-1)%max];	//end指向的是即将入队的元素位置，需要退一个位置
											//防止出现减1后为索引为-1情况需要先加max
	}
}

三、链队

package Queue;
/*
 * 链队
 * 补充知识点（Java值传递与引用传递）
 * 1.对象作为函数的参数传递过去的时候，是以原对象的引用的方式传递的，更改参数对象的值，会影响原来的对象。
 * 2.对象作为函数的返回值的时候，传递过来的也是一个引用传递，更改传递过来的对象的时候，会影响原来的对象 
 * 3.对象A给另一个对象B赋值的时候（无论B是否经过了new 开辟新空间），此时的B是对A对象的一个引用，更改B会影响A
 * 总结：传基本数据类型是值传递，传对象是引用传递（传的是对象的拷贝，若接收参数开辟新空间new对象后，则不再指向传入参数空间。）
 */
public class ChainQueue {
	Node head;	//队头直接用头结点指针判断
	Node end;
	ChainQueue() {
		head=new Node();
		head.next=null;
		end=head;
	}
	public void entry(char c) {
		if(head.next==null) {	//当队空时（正在进行时：队空后再次入队时进行判断）
			end=head;	
		}
		Node t=new Node();
		t.data=c;
		t.next=end.next;
		end.next=t;
		end=t;
	}
	public char exit() {
		if (head.next==null) {	//队空(当队空后再次出队时进行判断)
			return ' ';
		}
		Node t=head.next;
		char c=t.data;
		head.next=t.next;
		t=null;
		return c;
	}
	public char getStart() {	//取队首元素
		if (head.next==null) {
			return ' ';
		}
		return head.next.data;
	}
	public char getEnd() {		//取队尾元素
		if (head==end) {
			return ' ';
		}
		return end.data;
	}
}