队列的顺序/链式存储实现(Java版)

秒速五厘米 2022-11-20 09:40 133阅读 0赞

## 队列的定义 ##

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作， 而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。 进行插入操作的端称为入队，进行删除的操作成为出队。

## 队列的顺序存储实现 ##

package algorithm.datastructure.queue;
    
    /* * 队列 * 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作， * 而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。 * 进行插入操作的端称为入队，进行删除的操作成为出队 * * 顺序队列: * 采用连续的存储空间存储 */
    
    public class SeqQuque { 
    
        private int table[];//数组
        private int front;//队首下标
        private int rear;//队尾下标
        private int maxSize;//队列的容量
        private int length;//当前队列长度
        private int incrementCapacity;//扩容时增长容量
        private static final int QUEUE_DEFAULT_INIT_SIZE=10;//初始容量
        private static final int QUEUE_DEFAULT_INCREMENT_SIZE=5;//扩容时默认增长容量
        public SeqQuque(){ 
            this.maxSize=QUEUE_DEFAULT_INIT_SIZE;
            this.table=new int[maxSize];
            this.front=this.rear=0;
            this.incrementCapacity=QUEUE_DEFAULT_INCREMENT_SIZE;
        }
    
        public SeqQuque(int initialCapacity){ 
            this.maxSize=initialCapacity;
            this.table=new int[maxSize];
            this.front=this.rear=0;
            this.incrementCapacity=QUEUE_DEFAULT_INCREMENT_SIZE;
        }
    
        public SeqQuque(int initialCapacity,int incrementCapacity){ 
            this.maxSize=initialCapacity;
            this.table=new int[maxSize];
            this.front=this.rear=0;
            this.incrementCapacity=incrementCapacity;
        }
    
        //判断队列是否为空
    
        public Boolean isEmpty(){ 
            return front==rear;
        }
        //判断队列是否已满
        public Boolean isFull(){ 
            return length==maxSize;
    
        }
        //求队列长度
        public int length(){ 
            return length;
        }
        //表尾插入元素
        public void enQueue(int x){ 
            if (isFull()){ 
                ensureCapacity();
    
                table[rear++]=x;
    
                length++;
            } else{ 
                table[rear++]=x;
    
                length++;
            }
        }
        //表头删除元素
        public Integer deQueue(){ 
            if (isEmpty()){ 
                try { 
                    throw new Exception("队列空");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            } else { 
                length--;
                int x=table[front++];
    
               return x;
            }
            return null;
        }
    
        //获取队头元素
        public Integer getHead(){ 
            if (isEmpty()){ 
                try { 
                    throw new Exception("队列空");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            } else { 
                return table[front];
            }
            return null;
    
        }
        //清空队列
        public void clearQueue(){ 
            this.maxSize=QUEUE_DEFAULT_INIT_SIZE;
            this.table=new int[maxSize];
            this.front=this.rear=0;
            this.incrementCapacity=QUEUE_DEFAULT_INCREMENT_SIZE;
        }
    
    
        //扩容
        private void ensureCapacity() { 
            System.out.println("当前队列的容量为:"+maxSize+"，容量不足，扩容");
            maxSize=maxSize+incrementCapacity;
            int []newTable=new int[maxSize];
            for (int i=0;i<table.length;i++){ //将旧数组的元素移到新数组
                newTable[i]=table[i];
            }
            table=newTable;
            System.out.println("扩容成功，扩容后队列的新容量为:"+maxSize);
        }
    
    
    
    
        public static void main(String[] args) { 
    
            //测试
            SeqQuque seqQuque=new SeqQuque(1,1);
            seqQuque.enQueue(1);
            seqQuque.enQueue(2);
            seqQuque.enQueue(3);
            System.out.println(seqQuque.length());
            System.out.println(seqQuque.getHead());
            System.out.println(seqQuque.getHead());
            System.out.println(seqQuque.deQueue());
            System.out.println(seqQuque.deQueue());
            System.out.println(seqQuque.deQueue());
    
            seqQuque.clearQueue();
    
            //seqQuque.deQueue();
        }
    }

## 队列的链式存储实现 ##

package algorithm.datastructure.queue;
    
    
    /* * 队列 * 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作， * 而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。 * 进行插入操作的端称为入队，进行删除的操作成为出队 * 顺序队列: * 采用连非续的存储空间存储 * */
    
    public class LinkedQueue { 
    
        private Node front;//队头指针
        private Node rear;//队尾指针
        private Integer length;//当前队列长度
    
        private static class Node { 
            int data;
            Node next;
    
            public Node() { 
            }
    
            public Node(int data) { 
                this.data = data;
                this.next = null;
            }
    
            public Node(int data, Node next) { 
                this.data = data;
                this.next = next;
            }
        }
    
        //初始化
        public LinkedQueue() { 
            front = new Node();
            rear = front;
            front.next = null;
            length = 0;
        }
    
        //判断队列空
        public Boolean isEmpty() { 
            return front == rear;
        }
    
        //队尾插入元素
        public void enQueue(int x) { 
    
            Node newNode = new Node(x, null);
            rear.next = newNode;
            rear = newNode;
            length++;
        }
    
        //队首删除元素
        public Integer deQueue() { 
            if (isEmpty()) { 
                try { 
                    throw new Exception("队列空");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            } else { 
                Node x = front.next;
                front = front.next;
                length--;
                return x.data;
            }
            return null;
        }
    
    //获取队首元素
        public Integer getHead() { 
            if (isEmpty()) { 
                try { 
    
                    throw new Exception("队列空");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            } else { 
                return front.next.data;
            }
    
            return null;
    
        }
    
        //获取当前队列长度
        public int length() { 
            return length;
        }
    
        //清空队列
        public void clearQueue() { 
            front = new Node();
            rear = front;
            front.next = null;
            length = 0;
        }
    
        public static void main(String[] args) { 
            //测试
            LinkedQueue linkedQueue = new LinkedQueue();
            //System.out.println(linkedQueue.deQueue());
            linkedQueue.enQueue(6);
            linkedQueue.enQueue(2);
            linkedQueue.enQueue(3);
            System.out.println(linkedQueue.length());
            System.out.println(linkedQueue.getHead());
            System.out.println(linkedQueue.deQueue());
            System.out.println(linkedQueue.deQueue());
            System.out.println(linkedQueue.deQueue());
            //System.out.println(linkedQueue.deQueue());
            linkedQueue.clearQueue();
    
        }
    }