算法和数据结构------队列的实现

本文主要是介绍算法和数据结构------队列的实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

队列的的定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

•我们把允许删除的一端称为队首（front），插入的一端称为队尾（rear） •不含任何数据元素的队列称为空队列 •队列是一种先进先出（First In Last Out）的线性表，简称FIFO •队列本身是一个线性表，其数据元素具有线性关系，只不过它是一种特殊的线性表而已 •队列的插入操作，叫作入队 •队列的删除操作，叫作出队

代码的实现

Queue队列的接口实现

同样队列可以顺序存储实现也可以链表存储实现，所以将共性抽取定义出Queue接口。

public interface Queue<E> extends Iterable<E> {
    //入队
    public void offer(E element);
    //出队
    public E poll();
    //查看队首元素
    public E element();
    public boolean isEmpty();
    public void clear();
    public int size();
}

ArrayQueue类的实现

该类为队列的顺序存储具体实现，因为队列本身就是一种特殊的线性表，所以我们可以借用之前完成的ArrayList来实现我们的ArrayQueue。

public class ArrayQueue<E> implements Queue<E> {
    private ArrayList<E> list;
    public ArrayQueue() {
        list = new ArrayList<>();
    }
    @Override
    public void offer(E element) {
        list.add(list.size(), element);
    }
    @Override
    public E poll() {
        return list.remove(0);
    }
    @Override
    public E element() {
        return list.get(0);
    }
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
    @Override
    public void clear() {
        list.clear();
    }
    @Override
    public int size() {
        return list.size();
    }
    @Override
    public Iterator iterator() {
        return list.iterator();
    }
    @Override
    public String toString() {
        return list.toString();
    }
    @Override
    public boolean equals(Object o) {
        if (o == null){
            return false;
        }
        if (this == o){
            return true;
        }
        if (o instanceof ArrayQueue){
            ArrayQueue other = (ArrayQueue) o;
            return list.equals(other.list);
        }
        return false;
    }
}

文件夹遍历

只要队列不为空 则出队一个目录对象
将该目录对象展开 开始遍历 遇到文件则打印名称 遇到其他目录 则进队

代码实现

public class DirectoryTraversal {
    public static void main(String[] args){
        /*
         *只要队列不为空 则出队一个目录对象
         * 将该目录对象展开 开始遍历 遇到文件则打印名称 遇到其他目录 则进队
         */
        File dir = new File("D:\IDEA Demo One");
        QueueImplByStack<File> queue = new QueueImplByStack<>();
        queue.offer(dir);
        while (!queue.isEmpty()){
            File file = queue.poll();
            System.out.println("【" + file.getName() + "】");
            File[] files = file.listFiles();
            for (File f : files){
                if (f.isFile()){
                    System.out.println(f.getName());
                }else{
                    queue.offer(f);
                }
            }
        }
    }
}

栈实现队列

栈和队列，严格意义上来说，也属于线性表，因为它们也都用于存储逻辑关系为 "一对一" 的数据，使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使用队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列。

栈实现队列

public class StackToQueue {
    public static void main(String[] args) {
        QueueImplByStack<Integer> queue = new QueueImplByStack<>();
        for (int i = 1; i <= 5; i++){
            queue.offer(i);
        }
        System.out.println(queue);
        System.out.println(queue.poll());
        System.out.println(queue);
    }
}
class QueueImplByStack<E> implements Queue<E>{
    private ArrayStack<E> stackA;
    private ArrayStack<E> stackB;
    public QueueImplByStack(){
        stackA = new ArrayStack<>();
        stackB = new ArrayStack<>();
    }

    @Override
    public void offer(E element) {
        stackA.push(element);
    }

    @Override
    public E poll() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        while (stackA.size() != 1){
            stackB.push(stackA.pop());
        }
        E ret = stackA.pop();

        while (!stackB.isEmpty()){
            stackA.push(stackB.pop());
        }
        return ret;
    }

    @Override
    public E element() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        while (stackA.size() != 1){
            stackB.push(stackA.pop());
        }
        E ret = stackA.peek();

        while (!stackB.isEmpty()){
            stackA.push(stackB.pop());
        }
        return ret;
    }

    @Override
    public boolean isEmpty() {
        return stackA.isEmpty();
    }

    @Override
    public void clear() {
        stackA.clear();
    }

    @Override
    public int size() {
        return stackA.size();
    }

    @Override
    public Iterator<E> iterator() {
        return stackA.iterator();
    }

    @Override
    public String toString() {
        return stackA.toString();
    }
}

队列实现栈

用队列实现栈操作，其中主要是top和pop操作，和用栈实现队列一样，我们需要一个新队列辅助操作实现。
pop中需要将栈顶元素（队尾元素）出栈（释放队尾元素），将队列中的元素除队尾元素外全部入辅助队列，再将辅助队列元素再全部入原来的队列。
top中需要返回队尾元素，和pop的实现大致相同，只是在出队中将最后一个元素保存返回。

