数据结构——队列

队列的定义及基本运算

1、定义
    　队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
　　（1）允许删除的一端称为队头（Front）。
　　（2）允许插入的一端称为队尾（Rear）。
　　（3）当队列中没有元素时称为空队列。
　　（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
    　队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
　【例】在队列中依次加入元素a₁，a₂，…，a_n之后，a₁是队头元素，a_n是队尾元素。退出队列的次序只能是a₁，a₂，…，a_n。

2、java实现

package zieckey.datastructure.study.queue;

public class QueueInt
{
    private int        SIZE    = 20;    // 队列大小

    private int[]    queArray;        // 队列实际由数组构建

    int                front;            // 队列头，从这一端拿走一个元素

    int                rear;            // 队列尾，从这一端插入一个元素到队列中

    int                nItems;            // 队列中元素个数


    /**
     * 默认构造函数，队列大小为20
     */
    QueueInt( )
    {
        queArray = new int[SIZE];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    /**
     * 构造函数，队列大小由参数size决定。
     *
     * @param size
     * 队列大小
     */
    QueueInt( int size )
    {
        SIZE = size;
        queArray = new int[SIZE];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    /**
     * 插入一个元素到队列中
     *
     * @param iItem
     */
    public void insert( int iItem )
    {
        // 如果rear到达了队尾，就从头开始

        if ( rear == SIZE - 1 )
        {
            rear = -1;
        }

        if ( nItems == SIZE )
        {
            System.out
                    .println( "The Queue is full! Please remove some Items before inserting!" );
        } else
        {
            queArray[ ++rear] = iItem;
            nItems++ ;
        }
    }

    /**
     * @return 当前队列头的元素
     */
    public int remove()
    {
        if ( isEmpty() )
        {
            System.out
                    .println( "The Queue is empty! Please insert some Items before removing!" );
            return -1;
        } else
        {
            int frontItem = queArray[front++ ];// 得到当前队列前元素，并且队列头指针向前挪动一个

            if ( front == SIZE )
            {
                front = 0;
            }
            nItems-- ;
            return frontItem;
        }
    }

    public boolean isEmpty()
    {
        if ( nItems == 0 )
        {
            return true;
        }
        return false;
    }
    
    public int getSIZE()
    {
        return SIZE;
    }

    public void setSIZE( int size )
    {
        SIZE = size;
    }
}