队列 (queue)是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除, 所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出 (FIFO—first in first out)线性表。
比如我们去电影院排队买票,第一个进入排队序列的都是第一个买到票离开队列的人,而最后进入排队序列排队的都是最后买到票的。
在比如在计算机操作系统中,有各种队列在安静的工作着,比如打印机在打印列队中等待打印。
队列分为:
①、单向队列(Queue):只能在一端插入数据,另一端删除数据。
②、双向队列(Deque):每一端都可以进行插入数据和删除数据操作。
这里我们还会介绍一种队列——优先级队列,优先级队列是比栈和队列更专用的数据结构,在优先级队列中,数据项按照关键字进行排序,关键字最小(或者最大)的数据项往往在队列的最前面,而数据项在插入的时候都会插入到合适的位置以确保队列的有序。
Java代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 package queue;public class Queue { int front; int end; int elements; long arr[]; public Queue (int maxsize) { int front=0 ; int end=0 ; int elements=0 ; arr=new long [maxsize]; } public void insert (long value) { if (end==arr.length)end=0 ; arr[end]=value; ++elements; } public long remove () { if (front==arr.length)front=0 ; elements--; return arr[front++]; } public long peek () { return arr[end]; } public boolean isEmpty () { return elements==0 ; } public boolean isFull () { return elements==arr.length; } }
编写一个测试类:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 package queue;public class TestQueue { public static void main (String[] args) { Queue b=new Queue (8 ); b.insert(2 ); b.insert(8 ); System.out.println(b.isEmpty()); System.out.println(b.isFull()); System.out.println("队尾" +b.peek()); System.out.println(b.remove()); System.out.println("队尾" +b.peek()); } }
运行结果如下:
false
false
队尾8
8
队尾8
0
队尾8