//队列实现栈
public class QueueToStack {
    public static void main(String[] args) {
        StackImplByQueue<Integer> stack = new StackImplByQueue<>();
        System.out.println(stack);
        for (int i = 0; i <= 5; i++){
            stack.push(i);//队列A
        }
        System.out.println(stack.toString());
        System.out.println(stack.pop());
        System.out.println(stack);//队列B

    }
}
class StackImplByQueue<E> implements Stack<E>{
    private ArrayQueue<E> queueA;
    private ArrayQueue<E> queueB;

    public StackImplByQueue(){
        queueA = new ArrayQueue<>();
        queueB = new ArrayQueue<>();
    }

    @Override
    public int size() {
       if (queueA.isEmpty() && queueB.isEmpty()){
           return 0;
       }else if (!queueA.isEmpty()){
           return queueA.size();
       }else{
           return queueB.size();
       }
    }

    @Override
    public boolean isEmpty() {
        return queueA.isEmpty() && queueB.isEmpty();
    }

    @Override
    public void push(E element) {
        if (queueA.isEmpty() && queueB.isEmpty()){
            queueA.offer(element);
        }else if (!queueA.isEmpty()){
            queueA.offer(element);
        }else{
            queueB.offer(element);
        }

    }

    @Override
    public E pop() {
        if (isEmpty()){
            return null;
        }
        E ret = null;
        if (!queueA.isEmpty()){
            while(queueA.size() != 1){
                queueB.offer(queueA.poll());
            }
            ret = queueA.poll();
        }else {
            while (queueB.size() != 1){
                queueB.offer(queueB.poll());
            }
            ret = queueB.poll();

        }
        return ret;
    }

    @Override
    public E peek() {
       if (!queueA.isEmpty()){
           return null;
           }
       E ret = null;
       if (!queueA.isEmpty()){
           while(queueA.size() != 1){
               queueB.offer((queueA.poll()));
           }
           ret = queueA.poll();
           queueB.offer(ret);
       }else{
           while (queueB.size() != 1){
               queueA.offer((queueB.poll()));
           }
           ret = queueB.poll();
           queueA.offer(ret);
       }
       return ret;
    }

    @Override
    public void clear() {
        queueA.clear();
        queueB.clear();

    }

    @Override
    public Iterator<E> iterator() {
        if (isEmpty()){
            return queueA.iterator();
        }else if (!queueA.isEmpty()){
            return queueA.iterator();
        }else{
            return queueB.iterator();
        }
    }

    @Override
    public String toString() {
        if (isEmpty()){
            return "[]";
        }else if (!queueA.isEmpty()){
            return queueA.toString();
        }else{
            return queueB.toString();
        }
    }
}

循环队列

当在队列中插入一个新数据项，队头的Rear箭头向上移动，移向数组下标大的位置。移除数据项时，队尾Front指针也会向上移动。这种设计可能和人们直观察觉相反，因为人们在买电影票排队时，队伍总是向前移动的，当前面的人买完票离开队伍后，其他人都向前移动。计算机中在队列里删除一个数据项后，也可以将其他数据项都向前移动，但这样做的效率很差。相反，我们通过队列中队头和队尾指针的移动保持所有数据项的位置不变。

队列满的条件 (Rear+1)%n==Front

队列空的条件 (Rear+1)%n==Front

ArrayLoopQueue的实现

public class ArrayLoopQueue<E> implements Queue<E> {
    //存储数据的容器
    private E[] data;
    //队首指针(实际上就是数组中的索引角标)
    private int front;
    //队尾指针
    private int rear;
    //元素个数(f < r  r-f ; r < f ; )
    private int size;
    //默认容量
    private static int DEFAULT_CAPACITY = 10;


