数据结构——队列的使用

ゝ一纸荒年。 2022-07-17 04:09 145阅读 0赞

## 队列（Quene）是一种数据结构，与栈不同的是先进先出（FIFO）,最先进去的数据最先出来，而栈是一种（LIFO）。quene结构在现实生活中很常见，例如可以用Quene模拟人们在银行里排队，打印机打印文件，飞机等待起飞，互联网上数据包的发送等。 ##

## 与stack一样，Quene也有一套自己的操作。插入队列（add、insert），删除（remove、delete）等。Quene有一个tail与head。通常情况add操作是在tail后面添加元素或者数据，而remove操作是在head（队列的头部进行删除数据）。通常Quene有Peek（查看）、add、remove操作。在add数据之前需要提前判断Quene isFull，在remove数据之前需要判断Quene isEmpty。这些都是保证Quene操作安全稳定的措施。 ##

## **循环队列与缓冲环** ##

## 当向队列中不断从对尾（tail）添加数据时，tail指针不断上移（可以理解为向地址增大的方向的移动）。如果队列空间开辟很小，那么添加较少数数据tail指针就到了顶端。之后若是不及时优化处理就会使队列效率很低。因此采用循环队列或者缓冲环能够解决这一问题，缓冲环不仅在应用层使用广泛，特别是通信或者数据传输时使用方便。 ##

![这里写图片描述][20160831101615916]

## **环绕式处理** ##

## 为了避免队列不满却不能插入新数据的问题，可以让tail指针绕回到数组开始的位置。当删除数据项时可以让对头指针head也进行回绕，但是这样一来可能会形成“队列序列折断”现象。不过再继续下去就会恢复到head指针在tail指针下面的情况。在程序设计中表现为：在add数据项之前进行判断isFull，若true则可以使tail=-1；（回到初始状态），删除数据项之前判断isEmpty，若true则可以使head=0。 ##

class QueneDemo
    {
        private int n;
        private int nItem=0;
        private int head=0;
        private int tail=-1;
        int[] value=null;
        public QueneDemo(int n)
        {
            value=new int[n];
            this.n=n;
        }
        public void add(int data)
        {
            if(tail==n-1)
            {
                tail=-1;
            }
            value[++tail]=data;
            nItem++;
        }
        public int remove()
        {
            int temp=value[head++];
            if(head==n)
            {
                head=0;
            }
            nItem--;
            return temp;
    
        }
        public boolean isEmpty()
        {
            return (nItem==0);
    
        }
        public boolean isFull()
        {
            return (nItem==n);
        }
        public void peek()
        {
            System.out.println(value[head]); 
        }
    }

## 测试类： ##

public class QueneApp {
        
    
        /**
         * @param args
         */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            QueneDemo quene=new QueneDemo(5);
            quene.add(10);
            quene.add(20);
            quene.add(30);
            quene.add(40);
            quene.remove();
            quene.remove();
            quene.remove();
            quene.add(70);
            quene.add(80);
            quene.add(90);
            quene.add(80);
           // quene.peek();
            while(!quene.isEmpty())
            {
                int k=quene.remove();
                System.out.println(k);
            }
        }
    
    }

## 测试结果： ##

40
    70
    80
    90
    80

## 结果分析 ##

## 创建一个长度为5的队列以后向队列添加4个数据项，再从队列head开始删除3个数据，head指针后移三个数据项，再向队列添加了4个数据项，此时已经出现了指针回绕现象，tail指针回到了队列初始位置（tail=-1）。最后输出队列中的数据，在输出队列数据使用remove方法，会出现head指针回到队列初始状态（head=0，head指针回绕），最终队列里面一次从上到存放着数据项是：70、40、80、90 、80，符合先进先出的结构特征。 ##

[20160831101615916]: /images/20220717/80b869874b264c588e48a50026da5c6f.png