隊(duì)列(Queue)
隊(duì)列（Queue）是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒(méi)有元素時(shí)，稱為空隊(duì)列。
隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素成為出隊(duì)。因?yàn)殛?duì)列只允許在一段插入，在另一端刪除，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又稱為先進(jìn)先出（FIFO—first in first out）線性表。
本文圖片均來(lái)自網(wǎng)絡(luò)
隊(duì)列示意圖
隊(duì)列(Queue)和棧(Stack)一樣也有鏈表和數(shù)組兩種實(shí)現(xiàn)。
鏈表實(shí)現(xiàn)
鏈表
空隊(duì)列
入列代碼表示：
public void enqueue(T item) {
Node oldLast = last;
last = new Node();
last.item = item;
if (isEmpty()) {
top = last;
} else {
oldLast.next = last;
}
number++;
}
出列代碼表示：
public T dequeue() {
T temp = top.item;
top = top.next;
number--;
if (isEmpty())
last = null;
return temp;
}
完整的偽代碼如下：
/**
* Created by zzw on 2017/6/28.
* Version:
* Des:
*/
public class MyQuery<T> {
private Node top;
private Node last;
private int number;
class Node {
T item;
Node next;
}
public T dequeue() {
T temp = top.item;
top = top.next;
number--;
if (isEmpty())
last = null;
return temp;
}
public void enqueue(T item) {
Node oldLast = last;
last = new Node();
last.item = item;
if (isEmpty()) {
top = last;
} else {
oldLast.next = last;
}
number++;
}
private boolean isEmpty() {
return size() == 0;
}
private int size() {
return number;
}
}
圖示如下：
使用數(shù)組實(shí)現(xiàn)的稱為順序儲(chǔ)存，這種方式出隊(duì)復(fù)雜度高并且容易假溢出。
入列
public E enqueue(E item) {
addElement(item);
return item;
}
出列
public E dequeue() {
if (size() <= front)
return null;
E obj = elementAt(front);
setElementAt(null, front);
front++;
return obj;
}
完整偽代碼(繼承Vector實(shí)現(xiàn)):
/**
* Created by zzw on 2017/6/28.
* Version:
* Des:
*/
public class MyQuery<E> extends Vector<E> {
int front = 0;
public E enqueue(E item) {
addElement(item);
return item;
}
public E dequeue() {
if (size() <= front)
return null;
E obj = elementAt(front);
setElementAt(null, front);
front++;
return obj;
}
}
如下圖所示：
看看隊(duì)列在Android里面的使用
Handle消息隊(duì)列
使用Handle的時(shí)候都要使用Looper.loop()
/**
* Run the message queue in this thread. Be sure to call
* {@link #quit()} to end the loop.
*/
public static void loop() {
final Looper me = myLooper();
if (me == null) {
throw new RuntimeException("No Looper; Looper.prepare() wasn't called on this thread.");
}
final MessageQueue queue = me.mQueue;
// Make sure the identity of this thread is that of the local process,
// and keep track of what that identity token actually is.
Binder.clearCallingIdentity();
final long ident = Binder.clearCallingIdentity();
for (;;) {
Message msg = queue.next(); // might block
if (msg == null) {
// No message indicates that the message queue is quitting.
return;
}
// This must be in a local variable, in case a UI event sets the logger
final Printer logging = me.mLogging;
if (logging != null) {
logging.println(">>>>> Dispatching to " + msg.target + " " +
msg.callback + ": " + msg.what);
}
final long traceTag = me.mTraceTag;
if (traceTag != 0 && Trace.isTagEnabled(traceTag)) {
Trace.traceBegin(traceTag, msg.target.getTraceName(msg));
}
try {
msg.target.dispatchMessage(msg);
} finally {
if (traceTag != 0) {
Trace.traceEnd(traceTag);
}
}
if (logging != null) {
logging.println("<<<<< Finished to " + msg.target + " " + msg.callback);
}
// Make sure that during the course of dispatching the
// identity of the thread wasn't corrupted.
final long newIdent = Binder.clearCallingIdentity();
if (ident != newIdent) {
Log.wtf(TAG, "Thread identity changed from 0x"
+ Long.toHexString(ident) + " to 0x"
+ Long.toHexString(newIdent) + " while dispatching to "
+ msg.target.getClass().getName() + " "
+ msg.callback + " what=" + msg.what);
}
msg.recycleUnchecked();
}
}
//MessageQueue中
Message next() {
// Return here if the message loop has already quit and been disposed.
// This can happen if the application tries to restart a looper after quit
// which is not supported.
final long ptr = mPtr;
if (ptr == 0) {
return null;
}
int pendingIdleHandlerCount = -1; // -1 only during first iteration
int nextPollTimeoutMillis = 0;
for (;;) {
if (nextPollTimeoutMillis != 0) {
Binder.flushPendingCommands();
}
nativePollOnce(ptr, nextPollTimeoutMillis);
synchronized (this) {
// Try to retrieve the next message. Return if found.
final long now = SystemClock.uptimeMillis();
Message prevMsg = null;
Message msg = mMessages;
if (msg != null && msg.target == null) {
// Stalled by a barrier. Find the next asynchronous message in the queue.
do {
prevMsg = msg;
msg = msg.next;
} while (msg != null && !msg.isAsynchronous());
}
if (msg != null) {
if (now < msg.when) {
// Next message is not ready. Set a timeout to wake up when it is ready.
nextPollTimeoutMillis = (int) Math.min(msg.when - now, Integer.MAX_VALUE);
} else {
// Got a message.
mBlocked = false;
if (prevMsg != null) {
prevMsg.next = msg.next;
} else {
mMessages = msg.next;
}
msg.next = null;
if (DEBUG) Log.v(TAG, "Returning message: " + msg);
msg.markInUse();
return msg;
}
} else {
// No more messages.
nextPollTimeoutMillis = -1;
}
// Process the quit message now that all pending messages have been handled.
if (mQuitting) {
dispose();
return null;
}
// If first time idle, then get the number of idlers to run.
// Idle handles only run if the queue is empty or if the first message
// in the queue (possibly a barrier) is due to be handled in the future.
if (pendingIdleHandlerCount < 0
&& (mMessages == null || now < mMessages.when)) {
pendingIdleHandlerCount = mIdleHandlers.size();
}
if (pendingIdleHandlerCount <= 0) {
// No idle handlers to run. Loop and wait some more.
mBlocked = true;
continue;
}
if (mPendingIdleHandlers == null) {
mPendingIdleHandlers = new IdleHandler[Math.max(pendingIdleHandlerCount, 4)];
}
mPendingIdleHandlers = mIdleHandlers.toArray(mPendingIdleHandlers);
}
// Run the idle handlers.
// We only ever reach this code block during the first iteration.
for (int i = 0; i < pendingIdleHandlerCount; i++) {
final IdleHandler idler = mPendingIdleHandlers[i];
mPendingIdleHandlers[i] = null; // release the reference to the handler
boolean keep = false;
try {
keep = idler.queueIdle();
} catch (Throwable t) {
Log.wtf(TAG, "IdleHandler threw exception", t);
}
if (!keep) {
synchronized (this) {
mIdleHandlers.remove(idler);
}
}
}
// Reset the idle handler count to 0 so we do not run them again.
pendingIdleHandlerCount = 0;
// While calling an idle handler, a new message could have been delivered
// so go back and look again for a pending message without waiting.
nextPollTimeoutMillis = 0;
}
}
Handle 異步處理中用來(lái)存放Message對(duì)象的數(shù)據(jù)結(jié)構(gòu)，按照“先進(jìn)先出”的原則存放消息。存放并非實(shí)際意義的保存，而是將Message對(duì)象以鏈表的方式串聯(lián)起來(lái)的。MessageQueue對(duì)象不需要我們自己創(chuàng)建，而是有Looper對(duì)象對(duì)其進(jìn)行管理，一個(gè)線程最多只可以擁有一個(gè)MessageQueue。在Lopper方法中：出現(xiàn)了一個(gè)死循環(huán)，從隊(duì)列中不斷的取出message，執(zhí)行msg.target.dispatchMessage(msg);
EventBus
在EventBus里面中，將消息封裝成一個(gè)PendingPost
final class PendingPost {
private final static List<PendingPost> pendingPostPool = new ArrayList<PendingPost>();
Object event;
Subscription subscription;
PendingPost next;
private PendingPost(Object event, Subscription subscription) {
this.event = event;
this.subscription = subscription;
}
}
在使用隊(duì)列PendingPostQueue進(jìn)行管理
final class PendingPostQueue {
private PendingPost head;
private PendingPost tail;
synchronized void enqueue(PendingPost pendingPost) {
if (pendingPost == null) {
throw new NullPointerException("null cannot be enqueued");
}
if (tail != null) {
tail.next = pendingPost;
tail = pendingPost;
} else if (head == null) {
head = tail = pendingPost;
} else {
throw new IllegalStateException("Head present, but no tail");
}
notifyAll();
}
synchronized PendingPost poll() {
PendingPost pendingPost = head;
if (head != null) {
head = head.next;
if (head == null) {
tail = null;
}
}
return pendingPost;
}
synchronized PendingPost poll(int maxMillisToWait) throws InterruptedException {
if (head == null) {
wait(maxMillisToWait);
}
return poll();
}
}
Handler發(fā)送消息
final class HandlerPoster extends Handler {
private final PendingPostQueue queue;
private final int maxMillisInsideHandleMessage;
private final EventBus eventBus;
private boolean handlerActive;
HandlerPoster(EventBus eventBus, Looper looper, int maxMillisInsideHandleMessage) {
super(looper);
this.eventBus = eventBus;
this.maxMillisInsideHandleMessage = maxMillisInsideHandleMessage;
queue = new PendingPostQueue();
}
void enqueue(Subscription subscription, Object event) {
PendingPost pendingPost = PendingPost.obtainPendingPost(subscription, event);
synchronized (this) {
queue.enqueue(pendingPost);
if (!handlerActive) {
handlerActive = true;
if (!sendMessage(obtainMessage())) {
throw new EventBusException("Could not send handler message");
}
}
}
}
@Override
public void handleMessage(Message msg) {
boolean rescheduled = false;
try {
long started = SystemClock.uptimeMillis();
while (true) {
PendingPost pendingPost = queue.poll();
if (pendingPost == null) {
synchronized (this) {
// Check again, this time in synchronized
pendingPost = queue.poll();
if (pendingPost == null) {
handlerActive = false;
return;
}
}
}
eventBus.invokeSubscriber(pendingPost);
long timeInMethod = SystemClock.uptimeMillis() - started;
if (timeInMethod >= maxMillisInsideHandleMessage) {
if (!sendMessage(obtainMessage())) {
throw new EventBusException("Could not send handler message");
}
rescheduled = true;
return;
}
}
} finally {
handlerActive = rescheduled;
}
}
}
這里面有個(gè)死循環(huán)，不斷的取出event，通過(guò)eventBus.invokeSubscriber(pendingPost);執(zhí)行相關(guān)函數(shù)。
相關(guān)參考鏈接：
淺談算法和數(shù)據(jù)結(jié)構(gòu): 一 棧和隊(duì)列
隊(duì)列在Android中的使用
水平有限，文中有什么不對(duì)或者有什么建議希望大家能夠指出，謝謝！
