public class Queue001 {
int[] a=new int[10];
int i=0;
//入隊(duì)
public void in(int m){
a[i++]=m;
}
//出隊(duì)，先進(jìn)先出
public int out(){
int index=0;
int temp=a[0];//取數(shù)組的第一個(gè)元素出隊(duì)
for(int j=1;j<i;j++){
a[j-1]=a[j];//把數(shù)組中剩余的元素前移一位
}
return temp;
}
}
用集合實(shí)現(xiàn)隊(duì)列
public class Queue002 {
List<Integer> list=new ArrayList<>();
int index=0;
public void in(int n){
list.add(n);
index++;
}
public int out(){
if(!list.isEmpty()){
index--;
return list.remove(0);//移除并返回 list[0]
}
return -1;
}
}
二個(gè)堆棧實(shí)現(xiàn)隊(duì)列
public class Queue003 {
Stack<Integer> stackA=new Stack<Integer>();
Stack<Integer> stackB=new Stack<Integer>();
public void in(int n){
stackA.push(n);
}
public int out(){
if(stackB.isEmpty()){ //如果
while(!stackA.isEmpty()){ //把棧A中元素逐一出棧广辰，并壓入棧B中
return stackB.push(stackA.pop());//向讓棧A中元素逐一出棧暇矫，并壓入棧B中
}
}
return stackB.pop();
}
}
單鏈表實(shí)現(xiàn)隊(duì)列
public class Queue004<V> {
private Node<V> head;
private Node<V> tail;
private int size;
public Queue004(){
tail = head = new Node<V>(null);//初始化頭尾節(jié)點(diǎn)
size=0;
}
//入隊(duì) 添加元素
public void offer(V value){
Node<V> curNode=new Node<V>(value);
//初始狀態(tài)下，head=tail等價(jià)于head=tail.next=curNode
tail.next=curNode;//1.只需要保證尾部節(jié)點(diǎn)的next指向curNode即可择吊，
tail=curNode;//2.尾部節(jié)點(diǎn)變更為當(dāng)前節(jié)點(diǎn)
}
//出隊(duì) 獲取元素李根，頭部節(jié)點(diǎn)下移
public V poll(){
V temp=null;
if(head!=null){
temp=head.value;
head=head.next;
size--;
}
if(head==null){
head=tail=null;
}
return temp;
}
public class Node<V>{
public V value;
public Node<V> next;
public Node(V v){
this.value=v;
next=null;
}
}
}
2.MessageQueue隊(duì)列實(shí)現(xiàn)（單鏈表）
MessageQueue.enqueueMessage() 入隊(duì)
//入隊(duì)
boolean enqueueMessage(Message msg, long when) {
if (msg.target == null) {
throw new IllegalArgumentException("Message must have a target.");
}
synchronized (this) {
if (msg.isInUse()) {
throw new IllegalStateException(msg + " This message is already in use.");
}
if (mQuitting) {
IllegalStateException e = new IllegalStateException(
msg.target + " sending message to a Handler on a dead thread");
Log.w(TAG, e.getMessage(), e);
msg.recycle();
return false;
}
msg.markInUse();
msg.when = when;
Message p = mMessages; //head結(jié)點(diǎn)
boolean needWake;
if (p == null || when == 0 || when < p.when) {
msg.next = p;
mMessages = msg; //第一個(gè)節(jié)點(diǎn)保存為head結(jié)點(diǎn)
needWake = mBlocked;
} else { //head節(jié)點(diǎn)p不等于null
needWake = mBlocked && p.target == null && msg.isAsynchronous();
Message prev;
for (;;) { //死循環(huán)，從頭結(jié)點(diǎn)開始遍歷
prev = p;//prev保存每一次要遍歷的節(jié)點(diǎn)几睛，最終prev會(huì)變成tail尾部節(jié)點(diǎn)
p = p.next;//遍歷
if (p == null || when < p.when) {//當(dāng)?shù)阶詈笠粋€(gè)節(jié)點(diǎn) p時(shí)房轿，p.next必然為null
break;
}
if (needWake && p.isAsynchronous()) {
needWake = false;
}
}
msg.next = p; //此時(shí)p=null
prev.next = msg;//prev節(jié)點(diǎn)變成了tail節(jié)點(diǎn)，
}
// We can assume mPtr != 0 because mQuitting is false.
if (needWake) {
nativeWake(mPtr);
}
}
return true;
}
MessageQueue.next() 出隊(duì)
Message next() {
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) {
final long now = SystemClock.uptimeMillis();
Message prevMsg = null;
Message msg = mMessages;//head節(jié)點(diǎn)
//target就是handler,過濾掉沒有handler回調(diào)的msg所森，
if (msg != null && msg.target == null) {
do {
prevMsg = msg;
msg = msg.next;
} while (msg != null && !msg.isAsynchronous());
}
//直到msg的target!=null時(shí)
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; //返回target!=null的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);
}
}
}
pendingIdleHandlerCount = 0;
nextPollTimeoutMillis = 0;
}
}
