数据结构——队列及其Java实现
本节目录
队列及其Java实现
队列(Queue)是一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作,与栈一样,队列是一种操作受限制的线性表(先进先出,FIFO-first in first out)。队列有两个末端,其中,执行插入操作的端叫作队尾,执行删除操作的端叫作队头。若队列中没有元素,称为空队列,在队列中插入一个队列元素叫作入队,从队列中删除一个队列元素叫作出队。
具体的数据结构如图:

1.实现队列核心方法
- boolean add(E e)//向队列的尾部添加一个元素,先入队列的元素在最前面。如果队列已满,则抛出一个IIIegaISlabEepeplian异常。
- boolean offer(E e)//添加一个元素并返回true 如果队列已满,则返回false。
- E remove()//删除队列的头。如果队列为空,则抛出一个NoSuchElementException异常。
- E poll()//移除并返问队列头部的元素,如果队列为空,则返回null。
- Eelement()//返回队列头部的元素,如果队列为空,则抛出一个NoSuchElementException异常。
- E peek()//返回队列头部的元素,如果队列为空,则返回null。
2.队列的具体实现过程
package person.xsc.datamanage; public class QueueDemo1<E> { private Object[] data=null;//队列数据存储 private int maxSize;//队列的容量 private int front;//队列头,允许删除 private int rear;//队列尾,允许插入 public QueueDemo1 (int initialSize) { if(initialSize>=0) { this.maxSize = initialSize; data = new Object[initialSize]; front=rear=0; }else { throw new RuntimeException("初始化大小不能小于0:"+initialSize); } } /** * 入队 * @param value */ public void in(Object value) throws Exception { if(rear == maxSize){ throw new RuntimeException("队列已满,无法插入新元素"); } data[rear ++] = value; } /** * 出队 */ public E poll(){ if(isEmpty()){ throw new RuntimeException("空队列异常"); }else { E value = (E) data[front]; data[front++] = null; return value; } } /** * 是否为空队列 * @return */ public boolean isEmpty(){ return front == rear; } /** *队列数据查询 */ public E peek(){ if(isEmpty()){ throw new RuntimeException("空队列异常"); }else { return (E) data[front]; } } }3.链表用作FIFO队列
LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。package person.xsc.datamanage;
import java.util.LinkedList; import java.util.Queue;
public class QueueDemo2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
//前面说了add()和remove()方法在失败的时候会抛出异常,所以这里不推荐使用
Queue<String> queue = new LinkedList<String>();
//添加元素
queue.offer("H");
queue.offer("e");
queue.offer("l");
queue.offer("l");
queue.offer("o");
System.out.println("----------------“遍历队列,元素不被移除”------------------------");
for(String q : queue){
System.out.print(q+" ");
}
System.out.println("");
System.out.println("----------------“遍历队列,元素逐个被移除”------------------------");
while (queue.peek() != null) {
System.out.print(queue.poll()+" ");
}
System.out.println("");
System.out.println("----------------“判断是否为空队列”------------------------");
if(queue.isEmpty()) {
System.out.println("空队列!");
}else {
System.out.println("队列不空!");
}
System.out.println("----------------“向队列插入新数据,并遍历队列”------------------------");
queue.offer("W");
queue.offer("o");
queue.offer("r");
queue.offer("l");
queue.offer("d");
for(String q : queue){
System.out.print(q+" ");
}
System.out.println("");
System.out.println("----------------“返回第一个元素 ,元素不移除”------------------------");
System.out.println("队头="+queue.peek());
}}
输出:
----------------“遍历队列,元素不被移除”------------------------
H e l l o
----------------“遍历队列,元素逐个被移除”------------------------
H e l l o
----------------“判断是否为空队列”------------------------
空队列!
----------------“向队列插入新数据,并遍历队列”------------------------
W o r l d
----------------“返回第一个元素 ,元素不移除”------------------------
队头=W
## 4.关于队列的面试问题
- **求队列最大值(有入队、出队操作)**package person.xsc.datamanage; import java.util.LinkedList; import java.util.Queue; class MaxQueue { Queue mainQueue=new LinkedList();//主 LinkedList maxQueue=new LinkedList();//辅助 public void push(int value) { mainQueue.offer(value); while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) { //peekLast()尾部元素 maxQueue.pollLast();//删除尾部元素 } maxQueue.offerLast(value);//将指定元素加入辅助 } public int max_value() { return maxQueue.isEmpty()?-1:maxQueue.peekFirst(); } public void pop() { if (mainQueue.isEmpty()) { throw new RuntimeException("空队列异常"); } if (mainQueue.poll()== maxQueue.peekFirst()) { maxQueue.pollFirst(); } } } public class QueueDemo4 { public static void main(String[] args) { // TODO Auto-generated method stub MaxQueue qu = new MaxQueue(); qu.push(6); qu.push(1); qu.push(2); qu.pop(); System.out.println(qu.max_value()); } } 输出:2
- **栈和队列的共同特点**
只允许在端点处插入和删除元素。
- **用两个栈实现一个队列**package person.xsc.datamanage; import java.util.Stack; public class QueueDemo5 { private Stack stack1 = new Stack<>();//执行入队操作的栈 private Stack stack2 = new Stack<>();//执行出队操作的栈 //方法:给队列增加一个入队的操作 public void push(int data) { stack1.push(data);//向执行入队操作的栈中压入一个数据 } //方法:给队列正价一个出队的操作 public int pop() throws Exception { ////stack1中的数据放到stack2之前,先要保证stack2里面是空的 if (stack2.empty()) { while (!stack1.empty()) { stack2.push(stack1.pop());//把stack1栈顶数据出栈,放到stack2中,直至stack1为空 } } if (stack2.empty()) { //stack2为空时,有两种可能:1、一开始,两个栈的数据都是空的;2、stack2中的数据出完了 throw new Exception("队列为空"); } return stack2.pop(); } public static void main(String[] args) throws Exception { // TODO Auto-generated method stub QueueDemo5 queue = new QueueDemo5(); System.out.println("-----------“元素1入队”--------------"); queue.push(1); System.out.println("-----------“元素11入队”--------------"); queue.push(11); System.out.println("-----------“取出队头并删除”--------------"); System.out.println(queue.pop()); System.out.println("-----------“元素4入队”--------------"); queue.push(4); System.out.println("-----------“取出队头并删除”--------------"); System.out.println(queue.pop()); System.out.println("-----------“元素2入队”--------------"); queue.push(2); System.out.println("-----------“取出队头并删除”--------------"); System.out.println(queue.pop()); }
} 输出: -----------“元素1入队”-------------- -----------“元素11入队”-------------- -----------“取出队头并删除”-------------- 1 -----------“元素4入队”-------------- -----------“取出队头并删除”-------------- 11 -----------“元素2入队”-------------- -----------“取出队头并删除”-------------- 4 ```