1.队列(Queue)
1.1概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)的性质
入队列:进行插入操作的一端称为队尾(Tail/Rear)
出队列:进行删除操作的一端称为队头(Head/Front)
1.2 队列的使用
在Java中,Queue是个接口,底层是通过链表实现的,在实例化Queue时,必须实例化LinkedList对象,因为LinkedList实现了Queue接口
方法 | 功能 |
boolean offer(E e) | 入队列 |
E poll() | 出队列 |
peek() | 获取队头元素 |
int size() | 获取队列中有效元素个数 |
boolean isEmpty() | 检测队列是否为空 |
1.3 队列模拟实现(双列表实现)
java">public class MyQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode first;public ListNode last;//尾插public void offer(int val) {ListNode node = new ListNode(val);if(first == null) {first = last = node;}else {node.prev = last;last.next = node;last = last.next;}}//头删public int poll() {//队列为空if(first == null) {return -1;}int ret = first.val;//队列只有一个节点if(first.next == null) {first = last = null;}else {//队列有多个节点first = first.next;first.prev = null;}return ret;}//查看队头元素public int peek() {if(first == null) {return -1;}return first.val;}//判断队列是否为空public boolean isEmpty() {return first == null;}
}
1.4 循环队列(数组实现)
一开始,first 和 last 从0下标开始,放一个元素 last++ ,如此,last 即为元素当前要存放的下标
判断循环队列是否已满:
解决下标从7 到 0 的过程,不能一直让 last++、first++,这样肯定会越界
公式:last = ( last + 1 ) % len(数组长度)
代码:
java">class MyCircularQueue {public int[] elem;//数组实现public int first;public int last;public MyCircularQueue(int k) {//因为计数方法为保留一个空间,所以想要存放K个元素,需要申请K+1个空间elem = new int[k+1];}//队尾添加元素public boolean enQueue(int value) {if(isFull()) {return false;}elem[last] = value;last = (last+1)%elem.length;return true;}//队头删除元素public boolean deQueue() {if(isEmpty()) {return false;}first = (first+1)%elem.length;return true;}//从队头获取元素public int Front() {if(isEmpty()){return -1;}return elem[first];}//从队尾获取元素public int Rear() {if(isEmpty()){return -1;}int index = (last == 0) ? elem.length-1 : last-1;return elem[index];}//判空public boolean isEmpty() {return first == last;}//判满public boolean isFull() {return (last+1)%elem.length == first;}
}
2. 双端队列(Deuqe)常用!
双端队列是指允许两端都可以进行入队和出队操作的队列,deque是 "double ended queue" 的简称
Deque是一个接口,使用时必须创建LinkedList对象
在实际工程中,使用Deque接口是比较多的,栈和队列均可使用该接口,如:
java">Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
3. OJ
3.1 用队列实现栈
java">import java.util.LinkedList;
import java.util.Queue;//用队列实现栈
//该方法用到两个队列
class MyStackUseQueue {Queue<Integer> qu1;Queue<Integer> qu2;public MyStackUseQueue() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(empty()) {//若两队列均为空,将x添加到qu1中qu1.offer(x);return;}if(!qu1.isEmpty()) {//两队列哪个不为空,添加到哪个里面qu1.offer(x);}else {qu2.offer(x);}}//删除栈顶元素public int pop() {if(empty()) {//若两队列均为空,返回-1return -1;}if(!qu1.isEmpty()) {//若qu1不为空,将qu1中size-1个元素放到qu2中,剩下一个元素即为栈顶元素int size = qu1.size();//存放qu1元素个数for (int i = 0; i < size-1; i++) {//循环size-1次将元素放到qu2中qu2.offer(qu1.poll());}return qu1.poll();//将qu1中剩下一个元素出队}else {int size = qu2.size();//与上同理for (int i = 0; i < size-1; i++) {qu1.offer(qu2.poll());}}return qu2.poll();}//获取栈顶元素public int top() {if (empty()) {return -1;}//若qu1不为空,循环将qu1中所有元素,通过中间变量ret放到qu2中,当放完后,ret中存放的值即为栈顶元素if (!qu1.isEmpty()) {int size = qu1.size();int ret = -1;for (int i = 0; i < size; i++) {ret = qu1.poll();//qu1中元素出队,赋值给retqu2.offer(ret);//ret中值入队给qu2}return ret;} else {int size = qu2.size();int ret = -1;for (int i = 0; i < size; i++) {ret = qu2.poll();qu1.offer(ret);}return ret;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}
3.2 用栈实现队列
java">import java.util.Stack;//用栈实现队列,先进先出,用到两个栈
class MyQueueUseStack {Stack<Integer> st1;Stack<Integer> st2;public MyQueueUseStack() {st1 = new Stack<>();st2 = new Stack<>();}//添加元素全部添加到st1中public void push(int x) {st1.push(x);}//删除队首元素public int pop() {if(empty()) {return -1;}//若st2不为空,将st1中元素pop,push到st2中if(st2.empty()) {while(!st1.empty()) {st2.push(st1.pop());}}//因为栈是先进后出,所以模拟队列的队首元素在st1的最下面//当把元素全部挪到st2中后,st2的栈顶元素即是队首元素return st2.pop();}public int peek() {if(empty()) {return -1;}if(st2.empty()) {while(!st1.empty()){st2.push(st1.pop());}}return st2.peek();}public boolean empty() {return st1.empty() && st2.empty();}
}
以上两个OJ,若用双端队列来实现会更简单