java 数据结构堆栈和队列分析

虾米哥 阅读:427 2021-04-01 10:06:50 评论:0

队列的基本概念

              队列(简称队)也是一种特殊的线性表,队列的数据元素以及数据元素间的逻辑关系和线性表完全相同。差别是线性表允许在任意位置插入和删除,而队列只允许在一端进行插入操作而在另一端进行删除操作。

              队列中允许插入操作的一端称为队尾,允许进行删除操作的一端称为队头。队列的插入操作通常称为入队列,队列的删除操作通常称为出队列。

              根据队列的定义,每次入队列的数据元素都放在原来的队尾之后成为新的队尾元素,每次出队列的数据元素都是队头元素。这样,最先入队列的数据元素总是最先出队列。最后入队列的数据元素总是最后出队列,所以队列也称为先进先出表。

 

队列的抽象数据类型

              1、数据集合:队列的数据集合可以表示为a1,a2,a3,a4,每个数据元素的数据类型可以是任意类类型

               2、操作集合:1、入队列操作(append())

                                          2、出队列操作(delete())

                                          3、取队列的头元素(getFront())

                                          4、判断队列是否为空(isEmpty())

源代码------顺序存储结构

 

队列接口代码

package com.queue; 
//队列接口 
public interface Queue { 
	//入队列操作 
	public void append(Object object); 
	//出队列操作 
	public Object delete(); 
	//取队列头元素 
	public Object getFront(); 
	//判断队列是否为空 
	public boolean isEmpty(); 
 
}


队列接口实例化类

package com.queue; 
 
public class SeqQueue implements Queue { 
	//相关属性和构造方法 
	//默认大小 
	static final int defauleSize=10; 
	//队头 
	int front; 
	//队尾 
	int rear; 
	//队列元素个数统计 
	int count; 
	//队列初始化大小 
	int maxSize; 
	//队列数据信息 
	Object[] data; 
	 
	public void initiate(int sz){ 
		maxSize=sz; 
		front=rear=0; 
		count=0; 
		data=new Object[sz]; 
	} 
	 
	public SeqQueue(){ 
		initiate(defauleSize); 
	} 
	public SeqQueue(int length){ 
		initiate(length); 
	} 
 
	@Override 
	public void append(Object object) { 
		// TODO Auto-generated method stub 
             if(count>0&&front==rear){ 
            	 return; 
             } 
             data[rear]=object; 
             //求模运算 
             rear=(rear+1)%maxSize; 
             count++; 
	} 
 
	@Override 
	public Object delete() { 
		// TODO Auto-generated method stub 
		Object object=null; 
		if(count==0){ 
			object="404"; 
			return object; 
		}else{ 
			object=data[front]; 
			//求模运算 
			front=(front+1)%maxSize; 
			count--; 
			return object; 
		} 
		 
	} 
 
	@Override 
	public Object getFront() { 
		// TODO Auto-generated method stub 
		Object object=null; 
		if(count==0){ 
			object="404"; 
			return object; 
		}else{ 
			return data[front]; 
		} 
		 
	} 
 
	@Override 
	public boolean isEmpty() { 
		// TODO Auto-generated method stub 
		return count!=0; 
	} 
 
} 


实验结果:

package com.queue; 
 
public class QueueTest { 
 
	/** 
	 * @param args 
	 */ 
	public static void main(String[] args) { 
		// TODO Auto-generated method stub 
		SeqQueue queue=new SeqQueue(); 
		//判断队列是否为空 
		boolean target=queue.isEmpty(); 
		System.out.println("队列是否为空:"+target); 
		//入队列 
		queue.append("c"); 
		queue.append("c++"); 
		queue.append("c#"); 
		queue.append("object-c"); 
		queue.append("php"); 
		queue.append("java"); 
		queue.append("ruby"); 
		queue.append("javascript"); 
		queue.append("ext"); 
		queue.append("jquery"); 
	      
		//再次判断队列是否为空 
		boolean targets=queue.isEmpty(); 
		System.out.println("再次判断队列是否为空:"+targets); 
		//出队列 
		Object object=queue.delete(); 
		System.out.println("出队列的元素是:"+object); 
		//取队列头元素 
		Object front=queue.getFront(); 
		System.out.println("队列头元素是:"+front); 
		 
 
	} 
 
} 


图片展示:

源代码--------链式存储结构

 接口代码

package com.queuelinked; 
 
//队列结点类 
public class QueueNode { 
	// 相关属性和构造函数 
	Object data; // 节点存储的数据 
	QueueNode next; // 指向下个节点的指针 
 
	public QueueNode() { 
		this(null, null); 
	} 
 
	public QueueNode(Object data) { 
		this(data, null); 
	} 
 
	public QueueNode(Object data, QueueNode next) { 
		this.data = data; 
		this.next = next; 
	} 
 
}


接口实例化类

package com.queuelinked; 
 
public class QueueLinked { 
	QueueNode front; // 队首指针 
	QueueNode rear; // 队尾指针 
 
	public QueueLinked() { 
		this.rear = null; 
		this.front = null; 
	} 
 
	/** 
	 * 将一个对象追加到队列的尾部 
	 *  
	 * @param obj 
	 *            对象 
	 */ 
	public void enqueue(Object obj) { 
		// 如果队列是空的 
		if (rear == null && front == null) { 
			rear = new QueueNode(obj); 
			front = rear; 
		} else { 
			QueueNode node = new QueueNode(obj); 
			rear.next = node; 
			rear = rear.next; 
		} 
	} 
 
	/** 
	 * 队首对象出队 
	 *  
	 * @return 出队的对象,队列空时返回null 
	 */ 
	public Object dequeue() { 
		// 如果队列空 
		if (front == null) { 
			return null; 
		} 
		// 如果队列中只剩下一个对象 
		if (front == rear && rear != null) { 
			QueueNode node = front; 
			rear = null; 
			front = null; 
			return node.data; 
		} 
		Object obj = front.data; 
		front = front.next; 
		return obj; 
	} 
 
}


实验结果

package com.queuelinked; 
 
public class QueueTest { 
 
	/** 
	 * @param args 
	 */ 
	public static void main(String[] args) { 
		// TODO Auto-generated method stub 
		QueueLinked q = new QueueLinked();   
		       q.enqueue("张三");   
		       q.enqueue("李斯");   
		       q.enqueue("赵五");   
		       q.enqueue("王一");   
		        for(int i=0;i<4;i++){ 
		        	System.out.println(q.dequeue());  
		        } 
		             
		      
 
	} 
 
} 


图片展示:

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

一个IT知识分享的公众号