数据结构与算法(五)队列

定义

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

特点

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出

  • 先进先出(FIFO--first in first out)

图形

  1. 单向队列

image.png

  1. 循环队列

image.png

手写一个循环队列

public class MyQueue<E> {

    private Object[] data;

    private int head;

    private int tail;

    private int capacity; //队列容量

    private static int DEFAULT_CAPACITY = 10;

    public MyQueue(){
        this(DEFAULT_CAPACITY);
    }


    public MyQueue(int capacity){
        this.capacity = capacity;
        data = new Object[capacity];
    }

    public void push(E e){
        if(tail - head == capacity) throw new IndexOutOfBoundsException("队列已满");
        data[tail++%capacity] = e;
    }

    @SuppressWarnings("unchecked")
    public E pop(){
        if(tail == head) return null;
        if(head >= capacity){
            head -= capacity;
            tail -= capacity;
        }
        Object e = data[head];
        data[head++] = null;
        return (E) e;
    }

    public int size(){
        return tail - head;
    }

    public boolean isEmpty(){
        return tail == head;
    }
}
# 队列 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×