Visible data structure of the Android version of the queue article

Zero, preface,

1. In the real world, we pay more attention to first come, first come, first come, first wait in line, first buy tickets, so that there is order, after all, we are not so patient as computers

2. Queue structure can be used to simulate and solve things similar to life, such as message sending with queue maintenance is very appropriate 3. The queue is like buying tickets at the zoo. First deal with the head of the queue. When new people come, wait in the back. Another interesting type of queue is circular queue, which is due to the difficulty of array header operation, thus changing the idea that arrays can also implement queue structure very well, which will be analyzed in detail later 5. I hope you can and I at Github together to witness: the birth and growth of DS4Android, welcome to star

1. The operation effect of the final realization of queue:

An array implements a common queue:

The blue area is the array. See: Initialize four Spaces. If there is not enough space, expand it

Linked list to implement common queue:

2. Brief introduction to queue structure:

A queue is a linear data structure: tail add, head out first-in, first-out FIFO operation: enqueue enter the queue dequeue exit the queue getFront View the first element in the queueCopy the code

1. Queue interface

The troops and horses have not moved, the food and grass first, the interface is easy to handle affairs.

/** * Author: Zhang Feng Jiete Lie * Time: 2018/8/17 0017:15:57 * Email: [email protected] * Description: Public interface IQueue<T> {/** * join the queue * @param el element */ void enqueue(T el); /** * dequeue * @return element */ T dequeue(); /** * getFront(); /** * getFront(); /** * Get the number of elements in the queue * @return number of elements */ int getSize(); /** * is null * @return is null */ Boolean isEmpty(); }Copy the code

Two, the array of ordinary queue implementation

The array implementation of the ordinary queue —- performance is very poor, then use the array to implement circular queue to optimize

Why would it be bad, because the tail add and the head remove, there’s always one that’s going to make everybody move, and then it’s going to be optimized with an array of circular queues

/** * Author: Zhang Feng Jiete Lie * Time: 2018/8/17 0017:15:57 * Email: [email protected] * Description: */ public class implements IQueue<E> {private ArrayChart<E> array; private ArrayChart<E> array; private ArrayChart<E> array; private ArrayChart<E> array; private ArrayChart<E> array; Public ArrayChartQueue(int capacity) {this.array = new ArrayChart<>(capacity); } public ArrayChartQueue() { this.array = new ArrayChart<>(); } @Override public void enqueue(E el) { array.add(el); } @Override public E dequeue() { return array.remove(0); } @Override public E front() { return array.get(0); } @Override public int size() { return array.size(); } @Override public boolean isEmpty() { return array.isEmpty(); }}Copy the code

2. Insert demo of array ordinary queue:

Since the implementation is based on an array, everything is based on an array

An initial array of four sizes, like reserving four chairs at a reception, and then adding chairs when the chairs are full

3. View the first element of the array of ordinary queue demo:

4. Array ordinary queue removal demo:

Array table structure removes header… The Root of all evil, do not use it, for demonstration only! This is for demonstration only! This is for demonstration only!!

Array table structure removes header… The Root of all evil, do not use it, for demonstration only! This is for demonstration only! This is for demonstration only!!

Circular queue

Array-based implementations of the queue will move the entire queue when fetched at the head of the queue, which will be inefficient

But zhuang zai my large array, can not even make a small queue, after which also have the face to stand on the throne… So there’s a circular queue. When you talk about a loop, you have a circle in your head. As long as it’s periodic, it’s a cycle, and it’s too narrow to think of it as a cycle

1. The idea of circular queue implementation:

Don't just want to know the line and the first is that, well, I come, maintain the give you not to go Note: the advantage of maintaining the party and the team first, insert and delete head was fixed, and array as a whole does not move, but mark was moving new added element, is back of the table, not enough capacity. The characteristics of a circular queue are as follows: if the queue is empty, 'end of the queue == head of the queue'; if the queue is full: '(end of the queue +1)% Array length == head of the queue' a circular queue makes the first position of the queue unavailable.Copy the code

