数据结构之队列【数组，集合，栈，链表来实现】
2024-12-05 本文已影响0人
Owen270
1.队列实现 (先进先出)
- 用数组实现队列
public class Queue001 {
int[] a=new int[10];
int i=0;
//入队
public void in(int m){
a[i++]=m;
}
//出队，先进先出
public int out(){
int index=0;
int temp=a[0];//取数组的第一个元素出队
for(int j=1;j<i;j++){
a[j-1]=a[j];//把数组中剩余的元素前移一位
}
return temp;
}
}
- 用集合实现队列
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;
}
}
- 二个堆栈实现队列
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()){
if(stackA.size()>0){
return stackB.push(stackA.pop());//向让栈A中元素逐一出栈，并压入栈B中
}
}
return stackB.pop();
}
}
- 单链表实现队列
public class Queue004<V> {
private Node<V> head;
private Node<V> tail;
private int size;
public Queue004(){
tail = head = new Node<V>(null);//初始化头尾节点
size=0;
}
//入队 添加元素
public void offer(V value){
Node<V> curNode=new Node<V>(value);
//初始状态下，head=tail等价于head=tail.next=curNode
tail.next=curNode;//1.只需要保证尾部节点的next指向curNode即可，
tail=curNode;//2.尾部节点变更为当前节点
}
//出队 获取元素，头部节点下移
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队列实现（单链表）
- MessageQueue.enqueueMessage() 入队
//入队
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结点
boolean needWake;
if (p == null || when == 0 || when < p.when) {
msg.next = p;
mMessages = msg; //第一个节点保存为head结点
needWake = mBlocked;
} else { //head节点p不等于null
needWake = mBlocked && p.target == null && msg.isAsynchronous();
Message prev;
for (;;) { //死循环，从头结点开始遍历
prev = p;//prev保存每一次要遍历的节点，最终prev会变成tail尾部节点
p = p.next;//遍历
if (p == null || when < p.when) {//当到最后一个节点 p时，p.next必然为null
break;
}
if (needWake && p.isAsynchronous()) {
needWake = false;
}
}
msg.next = p; //此时p=null
prev.next = msg;//prev节点变成了tail节点，
}
// We can assume mPtr != 0 because mQuitting is false.
if (needWake) {
nativeWake(mPtr);
}
}
return true;
}
- MessageQueue.next() 出队
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节点
//target就是handler,过滤掉没有handler回调的msg，
if (msg != null && msg.target == null) {
do {
prevMsg = msg;
msg = msg.next;
} while (msg != null && !msg.isAsynchronous());
}
//直到msg的target!=null时
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;
}
}
