队列Queue的实现

墨蓝 2022-05-30 02:09 152阅读 0赞

> 队列：先进先出  
> 两种实现方式：  
> 1.利用数组  
> 2.链式存储

需要两个变量指向队头front和队尾rear，当入队时，队尾后移；出队时，队头后移  
使用数组实现，当我们入队至数组满，然后出队至数组空，此时虽然数组为空，但是却不能再入队了，因为队尾rear已经指向了数组的最后一个索引位置。那么如何充分利用数组呢？  
通过一定的计算操作使得数组虚拟为环形的数组

package dream.linearlist.queue;
    
    /** * 队列：底层用数组实现 * 规定队列使用数组的n-1个空间 */
    public class ArrQueue { 
        private int front,rear;
        private Object[] queue;
        private int maxSize;
        public ArrQueue(int maxSize){
            this.maxSize = maxSize;
            queue = new Object[maxSize];
        }
        public boolean isEmpty(){
            return front == rear;
        }
        public boolean isFull(){
            return (rear+1)%maxSize == front;
        }
        public void addQ(Object o){
            if((rear + 1)% maxSize == front){
                System.out.println("队列已满，不能再入列...");
                return;
            }
            rear = (rear + 1) % maxSize;
            queue[rear] = o;
        }
        public Object deleteQ(){
            if(front == rear){
                System.out.println("队列为空，不能再出列...");
                return null;
            }
            front = (front + 1) % maxSize;
            return queue[front];
        }
        public void display(){
            for(int i = front + 1;i <= rear || i < (rear + 1) % maxSize;i ++){
                System.out.print(queue[i]+" ");
            }
            System.out.println();
        }
        public static void main(String[] args){
            ArrQueue aq = new ArrQueue(6);
            aq.addQ(2);
            aq.addQ(3);
            aq.addQ(4);
            aq.addQ(5);
            aq.deleteQ();
            aq.display();
            System.out.println(aq.isEmpty());
        }
    }

链表可谓是队列的最佳实现结构，因为链表没有长度的限制。

package dream.linearlist.queue;
    
    /** * 队列：使用链表实现 */
    class Node{
        Object data;
        Node next;
        public Node(Node next,Object data){
            this.next = next;
            this.data = data;
        }
        public Node(Object data){
            this(null,data);
        }
        public Node(){
            this(null,null);
        }
    }
    public class LinkQueue { 
        private Node front;
        private Node rear;
        public LinkQueue(){
            front = rear = null;
        }
        public boolean isEmpty(){
            return front == null;
        }
        public void addQ(Object o){
            Node newNode = new Node(o);
            //如果是空队列，头和尾均指向新节点
            if(front == null){
                front = rear = newNode;
                return;
            }
            //否则新节点增加至尾指针后，同时尾指针后移，指向新增的节点
            rear.next = newNode;
            rear = newNode;
        }
        public Object deleteQ(){
            //如果队列为空
            if(front == null){
                System.out.println("队列为空，不能再出列...");
                return null;
            }
            //如果队列只有一个元素
            Node curr = front;
            if(front == rear && rear != null){
                front = rear = null;
            }
            front = front.next;
            return curr.data;
        }
        public void display(){
            Node tem = front;
            while(tem != rear){
                System.out.print(tem.data+" ");
                tem = tem.next;
            }
            System.out.println(rear.data);
        }
        public static void main(String[] args){
            LinkQueue lq = new LinkQueue();
            lq.addQ(2);
            lq.addQ(3);
            lq.addQ(4);
            lq.addQ(5);
            lq.deleteQ();
            lq.display();
            System.out.println(lq.isEmpty());
        }
    }