/** * Author: Zhang Feng Jiete Lie * Time: 2018/8/17 0017:16:03 * Email: [email protected] * Description: */ public class ArrayLoopQueue<T> implements IQueue<T> {private T[] data; // Private int head; // Private int tail; // Private int size; Public ArrayLoopQueue() {// The default size is 8. } public ArrayLoopQueue(int capacity) {// +1 data = (T[]) new Object[capacity +1]; head = 0; tail = 0; size = 0; } @override public void enqueue(T el) {if (isFull()) {// Grow (capacity() * 2); } data[tail] = el; ----- tail = (tail + 1) % data.length; size++; } @Override public T dequeue() { if (isEmpty()) { throw new IllegalArgumentException("MakeSure it's not an empty } T ret  = data[head]; data[head] = null; ----- head = (head + 1) % data.length; size--; If (size == capacity() / 4 && capacity() / 2! = 0 && size > 4) { grow(capacity() / 2); } return ret; } @Override public T front() { if (isEmpty()) { throw new IllegalArgumentException("MakeSure it's not an empty } return data[head]; } /** * Expand/shrink capacity ** @param newCapacity New capacity */ private void grow(int newCapacity) {T[] newData = (T[]) new Object[newCapacity + 1]; for (int i = 0; i < size; NewData [I] = data[(I + head) % data.length]; } data = newData; head = 0; tail = size; } public int capacity() {return data.length-1;} public int capacity() {return data.length-1; } /** * @override public int size() {return size; } /** * is null ** @override public Boolean isEmpty() {return head == tail; } /** * Is the queue full ** @return is the queue full */ private Boolean isFull() {// return (tail + 1) % data.length == when the next position of tail is equal to head head; }}Copy the code

Four, the single list type implementation queue structure

The list and the queue are natural match, the list of the head to delete, the head to get quickly, but to add the tail to get the tail, need to traverse once, not good

However, the first identification can be maintained, so that the end of the line is also easy to obtain. (Of course you can also use a double linked list… The comment is very clear, look at the code, or debug walk a wave, I don’t need to repeat

/** * Author: Zhang Feng Jiete Lie * Time: 2018/8/17 0017:22:50 * Email: [email protected] * Description: */ public class SingleLinkedQueue<T> implements IQueue<T> {private Node head; // Head Node private Node tail; Private int size; Public SingleLinkedQueue() {head = null; tail = null; size = 0; } @override public void enqueue(T el) {// Join the queue // If the queue is empty, the queue is empty. Because tail always points to the last non-empty node. if (tail == null) { tail = new Node(null, el); // Initialize head = tail; } else { tail.next = new Node(null, el); // tail = tail.next; // update the end of the team} size++; } @override public T dequeue() {if (isEmpty()) throw new IllegalArgumentException("MakeSure it's not an empty queue"); Node targetNode = head; // I'm the boss. Head = head.next; // I am the second child, but I am going to usurp the throne... Targetnode. next = null; // The former boss left.... If (head == null) {// if the head node is null tail = null; } size--; return targetNode.el; } @Override public T front() { if (isEmpty()) throw new IllegalArgumentException("MakeSure it's not an empty queue"); return head.el; } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } private class Node { private T el; Private Node next; Private Node(Node next, T el) {this.el = el; // private Node(Node next, T el) {this.el = el; // private Node(Node next, T el) {this.el = el; this.next = next; }}}Copy the code

Five, the summary

1. Array ordinary queue: ArrayChartQueue test

2. Array Ring Queue: ArrayLoopQueue test

Methods \ | | 1000 times, 10000 times times | | | 10 w to 100 w – 1000 | — – | — – | — – | — – | — – | — – | the enqueue 0.0019 seconds 0.0004 seconds | | | | | 0.05414 seconds, 0.6896 seconds to 0.01775 seconds 0.0021 seconds 0.0005 seconds dequeu | | | | | 0.0360 seconds, 0.3327 seconds to 0.0091 seconds

3. Linked list queue: SingleLinkedStack test

Visible circular queue is still pretty good, strong zai, I big array!

Array ordinary queue, just get to know it… Don’t use it. Comparing an array ring queue with a list queue is the same as comparing an array with a list

Further updates in this series link collection :(dynamic updates)

• Visible data structures: the introduction to the Android version
• Array Tables for Android (Data Structures)
• Android Array Table (View Section)
• Visible data structure Android version of the single linked list
• Visible data structure Android version of the double Linked list
• Visible data structure stack for Android version
• Visible data structure of the Android version of the queue article
• Visible data structure Android version of the binary search tree
• More data structures – more on that later

Postscript: Jie wen standard

2. Growth records and errata of this paper

3. More about me

4. A statement

1—- This article is originally written by Zhang Fengjie, please note if reproduced

2—- welcome the majority of programming enthusiasts to communicate with each other 3—- personal ability is limited, if there is something wrong welcome to criticize and testify, must be humble to correct 4—- see here, I thank you here for your love and support