队列是一种线性数据结构，是一种运算受限的线性表，只允许在队尾插入，在队头删除。运算规则是先进先出。恰好和栈相反。栈是先进后出。因为栈只在栈顶做删除和插入。
队列按照存储结构可以分为顺序队列和链式队列。顺序队列采用数组实现，链式队列采用节点的方式实现。
//顺序队列
1 package queue; 2 //1.队列是一种运算受限的线性表，运算规则是先进先出。只能在队头和队尾进行操作 3 //2.队列由数据域，队头，队尾组成 4 //3.队列在队尾进行插入操作，在队头进行删除操作 5 public class Queue<E> { 6 private Object[] data = null; //数据域 7 private int front = 0; //队头，允许删除 8 private int rear = 0; //队尾，允许插入 9 private int maxSize = 0; //队列容量 10 11 //初始化队列 12 public Queue(){ 13 this(10); 14 } 15 16 public Queue(int initialSize) { 17 if(initialSize >= 0){ 18 this.data = new Object[initialSize]; //初始化数据域 19 this.maxSize = initialSize; 20 }else { 21 throw new RuntimeException("初始化大小不能小于0:" + initialSize); 22 } 23 } 24 25 //判断队列是否为空 26 public boolean isEmpty(){ 27 return this.front == this.rear; //如果队头队尾相等说明为空 28 } 29 30 //判断队列是否已满 31 public boolean isMaxSize(){ 32 return this.rear == this.maxSize ? true : false; //如果队尾指针大于最大容量，说明队列已经满了 33 } 34 35 //入队，从队尾插入，从队头删除 36 public boolean push(E e){ 37 //判断队列是否已满 38 if(this.isMaxSize()){ 39 System.err.println("队列已满，无法插入"); 40 return false; 41 } 42 data[rear] = e; //将元素插入到队尾 data[0] = 插入值 43 rear++ ; //更新队尾指针 44 return true; 45 } 46 47 //弹出队列 48 @SuppressWarnings("unchecked") 49 public E pop(){ 50 //判断是否为空，为空将无法出队 51 if(isEmpty()){ 52 System.err.println("队列为空，无法插入"); 53 return null; 54 } 55 //在队头弹出 56 E e = (E) data[front]; //对头引用 57 data[front] = null; //将弹出的对头内存销毁 58 front ++; //更新队头指针为后面的一位元素 59 return e; 60 } 61 62 //返回队首元素，但不删除 63 @SuppressWarnings("unchecked") 64 public E peek(){ 65 if(isEmpty()){ 66 System.err.println("队列为空"); 67 return null; 68 } 69 70 return (E) this.data[front]; 71 } 72 73 //遍历队列 74 public void display(){ 75 while(front < rear){ 76 System.out.println(data[front]); 77 front ++; 78 } 79 } 80 81 //返回队列实际长度 82 public int getSize(){ 83 return this.data.length; 84 } 85 86 public static void main(String args[]){ 87 Queue<Integer> queue = new Queue<Integer>(); 88 int i = 0; 89 while(i < 10){ 90 queue.push(i); 91 i ++; 92 } 93 // queue.pop(); 94 queue.display(); 95 } 96 97 }
//链式队列
1 package queue; 2 3 //链式队列，由队头和队尾节点组成，节点中包含数据域和指针域 4 public class LinkedQueue<E> { 5 //1.定义队列结构 6 //节点类 7 @SuppressWarnings("hiding") 8 private class Node<E>{ 9 public E data = null; //数据域 10 public Node<E> next = null; //指针域 11 12 //构造方法 13 @SuppressWarnings("unused") 14 public Node(){} 15 16 public Node(E data, Node<E> next){ 17 this.data = data; 18 this.next = next; 19 } 20 21 }/*Node*/ 22 23 private Node<E> front = null; //队头 24 private Node<E> rear = null; //队尾 25 private int size = 0; //队列长度 26 27 //2.判断队列是否为空 28 public boolean isEmpty(){ 29 return size == 0; 30 } 31 32 //3.入队 33 public boolean push(E e){ 34 Node<E> node = new Node<E>(e, null); 35 //队列为空的情况下 36 if(isEmpty()){ 37 this.rear = node; //尾节点赋值为新插入的节点 38 this.front = this.rear; //在只有一个节点的情况下，头尾节点相等 39 size++; 40 return true; 41 } 42 //不为空的情况下 43 this.rear.next = node; //尾节点指向新节点 44 this.rear = node; //更新尾节点 45 size ++; //队列节点数+1 46 return true; 47 } 48 49 //4.出队 50 public E pop(){ 51 //判断队列是否为空 52 if(isEmpty()){ 53 System.err.println("队列为空"); 54 return null; 55 } 56 //弹出队头，更新队头指针 57 Node<E> temp = this.front; //获取队头引用 58 this.front = this.front.next; //更新队头指针 59 temp.next = null; //释放原队头节点引用 60 return temp.data; 61 62 } 63 64 //5.返回队头但不删除 65 public E peek(){ 66 //判断是否为空 67 if(isEmpty()){ 68 System.err.println("为空，不能返回"); 69 return null; 70 } 71 return this.front.data; 72 } 73 74 //6.求长 75 public int getSize(){ 76 return this.size; 77 } 78 79 //7.打印队列 80 public void display(){ 81 for (int i = 0; i < this.size; i++) { 82 if(this.front == null){ 83 return; 84 } 85 System.out.println(this.front.data); 86 this.front = this.front.next; 87 } 88 } 89 90 public static void main(String args[]){ 91 LinkedQueue<Integer> queue = new LinkedQueue<Integer>(); 92 //1.入队 93 int i = 0; 94 while(i < 10){ 95 queue.push(i); 96 i++; 97 } 98 99 //出队 100 int j = 0; 101 while(j < 8){ 102 System.out.println(queue.pop()); 103 j ++; 104 } 105 106 107 // queue.display(); 108 109 } 110 111 112 }