1.队列的概念
1.队列就是相当于排队打饭
2.在排队的时候就有一个队头一个队尾。
3.从队尾进对头出
4.所以他的特点就是先进先出
所以我们可以用链表来实现
单链表实现要队尾进队头出{要有last 尾插头删}
双向链表实现效率高：不管从哪个地方当作队列都是可以的，所以Linklist是神大拇指高高竖起，
所以队列是很简单的，只要写一个头删和尾部删除很简单
2.队列的代码实现
2.1普通队列的实现
我们用双向链表来队队列进行实现
很简单就不细说了，想更好了解的到链表那边去看一看。
（1）定义一个基本的双向链表
（2）用双向链表来实现入队
自己看把比较简单看过链表文章都会
package queuedemo;
public class MyQueue {
static class ListNode{
public int val ;
public ListNode prev;
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
public ListNode head;
public ListNode last;
public void offer(int val){
ListNode node =new ListNode(val);
if (head == null){
head = last = node;
}else{
last.next = node;
last = node;
}
}
public void poll(){
if (head == null){
return;
}
head = head.next;
head.prev = null;
}
public boolean Empty(){
return head == null;
}
public int peek(){
if (head == null){
return -1;
}
return head.val;
}
}
3.双端多了Deque是双端队列，两边都可以进出java包中有
2.2.循环数组（循环队列的实现原理）
1.可以保证空间不被浪费
2.定义一个front rear 这两个用来标记数据，然后rear再清零再循环到0位置继续往后，就变成循环队列了
3.这个有点抽象我们用 一个圆盘图来讲解（卷起来的数组）
开始rear和front斗士在0位置
现在有12 23 34 45 67 78 89
放一个往后面rear走一个，当rear和front相遇的时候就满了
（1）rear和front相遇有空的和满的情况
（2）如果放完下一个是front就是满的（浪费一个空间）
（3）定义一个usedSized来计数，没rear走一次就加一如果和数组长度一样了那么就是满的
（4）加一个标记第一次相遇时true 第二次就是满这样解决。
其中rear和front满足一个关系就是，通过这个关系可以来更好的实现
rear = （rear+1）%|len|
我们通过牛客上面一个题来队循环队列来进行实现
. - 力扣（LeetCode）//这是网址自己进去练习
这里我会在idea中演示代码
出队就是front往后面走，入队就是rear往后面走，记得要判断队列是否都满了控了。
代码实现
package queuedemo;
class MyCircularQueue {
public int[] elem;
public int front;
public int rear;
public MyCircularQueue(int k) {
elem = new int[k];
}
//入队操作
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
elem[rear] = value;
rear = (rear+1) % elem.length;
return true;
}
//删除队头元素
public boolean deQueue() {
if(isEmpty()) {
return false;
}
front = (front + 1) % elem.length;
return true;
}
//得到队头元素 不删除
public int Front() {
if(isEmpty()) {
return -1;
}
return elem[front];
}
//得到队尾元素 不删除
public int Rear() {
if(isEmpty()) {
return -1;
}
int index = (rear == 0) ? elem.length-1 : rear-1;
return elem[index];
}
//判空 front和rear相遇
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear+1) % elem.length == front;
}
}2.3双端队列
双端队列指的时两边都可以进出
实现代码是这样
Deque stack = new ArrayDeque<>();//双端队列的线性实现//意味着你不仅可以当作队列也可以当作栈来使用，所以stack不唯一
Deque queue = new LinkedList<>();//双端队列的链式实现 比特就
2.4队列实现栈
两个队列才能实现栈
当两个队列都是空的时候，放到第一个队列，
再次入栈的时候方到不为空的队列
出栈的时候出刀到不为空的队列出size-1个元素
剩下的就是我要出栈的元素
. - 力扣（LeetCode）题目这个就是队列实现栈
代码实现
package testdemo;
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x) {
if(empty()) {
qu1.offer(x);
return;
}
if(!qu1.isEmpty()) {
qu1.offer(x);
}else {
qu2.offer(x);
}
}
public int pop() {
if(empty()) {
return -1;
}
//找到不为空的队列 出size-1个元素
if(!qu1.isEmpty()) {
int size = qu1.size();
for (int i = 0; i < size-1; i++) {
qu2.offer(qu1.poll());
}
return qu1.poll();
}else {
int size = qu2.size();
for (int i = 0; i < size-1; i++) {
qu1.offer(qu2.poll());
}
return qu2.poll();
}
}
//peek
public int top() {
if(empty()) {
return -1;
}
//找到不为空的队列 出size-1个元素
if(!qu1.isEmpty()) {
int size = qu1.size();
int tmp = -1;
for (int i = 0; i < size; i++) {
tmp = qu1.poll();
qu2.offer(tmp);
}
return tmp;
}else {
int size = qu2.size();
int tmp = -1;
for (int i = 0; i < size; i++) {
tmp = qu2.poll();
qu1.offer(tmp);
}
return tmp;
}
}
public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
}
