美文网首页
数据结构之队列【数组,集合,栈,链表来实现】

数据结构之队列【数组,集合,栈,链表来实现】

作者: Owen270 | 来源:发表于2024-12-05 20:14 被阅读0次

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;
        }
    }

相关文章

  • 数据结构java描述

    接口 栈 队列 集合 并查集 映射 数组 链表 栈 数组实现 链表实现 队列 数组实现 链表实现 二分搜索树 集合...

  • 复习

    数据结构 数据结构 集合常见数据结构:集合,链表,队列,数组,栈,映射java中:List列表,Set集合,Map...

  • 常见的数据结构

    常见的数据结构有: 数组 链表单链表、双向链表、循环链表、双向循环链表、静态链表 栈顺序栈、链式栈 队列普通队列、...

  • ARTS-第三周

    Algorithm 这周实现了最基本的动态数据结构链表,并用数组和链表分别实现了栈和队列。 git代码地址 数组和...

  • Collection 总结

    Collection Java集合是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、数组、映射等...

  • Collection框架

    数据结构有: 数组、链表、栈、集合、队列、哈希表、树等 顶级抽象接口Collection 子接口分为List/...

  • 数据结构

    数据结构 队列&栈&链表&集合&hash表&树&图 队列 先进先出 栈 先进后出 链表 单向链表 双向链表 循环链...

  • 身为一个合格的java开发,这些java集合的知识你得知道,写的

    数据结构 数组 队列 链表 二叉树 集合 Collection List集合 List集合接口**的实现类(1) ...

  • Java集合干货系列-集合总体大纲

    前言 Java集合是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、数组、映射等。Java集合工...

  • Vector

    Java集合 Java集合是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、数组、映射等。Jav...

网友评论

      本文标题:数据结构之队列【数组,集合,栈,链表来实现】

      本文链接:https://www.haomeiwen.com/subject/utypsjtx.html