Java队列数据结构的实现

Java队列数据结构的实现

1.队列的基本概念

什么是队列?

队列是一种特殊的线性表

它只允许在表的前端（队头）进行删除操作

在表的后端（队尾）进行插入操作

队列是一个有序表(可以用数组或链表实现)

队列先进先出

队列开辟的是一块连续的空间

顺序队列中的溢出现象：

真溢出：当队列满时，做进栈运算产生空间溢出的现象。

假上溢：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。

2.循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增http://1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列

3.实现思路

由于普通队列存在溢出问题所以这里用数组来实现环形队列

1、front指向队列的首元素 初始为0

2、rear指向队列尾元素的后一个位置 (空出来的一块空间作为约定)初始为0

3、队列满的条件：(rear+1) % maxSize = front

4、队列空的条件：rear = front

5、队列中元素的个数：(rear+maxSize-front) % maxSize

为什么队列满的条件是(rear+1) % maxSize = front

(1)假设rear>front

rear-front=maxSize-1

rear+1-maxSize=front

由于当rear>front队列满时rear+1一定等于maxSize

(rear+1) % maxSize = rear+1-maxSize =0

(2)假设front>rearhttp://

front-rear=1

rear+1=front

由于当front>rear时rear+1一定小于maxSize

所以(rear+1) % maxSize=rear+1

(3)有上述所示可以得出队列满的条件是(rear+1) % maxSize = front

元素个数的计数与这相似

4.代码实现

public class Queue {

private int maxSzie; //队列中能存储的最大个数

private int frontPoint; //头指针指向队头

private int rearPoint; //尾指针指向队尾的后一个数据

private int[] array; //模拟队列的数组

/**

* 初始化队列

*/

public Queue(int max) {

maxSzie = max;

frontPoint = 0;

rearPoint = 0;

array = new int[max];

}

/**

* 判断队列是否为空

*/

public boolean isEmpty(){

return frontPoint == rearPoint;

}

/**

* 判断队列是否已满

*/

public boolean isFull(){

return (rearPoint+1)%maxSzie == frontPoint;

}

/**

* 向队列中添加数据

*/

public void add(int x){

if (isFull()){

System.out.println("当前队列已满");

return;

}

//添加数据

array[rearPoint] = x ;

//后移尾指针

rearPoint = (rearPoint+1) % maxSzie;

System.out.println("添加成功");

}

/**

* 取出队列中的数据

*/

public int remove(){

if (isEmpty()){

throw new RuntimeException("当前队列为空");

}

//把队头的值赋值给临时变量

int x = array[frontPoint];

//移除数据后头指针需要向后移动 时其指向新的队头

frontPoint = (frontPoint+1) % maxSzie;

System.out.println("移除成功");

return x;

}

/**

* 获取队列头数据

*/

public int gethead(){

if (isEmpty()){

throw new RuntimeException("当前队列为空");

}

return array[frontPoint];

}

/**

* 遍历队列

*/

public void show(){

int x = 0;

for (int i = frontPoint; i <= (rearPoint+maxSzie-frontPoint)%maxSzie; i++) {

x++;

System.out.println("队列的第"+x+"个数据是"+array[i]);

}

}

}

public class QueueTest {

public static void main(String[] args) {

Queue queue = new Queue(5);

Scanner scanner = new Scanner(System.in);

char systemIn = ' ';

boolean noEnd = true;

while (noEnd){

System.out.println("a:add(添加数据)");

System.out.println("r:remove(删除数据)");

System.out.println("h:head(获取队头)");

System.out.println("s:show(遍历队列)");

System.out.println("e:exit(退出程序)");

System.out.println("请输入字符");

systemIn = scanner.next().charAt(0);

switch (systemIn){

case 'a':

System.out.println("请输入入队的数据(数字)");

int x = Integer.parseInt(scanner.next());

queue.add(x);

break;

case 'r':

queue.remove();

break;

case 'h':

int head = queue.gethead();

System.out.println("队头是"+head);

break;

case 's':

queue.show();

EZfiGObihI break;

case 'e':

noEnd = false;

break;

}

}

}

}

5.测试

插入元素:

当添加到第五个的时候队列已满插入失败:

遍历队列:

移除元素:

查看队头:

删除一个元素后再次遍历队列:

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。