数据结构——队列
2018-07-04 本文已影响20人
我哈啊哈啊哈
目录
1、什么是队列
2、队列的实现
2.1、基于简单循环数组的实现
2.1.1、为什么需要循环数组
2.1.2、代码实现
2.1.3、性能和局限性
2.2、基于动态循环数组的实现
2.2.1、代码实现
2.2.2、性能
2.3、基于链表的实现方法
2.3.1、代码实现
2.3.2、性能
正文
1、什么是队列
- 定义：队列是一种只能在一端插入（队尾），在另一端删除（队首）的有序线性表。
-
在队列中插入一个元素，称为入队（EnQueue）。从队列中删除一个元素，称为出队（DeQueue）。试图对一个空队列执行出队操作称为下溢（underflow），试图对一个满队列执行入队操作称为溢出（overflow）。
图1-1 队列
2、队列的实现
- 基于简单循环数组的实现
- 基于动态循环数组的实现
- 基于链表的实现方法
2.1、基于简单循环数组的实现
2.1.1、为什么需要循环数组
-
首先，分析是否可以借鉴基于简单数组实现栈的方法来实现队列。由队列的定义可知，只能在一端执行插入操作，而在另一端执行删除操作。当执行多次操作之后，出现如下问题，数组中靠前的空间浪费。
图2-1 简单数组实现队列
-
为了解决这个问题，假设数组是循环存储的方式，即将数组最后一个元素和第一个元素看作是连续的。依据这个假设，如果数组前端有空闲的空间，指向队尾的指针就能够很容易地移动到下一个空闲的位置。
图2-2 简单循环数组实现队列
- 在数组中，采用循环增加元素的方式，并使用两个变量分别记录队首元素和队尾元素。由于是固定大小的数组，可能会出现数组被填满的情况。这是如果执行入队操作，将抛出“队列满异常”。
2.1.2、代码实现
public class ArrayQueue {
private int front;
private int rear;
private int capacity;
private int[] array;
//初始化
private ArrayQueue(int size){
capacity=size;
front=-1;
rear=-1;
array=new int[size];
}
//创队列
public static ArrayQueue createQueue(int size){
return new ArrayQueue(size);
}
//是否空队列
public boolean isEmpty(){
return (front==-1);
}
//是否满队列
public boolean isFull(){
return ((rear+1)%capacity==front);
}
//队列大小
public int getQueueSize(){
return ((capacity-front+rear+1)%capacity);
}
//出队
public int deQueue(){
int data=-1;
if(isEmpty()){
return data;
}else {
data=array[front];
if(front==rear){
//空队列
front=rear=-1;
}else {
front=(front+1)%capacity;
}
}
return data;
}
//入队
public void enQueue(int data){
if(isFull()){
return;
}
else {
rear=(rear+1)%capacity;
array[rear]=data;
if(front==-1){
front=rear;
}
}
}
}
2.1.3、性能和局限性
-
性能：
图2-3 基于简单循环数组实现性能
- 局限性：用于实现队列的数组的最大空间必须预先声明且不能改变。试图对一个满队列执行入队操作会产生异常。
2.2、基于动态循环数组的实现
- 与简单循环数组的区别在于，试图对一个满队列执行入队操作时，会动态增加数组的大小，使之可以成功入队元素。
2.2.1、代码实现
public class DynArrayQueue {
private int front;
private int rear;
private int capacity;
private int[] array;
//构造函数
private DynArrayQueue(){
capacity=1;
front=-1;
rear=-1;
array=new int[1];
}
//创队列
public static DynArrayQueue createDynArrayQueue(){
return new DynArrayQueue();
}
//是否空队列
public boolean isEmpty(){
return (front==-1);
}
//是否满队列
public boolean isFull(){
return ((rear+1)%capacity==front);
}
//队列大小
public int getQueueSize(){
if(front==-1){
return 0;
}
int size=(capacity-front+rear+1)%capacity;
if(size==0){
return capacity;
}else {
return size;
}
}
//重置数组
public void resizeQueue(){
int initCapacity=capacity;
capacity*=2;
int[] oldArray=array;
array=new int[this.capacity];
for(int i=0;i<oldArray.length;i++){
array[i]=oldArray[i];
}
if(rear<front){
for(int i=0;i<front;i++){
array[i+initCapacity]=this.array[i];
array[i]=-1;
}
rear=rear+initCapacity;
}
}
//入队
public void enQueue(int data){
if(isFull()){
resizeQueue();
}
rear=(rear+1)%capacity;
array[rear]=data;
if(front==-1){
front=rear;
}
}
//出队
public int deQueue(){
int data=-1;
if(this.isEmpty()){
return data;
}else {
data=array[front];
if(front==rear){
//空队列
front=rear=-1;
}else {
front=(front+1)%capacity;
}
}
return data;
}
}
2.2.2、性能
图2-4 基于动态循环数组实现性能
2.3、基于链表的实现方法
-
通过在链表的末端插入元素的方法实现入队操作，通过删除链表表头元素的方法实现出队操作。
图2-5 链表实现队列
2.3.1、代码实现
public class LLQueue {
private ListNode frontNode;
private ListNode rearNode;
//构造函数
private LLQueue(){
this.frontNode=null;
this.rearNode=null;
}
//创队列
public static LLQueue creteQueue(){
return new LLQueue();
}
//是否空队列
public boolean isEmpty(){
return (frontNode==null);
}
//入队
public void enQueue(int data){
ListNode newNode=new ListNode(data);
if(rearNode!=null){
rearNode.setNext(newNode);
}
rearNode=newNode;
if(frontNode==null){
frontNode=rearNode;
}
}
//出队
public int deQueue(){
int data=-1;
if(isEmpty()){
return data;
}else {
data=frontNode.getData();
frontNode=frontNode.getNext();
}
return data;
}
}
2.3.2、性能
图2-6 基于链表实现性能
