[数据结构与算法]【数据结构6】队列

1、基本常识

1.1 什么是队列

????????只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

1.2 队列的特点

????????队列是一种先进先出的线性表，简称FIFO。

2、队列的实现——数组

用数组来实现的话问题就在于一个数组新创建出来长度就已经固定，所以在增删操作时就要不断新建新的数组，把原来复制过去，再进行增删。

开始先定义新建一个数组

public class arrayQ {
	private  Object[] sa=new Object[0];
}

接着就是实现一些基本功能，增删改查，获取个数，遍历

增

public void add(Object s) {
		  //1.新建一个数组，是原数组长度+1,扩容
		Object[] temA=new Object[sa.length+1];
		  //2.把原数组的，复制到新数组
		for(int i=0;i<sa.length;i++){
			temA[i]=sa[i];			
		}
		//数据结加新数组最后一个位子
		temA[temA.length-1]=s;
		sa=temA;
	}

删

public Object pop() {
		//1.新建一个数组，是原数组长度-1,缩小
		Object[] temB=new Object[sa.length-1];
		//2.取出出队的数据
		Object a = sa[sa.length-1];
		//3.复制除最后一个队列元素的所有元素
		for(int i=0;i<sa.length-1;i++) {
			temB[i] = sa[i];
		}
		sa = temB;
		return a;
	}

改：

public void update(int index,Object s) {
		if (index < 0 || index >= sa.length) {
			System.out.println("位置不合法");
			}
		sa[index] = s;
	}

查：

	public Object get(int index){
		if (index < 0 || index >= sa.length) {
			System.out.println("位置不合法");
			return null;
		}
		Object m=sa[index];
		return m;
	}

获得队列中元素的个数：

public int size(){
		return sa.length;
	}

遍历打印队列：

	public void print() {
		for(int i=0;i<sa.length;i++) {
			System.out.println(""+sa[i]);
		}
	}