第二章 线性结构+顺序存储(队列的定义和实现)

目录

队列

队列的定义

队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表
●我们把允许删除的一端称为队首(front) ,插入的一端称为队尾(rear)
●不含任何数据元素的队列称为空队列
●队列是一种先进先出(First In Last Out)的线性表,简称FIFO
●队列本身是一个线性表,其数据元素具有线性关系,只不过它是一种特殊的线性表而已
●队列的插入操作,叫作入队
●队列的删除操作,叫作出队
第二章 线性结构+顺序存储(队列的定义和实现)

队列的理解

可以看成是排队打饭,先来的先打饭

第二章 线性结构+顺序存储(队列的定义和实现)

介绍完之后,同样我们开始实现队列的代码实现,因为队列和我们上面定义好的栈以及线性表功能不同,所以我们还是要重新写队列的接口,队列的功能线性表基本都有,所以,我们对线性表进行二次封装即可。

代码

接口

package p1.接口;

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();
}

package p2.线性结构;
import p1.接口.Queue;
import java.util.Iterator;

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<E> 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;
    }
}

测试代码

package p0.测试;

import p2.线性结构.ArrayQueue;

public class TestArrayQueue {
    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i = 1; i <= 10; i++) {
            queue.offer(i);
        }
        System.out.println(queue);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue);
    }
}
输出
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1
2
[3, 4, 5, 6, 7, 8, 9, 10]

队列介绍完了,那来看一下对列的应用

文件夹的遍历(用对列实现,也就是层序遍历)

思路

先让需要遍历的A文件夹入队,只要队列不为空,就一直让里面出队,所以A出队,A出队后就开始listFiles方法遍历A目录里面的内容,A里面的内容入队,也就是B、C文件夹入队,其他文件直接打印文件名(因为除了文件夹,其他文件没有下一层文件)。然后按顺序,B出队,里面内容入队/打印,C出队,里面内容入队/打印…
第二章 线性结构+顺序存储(队列的定义和实现)

代码

package p2.线性结构;

import java.io.File;

//文件夹遍历
public class DirectoryTraversal {
    public static void main(String[] args) {
        /*
         * 只要队列不为空 则出队一个目录对象
         * 将该目录对象展开 开始遍历 遇到文件则打印名称 遇到其他目录 则进队
         * */
        File dir = new File("C:\\Users\\HENG\\Desktop\\DS");
        ArrayLoopQueue<File> queue = new ArrayLoopQueue<>();
        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);
                }
            }
        }
    }
}

栈和队列的相互转换

栈实现队列

思路

创建两个栈A、B(辅助栈),每次入队时,直接正常入队A,出队时,先把A中元素弹栈到B,弹到最后一个元素即时出队元素,然后再让B中元素弹栈到A,及完成一次出队。(查看队首元素同理),然后入对的话,就自己入队A…

第二章 线性结构+顺序存储(队列的定义和实现)

代码

package p2.线性结构;

import p1.接口.Queue;

import java.util.Iterator;

//栈实现队列
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();
    }
}
测试输出:
[1, 2, 3, 4, 5]
1
[2, 3, 4, 5]

队列实现栈

思路

同栈实现队列,但B中的元素没必要再次弹到A,因为涉及先后顺序问题,栈(先进后出,弹到另一个栈时,顺序和原来相反,所以需要重新弹栈回来,保持顺序不变)实现队列需要,但队列(先进先出,出队到另一个队列是顺序还是一样)实现栈不需要,这个地方也好理解

代码

package p2.线性结构;

import p1.接口.Stack;

import java.util.Iterator;

//队列实现栈
public class QueueToStack {
    public static void main(String[] args) {
        StackImplByQueue<Integer> stack = new StackImplByQueue<>();
        System.out.println(stack);
        for (int i = 1; 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) {
                queueA.offer(queueB.poll());
            }
            ret = queueB.poll();
        }
        return ret;
    }

    @Override
    public E peek() {
        if (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();
        }
    }

}
测试输出:
[]
[1, 2, 3, 4, 5]
5
[1, 2, 3, 4]

回顾ArrayQueue

