java数据结构之队列

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

队列概述
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
–队尾(rear)——允许插入的一端
–队头(front)——允许删除的一端
队列特点：先进先出(FIFO)

线性表的操作主要包括：
（1）清空队列
（2）判断是否为空
（3）元素的个数
（4）入队列
（5）出队列
（6）取对头元素

接口
对队列的抽象数据类型定义Queue接口如下：
package com.example.code;

public interface Queue {
     /**
     * 清空队列
     */  
    public void clear();  
    /**
     * 出队列
     * @return
     */  
    public Object deQueue();  
    /**
     * 判断是否为空
     * @return
     */  
    public boolean isEmpty();  
    /**
     * 取对头元素
     * @return
     */  
    public Object peek();  
    /**
     * 入队列
     * @param obj
     */  
    public void push(Object obj);  
    /**
     * 元素的个数
     * @return
     */  
    public int size();  
}

顺序循环队列

结构模型：

存在问题
设数组长度为M，则：
–当front=0,rear=M时，再有元素入队发生溢出——真溢出
–当front!=0,rear=M时，再有元素入队发生溢出——假溢出
解决方案
–队首固定，每次出队剩余元素向下移动——浪费时间
–循环队列
»基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;

模拟ArrayQueue实现Queue

package com.example.code;

public class MyArrayQueue implements Queue {
    private static  int  DEFAULT_SIZE = 10;   
    private Object array[] = null;  
    private int front, rear, count; //队首，队尾标注和队列的大小  
    
    public MyArrayQueue() {  
        array = new Object[DEFAULT_SIZE];  
        front = rear = count = 0;  
    }  
    @Override
    public void clear() {
        for(int i=0; i<DEFAULT_SIZE; i++) {  
            array[i] = null;  
        }  
        front = rear = count = 0;  
    }

@Override
    public Object deQueue() {
        if(0 == count) {  
            throw new IllegalStateException("队列已空，无数据元素可出队列！");  
        } else {  
            Object obj = array[front];  
            front = (front+1)%DEFAULT_SIZE;  
            count --;  
            return obj;  
        }  
    }

@Override
    public boolean isEmpty() {
        if((rear == front) && (0 == count))  
            return true;  
        else  
            return false;  
    }

@Override
    public Object peek() {
        if(0 == count) {  
            throw new IllegalStateException("队列已空，无数据元素可出队列！");  
        } else{
            return array[front];
        }
    }
    
    private void expand() {  
        Object newArray[] = new Object[2*DEFAULT_SIZE];  
        for(int i=0; i<count; i++) {  
            newArray[i] = array[(front+i)%DEFAULT_SIZE];  
        }  
        array = newArray;  
        front = 0;   
        rear = count;  
        DEFAULT_SIZE = 2*DEFAULT_SIZE;  
    }
    @Override
    public void push(Object obj) {
        if((rear == front) && (count>0))  
            expand();  
        array[rear] = obj;  
        rear = (rear+1)%DEFAULT_SIZE;  
        count ++;  
    }

@Override
    public int size() {
        return count;  
    }

}

链式队列
结构模型

模拟LinkQueue实现Queue接口

package com.example.code2;

import com.example.code.Queue;

public class MyLinkQueue implements Queue {
    private Node front,rear;    //队头指针和队尾指针  
    private int size;  
    public MyLinkQueue() {  
        front = rear = new Node();  
        size = 0;  
    }  
    @Override  
    public void clear() {  
        front.next = null;  
        rear = front;  
        size = 0;  
    }  
 
    @Override  
    public Object deQueue() {  
        Node p = front.next;  
        front.next = p.next;  
        rear = p.next;  
        size --;  
        return p.data;  
    }  
 
    @Override  
    public boolean isEmpty() {  
        if(size == 0)  
            return true;  
        else   
            return false;  
    }  
 
    @Override  
    public Object peek() {  
        return front.next.data;  
    }  
 
    @Override  
    public void push(Object obj) {  
        Node p = new Node(obj);  
        rear.next = p;  
        rear = p;  
        size ++;  
    }  
 
    @Override  
    public int size() {  
        return size;  
    }  
      
    public String toString() {  
        StringBuilder sb= new StringBuilder("[");  
        Node p = front;  
        while((p=p.next) != null) {  
            sb.append(p.data + ", ");  
        }  
        sb.append("]");  
        return sb.toString();     
    }  
}

/**
 * 链队列的结点
 *
 */  
class Node{  
    Object data;    //数据元素  
    Node next;      //后驱结点  
    public Node() {  
        this(null);  
    }  
    public Node(Object data) {  
        this.data = data;  
        this.next = null;  
    }  
}

转载：http://blog.csdn.net/luoweifu/article/details/8507835