数据结构—自定义队列

Bertha 。 2023-10-12 08:03 72阅读 0赞

用链表创建队列

public class LinkQueue<E> implements Queue<E>{
        public class Node{
            public E e;
            public Node next;
    
            public Node(E e , Node next){
                this.e = e ;
                this.next = next;
            }
            public Node(E e){
                this.e = e;
                this.next = null;
            }
            public Node(){
                this(null,null);
            }
    
            @Override
            public String toString(){
                return e.toString();
            }
    
        }
        private Node head;
        private Node tail;
        private int size;
    
        public LinkQueue(){
            head = null;
            tail = null;
            size = 0;
        }
    
    
    
        @Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public E dequeue() {
            // 1.队列为空 即队首为空
            if(head == null){
                throw new IllegalArgumentException("队列为空");
            }
            Node node = head;
            head = head.next;
            node.next = null;   //将队首取出
            if(head == null) tail = null;
            size --;
            return node.e;
        }
    
        @Override
        public E getFront() {
            return null;
        }
    
        @Override
        public void enqueue(E e) {
         if (tail == null){  // 队列为空
             tail = new Node(e);
             head = tail;
         }else{
             Node node = new Node(e);
             tail.next = node;
             tail = node;
             size ++;
         }
        }
    }

用数组创建循环队列

需要注意的是：

a.尾指针一直指向null，即指向最后一个元素的后一个元素 （极大作用的维护循环队列的循环），这样来需要维护实际空间大小和需要创建、扩容的大小之间的关系

b.添加元素：先将需要添加的元素e 添加到·尾指针指向的数组data\[tail\] 中，然后tail指针继续+1；

c.判断是否需要扩容、缩容，由于tail指向最后一个元素的后一个位置，只需要在入队判断（tail+1）%（数组长度）是否会等于头指针 。

public class LoopQueue<E> implements Queue<E> {
    
        private E[] data;
    
        private int front ,tail;
    
        private int size;
    
        public LoopQueue(int capacity){
            data = (E[]) new Object[capacity+1];
            front = 0;
            tail = 0;
            size = 0;
        }
    
        public int getCapacity(){
            return data.length-1;
        }
        @Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return front == tail;  //
        }
    
        @Override
        public E dequeue() {
            if(isEmpty()){
                throw new IllegalArgumentException("无法出队");
            }
            E ret = data[front];
            data[front] = null;
            front = (front+1) % data.length;
            size --;
            if(size == getCapacity() / 4 && getCapacity() /2 !=0){
                resize(getCapacity()/2);
            }
            return ret;
        }
    
        @Override
        public E getFront() {
            return null;
        }
    
        @Override
        public void enqueue(E e) {
            /*if (tail+1 > data.length){
                tail = tail+1%data.length;
            }
            else
                tail++;
            data[tail] = e;
            size++;*/
            // 1。扩容
            if ((tail+1)%data.length == front){
                resize(getCapacity()*2);
            }
           data[tail] = e;
            tail = (tail+1)/data.length;
            size ++;
    
        }
    
        private void resize(int newCapacity) {
            E[] newData = (E[]) new Object[newCapacity+1];
            for (int i = 0 ; i < size ; i++){
                newData[i] = data[ (i+front) % data.length]; //data.length 和 size不相等 data.length 比size大一 tail指向队尾的后一个位置
            }
            data = newData;
            tail = size ;
            front = 0 ;
        }
    }

转载于:https://www.cnblogs.com/JTrun/p/11330676.html