数据结构(四):认识队列、实现及其扩展

• • 队列的介绍
  • 队列的抽象数据类型描述
  • 循环顺序队列实现

队列是一种特殊的线性表,它的特殊性体现在队列只允许在表尾插入数据元素,在表头删除数据元素,具有FIFO或LILO的特性。
队列中,允许插入的一端叫队尾 (rear),允许删除的一端称为队首(front)。
如下图:

public interface Queue {
    public void clean();    //清空队列
    public boolean isEmpty();   //判断是否为空
    public int length();    //判断队列长度
    public Object peek();   //取出队首元素
    public void offer(Object x)throws Exception;    //从队尾插入元素
    public Object poll();   //出队操作并取出其值
}

注意:
1.循环队列在满状态的时候,会牺牲掉一个存储空间,原因是为了避免伪溢出!

从上图中看出,当最后一个位置插入F的时候,rear指针挪到了指针为6的位置,从而溢出报错,但是实际存储的数据没有溢出,为解决此问题,可以空出一个存储空间。

2.计算length:
(rear-front+queueElem.length)%queueElem.length
3.插入新元素

插入的位置:queueElem[rear]
插入后rear的位置:(rear+1)%queueElem.length();

public class QueueImpl implements Queue{
    //顺序队列实质上是一个数组
    private Object[] queueElem;
    private int front;  //队首,若队列不空,front指向第一个元素
    private int rear;   //队尾,若队列不空,rear指向队尾元素的下一个存储位置
    public QueueImpl(int maxSize){
        front = rear = 0;
        queueElem = new Object[maxSize];    //创建数组
    }
    @Override
    public void clean() {
        front = rear = 0;
    }

    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    @Override
    public int length() {
        return (rear-front+queueElem.length)%queueElem.length;
    }
    //从栈顶取出元素
    @Override
    public Object peek() {
        if(isEmpty()){
            return null;
        }else{
            return queueElem[front];
        }
    }
    //将x元素插入到队尾中使其称为新的元素
    @Override
    public void offer(Object x) throws Exception {
        //判断队列是否满
        if((rear+1)%queueElem.length==front){
            throw new Exception("队列已经满了");
        }
        queueElem[rear] = x;
        rear = (rear+1)%queueElem.length;
    }
    //从队首取出元素并返回其值
    @Override
    public Object poll() {
        if(isEmpty()){
            return null;
        }else{
            Object t = queueElem[front];
            front = (front+1)% queueElem.length;
            return t;
        }
	}
}