Java教程
数据结构与算法（2）
本文主要是介绍数据结构与算法（2），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
笔记：
队列：（offer，poll，element ）
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
——我们把允许删除的一端称为队首（front），插入的一端称为队尾（rear）
——不含任何数据元素的队列称为空队列
——队列是一种先进先出（First In Last Out）的线性表，简称FIFO
——队列本身是一个线性表，其数据元素具有线性关系，只不过它是一种特殊的线性表而已
——队列的插入操作，叫入队
——队列的删除操作，叫出队
实现：ArrayQueue(底层可由ArrayList实现)
应用1：文件夹遍历 （listfile） （1）如果为目录则进队列
（2）如果为文件则输出文件名
循环队列：ArrayLoopQueue
（1） 定义队首指针（Front）和队尾指针（Rear）
两个指针随数据一起移动 ：出队时：Front++
入队时：Rear++
（2）当队尾或队头指针到达队尾时，如需后移可重新指向表头
队满：（Rear+1）%n==Front (n：队列长度)
队空：（Rear+1）%n==Front
（3）将一个空间预留出来不存在任何元素，尾指针始终指向这个null空间。
队空：Rear==Front
**·**扩缩容：
从头指针front处，以此遍历data中的元素，并从新数组的头部依次接收对应的值 直到front=rear。
注意：（1）有一个预留出来的空间不存元素 故而在创建队列时要使容量+1
(2)缩容时，size满足的条件必须给data的长度-1
（3）只有在扩，缩容时需要考虑当时给容量加的1，在其他情况下，data的长度必须是+1后的容 量才能保证长度的匹配。
扩容时，新长度等于旧长度*n再－（n-1）
缩容时，新长度等于旧长度/n再+（n+1）
双端队列 Deque
是限定插入和删除操作在表的两端进行的线性表，是一种具有队列和栈的性质的数据结构
判空，判满以及扩，缩容与循环队列一致
特有方法：
（1）addFirst（）：
front前移（ - -）后再将元素放入front
（2）addLast（）：
先将元素放入rear角标处，后让rear后移（++）
（3）removeFirst（）：
先将front处元素取出，再让front后移（++）
（4）removeLast（）：
先将（rear-1）处的元素取出，再让rear前移（- -）
（5）getFirst（） 返回front处的元素
（6）getLast（）返回rear左边的元素
代码：
文件夹遍历：
//文件夹遍历
public class DirectoryTraversal {
public static void main(String[] args) {
/*
* 只要队列不为空 则出队一个目录对象
* 将该目录对象展开 开始遍历 遇到文件则打印名称 遇到其他目录 则进队
* */
File dir = new File("C:\\Users\\32519\\Desktop\\DS");
ArrayQueue<File> queue = new ArrayQueue<>();
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 = 0; 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();
}
}
队列实现栈：
//队列实现栈
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);
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 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 String toString() {
if (isEmpty()) {
return "[]";
} else if (!queueA.isEmpty()) {
return queueA.toString();
} else {
return queueB.toString();
}
}
}
双端对列：
//双端对列
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];
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++;
}
@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++;
}
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 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);
}
return ret;
}
@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);
}
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;
}
}
}
这篇关于数据结构与算法（2）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
MQ底层原理资料详解：新手入门教程11-28
-
MQ项目开发资料详解：新手入门教程11-28
-
MQ项目开发资料详解：入门与初级用户指南11-28
-
MQ消息队列资料入门教程11-28
-
MQ消息队列资料：新手入门详解11-28
-
MQ消息中间件资料详解与应用教程11-28
-
MQ消息中间件资料入门教程11-28
-
MQ源码资料详解与入门教程11-28
-
MQ源码资料入门教程11-28
-
RocketMQ底层原理资料详解11-28
-
RocketMQ项目开发资料入门指南11-28
-
RocketMQ项目开发资料详解：新手入门与初级教程11-28
-
RocketMQ消息中间件资料入门教程11-28
-
RocketMQ源码资料入门教程11-28
-
RocketMQ源码资料入门教程11-28
栏目导航
