java--数据结构 顺序队列和链式队列的建立及使用

顺序队列（循环队列）：队列的特点是‘先进先出’。首先构建一个Object类型的数组，其类型由你的模板（）决定，再设置两个“指针”（其本质就是两个变量，利用其加减完成对Object数组上取值删值的操作）------------base和top分别是"头指针"和“尾指针”。peek函数就是取出队列顶端元素，put是入队列操作，take是出队列操作，empty是判断队列是否为空。

为何要用循环队列？

因为队列是先进先出，当初队列后，从Object[0]到Object[base]都为空，造成了空间的浪费，我们只需要当top“指针”到达Object数组顶端的时候，在进行下一步入队列操作的时候，只需要将top=0即让top“指针”指向Object的第一个元素即可。

如何让top指向Object的第一个元素？

你需要top=(top+1)%_MAXSIZE这样操作，当到队列最尾端的时候，让尾端+1再除这个Object数组的长度取余，就行了。

还有一个很重要，top和base的初始值要是-1，每次top操作前要先加1..................

public class Text2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		QueueS s2=new QueueS();
		s2.put(11);
		s2.put(22);
		s2.put(33);
		System.out.println("--------------");
		System.out.println(s2.empty());
		System.out.println("队列第一个元素："+s2.peek());
		System.out.println("弹出元素："+s2.take());
		System.out.println("弹出元素："+s2.take());
		System.out.println("弹出元素："+s2.take());
		System.out.println(s2.empty());
	}

}
class QueueS {
	final int MAXSIZE=10;
	private int _MAXSIZE;
	private int base;
	private int top;
	Object []t;
	int k;
	QueueS(){
		t=new Object[MAXSIZE];
		_MAXSIZE=MAXSIZE;
		base=-1;
		top=-1;
	}
	public boolean empty() {
		return base==top;
	}
	public N peek() {
		if(empty())
			return null;
		else
			k=(base+1)%_MAXSIZE;
			return (N)t[k];
	}
	public boolean enhance(int k) {
		Object []m=new Object[k];
		for(int i=0;i<=top;i++)
			m[i]=t[i];
		t=m;
		_MAXSIZE=k;
		return true;
	}
	public N put(N date) {
		if(top+1==base)
			return null;
		top=(top+1)%_MAXSIZE;
		t[top]=date;
		return date;
	}
	public N take() {
		if(empty())
			return null;
		base=(base+1)%_MAXSIZE;
		return (N)t[base];
	}
}

链式队列：也是需要一个头“指针”（base）和一个尾“指针”（top），入队列（put）就是生成一个新的节点，让尾节点的下一个节点为这个新生成的节点，然后再让尾节点等于这个新生成的节点。

出队列（take），就是让头节点的下一个等于头节点的下一个的下一个，这样操作完就出队列一个元素。

public class Text2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		QueueS s2=new QueueS();
		s2.put(11);
		s2.put(22);
		s2.put(33);
		System.out.println("--------------");
		System.out.println(s2.empty());
		System.out.println("队列第一个元素："+s2.peek());
		System.out.println("弹出元素："+s2.take());
		System.out.println("弹出元素："+s2.take());
		System.out.println("弹出元素："+s2.take());
		System.out.println(s2.empty());
	}

}
class QueueS {
	final int MAXSIZE=10;
	private int _MAXSIZE;
	private int base;
	private int top;
	Object []t;
	int k;
	QueueS(){
		t=new Object[MAXSIZE];
		_MAXSIZE=MAXSIZE;
		base=-1;
		top=-1;
	}
	public boolean empty() {
		return base==top;
	}
	public N peek() {
		if(empty())
			return null;
		else
			k=(base+1)%_MAXSIZE;
			return (N)t[k];
	}
	public boolean enhance(int k) {
		Object []m=new Object[k];
		for(int i=0;i<=top;i++)
			m[i]=t[i];
		t=m;
		_MAXSIZE=k;
		return true;
	}
	public N put(N date) {
		if(top+1==base)
			return null;
		top=(top+1)%_MAXSIZE;
		t[top]=date;
		return date;
	}
	public N take() {
		if(empty())
			return null;
		base=(base+1)%_MAXSIZE;
		return (N)t[base];
	}
}

还有一个很重要，java中没有指针，所说的“指针”就是类似于指针的操作。

或许有人会问，为什么base或top能在节点上像指针一样移动？

这是因为我们定义了一个类，next就是这个类的一个对象，而next又是这个类的一个成员，那我们每次调用base.next的时候，就相当于调用base这个对象的一个成员next，next又是这个类的对象，反复这样就构成了一个链式的结构。

 谢谢观看！