目录
队列
队列的定义
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
●我们把允许删除的一端称为队首(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、头指针后移
能否让队头指针和队尾指针一样随着数据元素的变化而移动?
出队一个元素，头指针向后移
但是，问题也很明显
- Rear指针不能再继续后移了
2)浪费了-些空间
2、头尾指针移动时，按循环移动(Rear+1)%n
这样解决了浪费空间的问题，但怎么判断对满呢
队列满的条件(Rear+1)%n==Front
但队列空的条件(Rear+1 )%n==Front
3、牺牲一个存储单元
将一个空间预留出来不存任何元素，尾指针始终指向这个null空间
开始时，队列为空，首位指针指向同一个，添加一个元素，rear指针后移，删除一个元素，front指针后移，所以每次添加完之后，rear指向的都是一个空的地址，到最后还有一个空地址时，即rear的下一个是front时，显示对满，添加不了，这样，对满和对空的判断就是不同的
队列满的条件(Rear+1)%nFront
队列空的条件RearFront
思考？
能不能不牺牲存储单元，但也能实现对满、对空判断呢？(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;
}
}
}