java 数据结构----------堆栈和队列

我不是女神ヾ 2023-10-16 18:39 138阅读 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);
    		
    
    	}
    
    }

图片展示：

![Center][]

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

接口代码

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()); 
    		        }
    		            
    		     
    
    	}
    
    }

图片展示：

![Center 1][]

[Center]: https://img-blog.csdn.net/20131105100119046?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvemhvdXpoaXdlbmdhbmc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20131105102233875?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvemhvdXpoaXdlbmdhbmc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center