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）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
springboot项目无法注册到nacos-icode9专业技术文章分享07-02
-
结对编程到底难不难？答案在这里06-26
-
《2023版Java工程师》课程升级公告06-19
-
matplotlib作图不显示3D图，怎么办？06-15
-
03-Loki 日志监控06-15
-
04-让LLM理解知识 -Prompt06-15
-
做软件测试需要懂代码吗？06-05
-
14-ShardingSphere的分布式主键实现06-05
-
为什么以及如何要进行架构设计权衡？06-03
-
全网首发第二弹！软考2024年5月《软件设计师》真题+解析+答案！（11-20题）05-31
-
全网首发！软考2024年5月《软件设计师》真题+解析+答案！（21-30题）05-31
-
【Java】百万数据excel导出功能如何实现05-30
-
我们小公司，哪像华为一样，用得上IPD（集成产品开发）？05-30
-
java excel上传--poi05-30
-
安装笔记本应用商店的pycharm，再安排pandas等模块，说是没有打包工具?05-30
栏目导航