队列的顺序存储结构本身是由ArrayList实现的
在数据元素入队的时候,相当于在ArrayList表尾添加元素
在数据元素出队的时候,相当于在ArrayList表头删除元素
很明显,入队的时间复杂度0(1),出队的时间复杂度O(n),因为,出队一个元素,后面的元素都需要前移(因为底层使用数组实现的)
线性表增删数据元素时间复杂符都是O(n),但是这个是按平均算的
队列的出队时间复杂度O(n),可不是按平均算的,因为每次出队都是O(n)

那么出队时间复杂度能否优化呢?

优化

1、头指针后移

能否让队头指针和队尾指针一样随着数据元素的变化而移动?

出队一个元素,头指针向后移

第二章 线性结构+顺序存储(队列的定义和实现)

但是,问题也很明显

  1. Rear指针不能再继续后移了
    2)浪费了-些空间

2、头尾指针移动时,按循环移动(Rear+1)%n

第二章 线性结构+顺序存储(队列的定义和实现)

这样解决了浪费空间的问题,但怎么判断对满呢

队列满的条件(Rear+1)%n==Front第二章 线性结构+顺序存储(队列的定义和实现)

但队列空的条件(Rear+1 )%n==Front第二章 线性结构+顺序存储(队列的定义和实现)

3、牺牲一个存储单元

将一个空间预留出来不存任何元素,尾指针始终指向这个null空间

开始时,队列为空,首位指针指向同一个,添加一个元素,rear指针后移,删除一个元素,front指针后移,所以每次添加完之后,rear指向的都是一个空的地址,到最后还有一个空地址时,即rear的下一个是front时,显示对满,添加不了,这样,对满和对空的判断就是不同的

第二章 线性结构+顺序存储(队列的定义和实现)

队列满的条件(Rear+1)%nFront
队列空的条件Rear
Front

思考?

能不能不牺牲存储单元,但也能实现对满、对空判断呢?(Rear+1)%n==Front

1、定义一个size保存里面有多少个值

2、定一个flag,记录上一步是删除操作还是添加操作,如果上一步是添加,那么便是对满,如果上一步是删除,那么便是对空

3、…

循环队列ArrayLoopQueue

该循环队列的实现思想也是动态数组
但是由于操作元素的特殊性,并不能直接由ArrayList或ArrayQueue实现
所以从头开始定义ArrayLoopQueue

基本思路都一样,就是把ArrayQueue中添加元素,删除元素,判断满和空改变一下

代码

package p2.线性结构;

import p1.接口.Queue;
import java.util.Iterator;
//循环队列
public class ArrayLoopQueue<E> implements Queue<E> {
    private E[] data;   //存储数据的容器
    private int front;  //队首指针(实际上就是数组中的索引角标)
    private int rear;   //队尾指针
    private int size;   //元素的个数 (f < r  r-f ; r < f  r+L-f)
    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++;
    }
    @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;
    }

    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 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[j])) {
                    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;
        }
    }
}

双端队列的定义

双端队列(double ended queue,deque)

是限定插入和删除操作在表的两端进行的线性表
是一种具有队列和栈的性质的数据结构

不管在那边进行删除和插入,front始终指向一边的首元素,rear始终指向一边的尾元素的后一个,所以在此原理上进行相应的代码改变

第二章 线性结构+顺序存储(队列的定义和实现)

判断对空对满和循环队列一样

Deque双端队列接口的定义
双端队列大致思想与循环队列一样
无非在队首可添加,在队尾可删除

代码

接口:因为功能比队列多一点,所以我们继承上面的Queue接口,再添加点方法

package p1.接口;

public interface Dequeue<E> extends Queue<E> {
    public void addFirst(E element);
    public void addLast(E element);
    public E removeFirst();
    public E reomveLast();
    public E getFirst();
    public E getLast();
}

package p2.线性结构;

import p1.接口.Dequeue;
import p1.接口.Stack;

import java.util.Arrays;
import java.util.Iterator;

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[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 void addLast(E element) {
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }

    @Override
    public E removeFirst() {
        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 null;
    }

    @Override
    public E reomveLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        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 element() {
        return getFirst();
    }

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

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

    @Override
    public void push(E element) {
        addLast(element);
    }

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

    @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 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;
        }
    }
}

继承关系总结

第二章 线性结构+顺序存储(队列的定义和实现)

上一篇:easyui中选项卡tabs嵌套了data-grid,结果不显示,单调访问表格数据jsp页面没有问题


下一篇:双端队列