    public ArrayLoopQueue(){
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    public void offer(E element) {
        //满了没
        if ((rear + 1) % data.length == front){
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }

    private void resize(int newlen) {
        E[] newData = (E[]) new Object[newlen];
        int index = 0;
        for (int i = front; i != rear; i = (i + 1) & data.length){
            newData[index++] = data[i];
        }
        data = newData;
        front = 0;
        rear = index;
    }

    @Override
    public E poll() {
        //空不空
        if (isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY){
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    @Override
    public E element() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        return data[front];
    }

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

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
        front = 0;
        rear = 0;
    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()){
            sb.append(']');
            return sb.toString();
        }
        for (int i = front; i != rear; i = (i + 1) % data.length){
            sb.append(data[i]);
            if ((i + 1) % data.length == rear){
                sb.append(']');
            }else{
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    @Override
    public boolean equals(Object o) { if(o == null){
        return false;
    }
        if (this == o){
            return true;
        }
        if (o instanceof ArrayLoopQueue){
            ArrayLoopQueue<E> other = (ArrayLoopQueue<E>) o;
            if (size != other.size){
                return false;
            }
            int i = front;
            int j = other.front;
            while (i != rear){
                if (data[i].equals(other.data[i])){
                    return false;
                }
                i = (i + 1) % data.length;
                j = (j + 1) % other.data.length;
            }
            return true;
        }
        return false;

    }
    @Override
    public Iterator<E> iterator() {
        return new ArrayLoopQueueIterator();
    }
    class ArrayLoopQueueIterator implements Iterator<E>{

        private  int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}

双端队列的实现

双端队列（deque，即double-ended queue的缩写）是一种具有队列和栈性质的数据结构，即可在线性表的两端进行插入和删除。双端队列使用了循环队列。判断满不满的条件是多开一个空间，即判断rear与front的关系。我们rear指针指向元素的下一个空位置，front指向元素

Deque双端队列接口的定义

双端队列大致思想与循环队列一样，无非在队首可添加，在队尾可删除

public interface Dequeue<E> extends Queue<E> {
    public void addFirst(E element);//在表头添加元素
    public void addLast(E element);//在表尾添加元素
    public E removeFirst();//在表头删除一个元素
    public E removeLast();//在表尾删除一个元素
    public E getFirst();//获取表头的元素
    public E getLast();//获取表尾的元素
}

ArrayDeque类的实现

addLast();队尾添加元素
addFirst());队头添加元素
removeFirst();移除列首元素
removeLast();移除列尾元素

public class ArrayDeque<E> implements Dequeue<E>, Stack<E> {
    private E[] data;
    private int front;
    private int rear;
    private int size;
    private static int DEFAULT_CAPACITY = 10;

    public ArrayDeque(){
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    public void addFirst(E element) {
        if ((rear + 1) % data.length == front){
            resize(data.length * 2 - 1);
        }
        front = (front - 1 + data.length ) % data.length;
        data[front] = element;
        size++;
    }

    private void resize(int newLen) {
        E[] newData = (E[]) new Object[DEFAULT_CAPACITY];
        int index = 0;
        for (int i = front; i !=rear; i = (i + 1) % data.length){
            newData[index++] = data[i];
        }
        data = newData;
        front = 0;
        rear = index;
    }

    @Override
    public void addLast(E element) {
        //判断是否满 角标的角度考虑
        if ((rear + 1) % data.length == front){
            //扩容
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        //rear向后移
        rear = (rear + 1) % data.length;
        size++;
    }

    @Override
    public E removeFirst() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        E ret = data[front];
        //front向后移
        front = (front + 1) % data.length;
        size--;
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY){
            resize(data.length / 2 + 1);
        }
        return null;
    }

    @Override
    public E removeLast() {
        //判空
        if (isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        //rear向前移
        rear = (rear - 1 + data.length) % data.length;
        E ret = data[rear];
        size--;
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY){
            //缩容
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    @Override
    public E getFirst() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        return data[front];
    }

    @Override
    public E getLast() {
        if (isEmpty()){
            throw new IllegalArgumentException("queue is null");
        }
        return data[(rear - 1 + data.length) % data.length];
    }

    @Override
    //入队的添加
    public void offer(E element) {
        addLast(element);
    }

    @Override
    public E poll() {
        return removeFirst();
    }

    @Override
    public E peek() {
        return getLast();
    }

    @Override
    public E element() {
        return getFirst();
    }

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

    @Override
    //入栈操作
    public void push(E element) {
        addLast(element);

    }

    @Override
    public E pop() {
        return removeLast();
    }

    @Override
    public void clear() {
        E[] data = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = 0;
        size = 0;

    }

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

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()){
            sb.append(']');
            return sb.toString();
        }
        for (int i = front; i != rear; i = (i + 1) % data.length){
            sb.append(data[i]);
            if ((i + 1) % data.length == rear){
                sb.append(']');
            }else{
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    @Override
    public boolean equals(Object o) {
        if(o == null){
            return false;
        }
        if (this == o){
            return true;
        }
        if (o instanceof ArrayDeque){
            ArrayDeque<E> other = (ArrayDeque<E>) o;
            if (size != other.size){
                return false;
            }
            int i = front;
            int j = other.front;
            while (i != rear){
                if (data[i].equals(other.data[i])){
                    return false;
                }
                i = (i + 1) % data.length;
                j = (j + 1) % other.data.length;
            }
            return true;
        }
        return false;
    }
    @Override
    public Iterator<E> iterator() {
        return new ArrayDequeIterator();
    }
    class ArrayDequeIterator implements Iterator<E>{
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}

本次分享就到这里，谢谢大家的观看！

这篇关于算法和数据结构------队列的实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程