Notes:
Queue: (offer, poll, element)
A queue is a linear table that only allows insertion at one end and deletion at the other end.
——We call the end that is allowed to be deleted as the front and the end that is inserted as the rear
——A queue without any data elements is called an empty queue
——Queue is a First In Last Out linear table, called FIFO for short
——The queue itself is a linear table, and its data elements have linear relations, but it is a special linear table
——Queue insertion is called queue joining
——Delete queue, call out queue
Implementation: arrayqueue (the bottom layer can be implemented by ArrayList)
Application 1: folder listfile (1) if it is a directory, enter the queue
(2) if it is a file, output the file name
Circular queue: ArrayLoopQueue
(1) Define the Front and Rear pointers
Two pointers move with the data: when leaving the queue: Front++
When joining the team: Rear++
(2) When the end of the queue or the head of the queue pointer reaches the end of the queue, if you need to move back, you can point to the header again
Team full:( Rear+1)%n==Front (n: queue length )
Team air:( Rear+1)%n==Front
(3) Reserve a space without any elements, and the tail pointer always points to the null space.
Team air: Rear==Front
**· * * expansion and contraction capacity:
Traverse the elements in the data from the head pointer front, and receive the corresponding values from the head of the new array until front=rear.
Note: (1) there is a reserved space without elements, so make the capacity + 1 when creating a queue
(2)When shrinking, size The conditions met must be given data Length of-1
(3)Only when expanding or shrinking the capacity, it is necessary to consider adding 1 to the capacity at that time. In other cases, data The length of must be+1 Volume after Quantity can ensure the matching of length.
During capacity expansion, the new length is equal to the old length*n again－(n-1)
When shrinking, the new length is equal to the old length/n again+(n+1)
Dual ended queue Deque
It is a linear table with limited insert and delete operations at both ends of the table. It is a data structure with the properties of queue and stack
Empty judgment, full judgment, expansion and shrinkage are consistent with the circular queue
Unique methods:
(1)addFirst():
front Move forward( - -)Then put the element into front
(2)addLast():
First put the element at the rear corner mark, and then move the rear back (+ +)
(3)removeFirst():
First take out the element at the front, and then move the front back (+ +)
(4)removeLast():
First take out the element at (rear-1), and then move the rear forward (- -)
(5) getFirst() returns the element at front
(6) getLast() returns the element to the left of the rear
code:
Folder traversal:
//Folder traversal
public class DirectoryTraversal {
public static void main(String[] args) {
/*
* A directory object is dequeued as long as the queue is not empty
* Expand the directory object and start traversal. If a file is encountered, print the name. If another directory is encountered, enter the queue
* */
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);
}
}
}
}
}
Stack implementation column alignment:
//Stack implementation queue
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();
}
}
Queue implementation stack:
//Queue implementation stack
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);//Queue A
}
System.out.println(stack);
System.out.println(stack.pop());
System.out.println(stack);//Queue 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();
}
}
}
Two end to column:
//Double ended column
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;
}
}
}