风也温柔

计算机科学知识库

循环队列的数据结构-Java循环队列的实现

  队列是一种特殊的线性表循环队列数据结构循环队列的数据结构-Java循环队列的实现,其特殊性体现在只允许在表尾插入元素,表头删除元素。它具有先进先进的特性。插入操作称为入队,删除操作称为出队。进行插入操作的端称为队尾rear,进行删除操作的端称为队头front。

  在实际使用中,由于顺序队列经常会因数组下标越界出现”假溢出“问题,所以除了一些简单应用之外,真正实用的队列是循环队列。

  顺序循环队列_循环队列是_循环队列的数据结构

  队空状态: front=rear=0

  Java循环队列的实现

  队满状态: front=(rear+1)%

  Java循环队列的实现

  代码如下:

   public class CircleSqQueue {

        
        private Object[] queueElement;
        private int front;
        private int rear;
        public CircleSqQueue(int maxSize)
        {
            queueElement=new Object[maxSize];
            front=rear=0;
        }
        //清空
        public void clear()
        {
            front=rear=0;
        }
        //判断是否为空
        public boolean isEmpty()
        {
            return front==rear;
        }
        //长度
        public int length()
        {
            return (rear-front+queueElement.length)%queueElement.length;
        }
        //队首
        public Object peek()
        {
            if(front==rear)
                return null;
            else
                return queueElement[front];
        }
        //入队
        public void offer(Object x) throws Exception
        {
            if((rear+1)%queueElement.length==front)
            {
                throw new Exception("队列已满!");
            }
            else
            {
                queueElement[rear]=x;
            }
            rear=(rear+1)%queueElement.length;
        }
        //出队
        public Object poll()
        {
            if(front==rear)
                return null;
            else
            {
                Object obj=queueElement[front];
                front=(front+1)%queueElement.length;
                return obj;
            }
        }
        //打印
        public void display()
        {
            if(front!=rear)
            {
                for(int i=front; i!=rear; i=(i+1)%queueElement.length)
                {
                    System.out.print(queueElement[i].toString()+" ");
                }
                System.out.println();
            }
        }
        public static void main(String[] args) throws Exception
        {
            CircleSqQueue queue=new CircleSqQueue(30);
            queue.offer(3);
            queue.offer(4);
            queue.offer(5);
            System.out.print("栈中元素: ");
            queue.display();
            System.out.println("栈中元素个数: "+queue.length());
            int top=(int)queue.peek();
            System.out.println("栈顶: "+top);
            System.out.print("出队后: ");
            queue.poll();
            queue.display();
        }

  运行结果:

  ​

  可以看到,当空间容量为时循环队列的数据结构,最多只允许存放-1个数据元素。这样可以解决循环队列的堆空、堆满的判断问题。(判空为front=rear,判满为front=(rear+1)%)

  文章来源:http://www.toutiao.com/a6822570311221772804/