04-17 07:28 阅读 186

关注

数据结构与算法——队列

引言

   本篇介绍队列的定义、队列的实现方式（数组实现队列，链表实现队列），如果你需要了解其他数据结构，请点击下面链接查看！！！

了解更多：数据结构与算法目录整理

队列

一、队列的定义

   队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
  队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

二、队列的实现方式（顺序存储于链式存储）

   1）队列的基本操作及其说明

   2）队列的数组实现

import java.util.ArrayList;import java.util.List;import java.util.Scanner;import javax.management.RuntimeErrorException;/**
 *  *队列的数组实现
 * @author 蜡笔小新
 *
 */public class Test3 {public static void main(String []args) {
 boolean temp=true;
 ArrQueue arrQueue=new ArrQueue(3);
 while(temp) {
 System.out.println("isFull:队列是否为满");
 System.out.println("isEmpty:队列是否为空");
 System.out.println("add:添加元素");
 System.out.println("getOne:获取元素");
 System.out.println("getHead:获取头部元素");
 System.out.println("getQueue:获取队列");
 System.out.println("size:获取队列中元素的个数");
 System.out.println("exit:退出程序");
 System.out.println("输入你的操作命令：");
 Scanner scanner=new Scanner(System.in);
 String str=scanner.nextLine();switch(str) {case "isFull": System.out.println(arrQueue.isFull());break;case "isEmpty": System.out.println(arrQueue.isEmpty());break;case "add": System.out.println("输入要添加的数据：");int n=scanner.nextInt(); arrQueue.add(n);break;case "getOne":try {int m = arrQueue.getOne();
System.out.println(m);} catch (Exception e) {
System.out.println(e.getMessage());}break;case "getHead":try {int s=arrQueue.getHead();
System.out.println(s);} catch (Exception e) {// TODO: handle exception
System.out.println(e.getMessage());}break;case "getQueue":try {
System.out.println(arrQueue.getQueue());} catch (Exception e) {// TODO: handle exception
System.out.println(e.getMessage());}break;case "size": System.out.println(arrQueue.size());break;case "exit": temp=false;break;default: System.out.println("输入有误");break;
 }
 }
 System.out.println("程序退出！");}}class ArrQueue{private int maxSize; //队列的最大容量private int front; //队列头private int rear; //队列尾private int []arr; //模拟队列public ArrQueue(int maxSize) {this.maxSize=maxSize;
front=-1; //指向头部的前一个位置
rear=-1; //指向尾部的位置
arr=new int[maxSize]; //初始化数组}//判断队列是否为空public boolean isEmpty() {return front==rear;}//判断队列是否为满public boolean isFull() {return rear==maxSize-1;}//向队列中添加元素public void add(int data) {if(isFull()) {
System.out.println("队列已满");return ;}
arr[++rear]=data;}//从队列中去除元素public int getOne() throws Exception{if(isEmpty()) {throw new Exception("队列为空");}

  return arr[++front];}//size() int 无 获取队列中元素的个数//getHead() int 无 获取头部元素public int getHead() throws Exception {if(isEmpty()) {throw new Exception("队列为空");}
  return arr[front+1];}//获取队列元素public List getQueue() {if(isEmpty()) {throw new RuntimeException("队列为空");}
List list=new ArrayList<>();for(int i=front+1;i<=rear;i++) {
list.add(arr[i]);}return list;}//获取队列元素个数public int size() {if(isEmpty()) {return 0;}return rear+1;}}

运行结果：

以上就是队列的数组实现，但是我们发现以上方法只能使用一次，无法做到复用的效果，因此对以上代码进行修改如下：

对以上程序中的 getOne()方法进行修改

//从队列中去除元素public int getOne() throws Exception{if(isEmpty()) {throw new Exception("队列为空");}

  int t=arr[++front];
  if(isEmpty()) {
  front=rear=-1;
  }
  else {
  for(int i=front+1;i<=rear;i++) {
  arr[i-1]=arr[i];
  }
  front--;
  rear--;
  }
  return t;}

   3）队列的链表实现