大家好，今天是队列的知识哦~
目录
一、概念
数组 、单链表和双链表都可以实现队列
1.0单链表
入栈操作：单链表是头插 时间复杂度O（1） 出栈操作：单链表是删除头节点
这样实现了 队列 先进先出的特点
2.0双链表
头插 尾删 可以实现队列
尾插 头删 也可以实现队列
只要保证特性满足 队列的特性即可
源码里面是尾插头删
3.0数组
队尾入 队头出 如果放到数组里面很难搞 队尾已经到了数组长度的极限了，队头删了还有空间
我们会发现 如果把数组前面当作队头 数组最后当作队尾
当队尾一直遍历到数组末尾 不能加数据了 但是随着队头出 数组还是有空间的呀
如果把数组卷起来 头尾相连 得到一个循环数组 这样就能更大化的利用空间了
这里我们的rear补药rear++
用下面这个公式可以是rear循环走：rear=(rear+1)%len front也一样 不会越界
有关这个部分的内容放到下面的题目里面了 622. 设计循环队列 - 力扣（LeetCode）
二、队列的方法
Queue是个接口，底层是通过链表实现的
方法预览：
1.0 offer方法
入队列 我们用的是双链表 源码里面的offer是用的头插法
所以逻辑和我们双链表的头插几乎一样
这个usedSize 可以搞一个
代码这里是尾插
下面是代码：
public void offer (int e){
ListNode newNode = new ListNode(e);
if(front ==null){
front = rear = node;
}else{
last.next = node;
node.prev = last;
last = node;
}
uesdSize++;
}2.0 poll方法
同理 类似双链表的删除头节点的方法
下面是代码：
public int poll(){
if(front == null){
return -1;
}
int ret = front.val;;
if(front == rear){
front = null;
rear = null;
usedSize--;
}
front = front.next;
front.prev= null;
usedSize--;
return ret;
}3.0 peek方法
获取队头元素 也就是获取双链表头结点元素
要注意分情况讨论
public int peek(){
if(front == null){
return -1;
}
return front.val;
}4.0 isEmpty方法
public boolean isEmpty(){
return usedSize == 0;
}三、队列的题目
1.0 用队列实现栈
思路分析：
如何用队列实现栈呢？ 如何用队列让先进的后出
方法有很多种 这里我们讲解一个方法 用交换法
两个队列 队列1和队列2 存入的时候 都存到queue1里面
要实现pop方法和top方法的时候 明确我们要删除的是后进的那个元素
我们将队列1添加的元素出队到队列2 剩下最后一个元素 （这个元素就是后进的那个）
用popped记录下后删除 然后交换队列把那些在队列2的元素交换回来
top方法的大体思路同样如此哦 这里就不再赘述了 多犯错误多调试比较快
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue1.offer(x);
}
public int pop() {
while(queue1.size()>1){
queue2.offer(queue1.poll());
}
int popped=queue1.poll();
Queue<Integer> temp = queue1;
queue1=queue2;
queue2=temp;
return popped;
}
// while(queue1.isEmpty()){
// queue2.offer(queue1.getLast());
// }
// queue2.poll();
public int top() {
// return queue2.peek();
while(queue1.size()>1) {
queue2.offer(queue1.poll());
}
int top = queue1.peek();
queue2.offer(queue1.poll());
Queue<Integer> temp = queue1;
queue1=queue2;
queue2=temp;
return top;
}
public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}2.0 用栈实现队列
思路分析：
要达到的目标是用栈模拟实现队列先进先出的结构
栈的结构是先进后出
我们可以用两个栈 一个用来push 一个用来pop和peek
我们要实现先进先出 把栈1里面的元素push到栈2里面
此时栈2的栈顶元素就是先进的元素 然后用栈2的pop方法peek方法就可以达到目的
要注意的点是：判断栈2是否为空
有时候 栈2的元素还没有pop完呢 栈1里面又加入新的元素了
这个时候我们pop也是从栈2里面出 毕竟栈2的元素比栈1早进
然后直到栈2为空了 我们想要pop了 再把栈1的元素push到栈2pop
所以pop方法和peek方法 要先判断栈2是否为空
下面是代码：
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue() {
stack1= new Stack<>();
stack2= new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(empty()){
return -1;
}
// 为什么要判断 stack是否为空呢 难道还能中途
//确保stack1 的元素只会在stack为空时倒入
//如果stack1里面有元素 stack2里面也有元素 stack里面的早 所以弹stack2
//stack2为空了再倒入
if(stack2.isEmpty()){
while(! stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if(empty()) return -1;
if(stack2.isEmpty()) {
while(! stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty()&&stack2.isEmpty();
}
}3.0 设计循环队列
我们定义了一个数组之后 开始往里面放元素呀
rear和front都在数组0下标 放入一个元素 队头front不变 队尾rear往后面加
这样直到数组满了 对应上面图片第一张 此时rear从7下标到了0小标 这个时候的处理方法有三种
第一种是 定义usedSize来记录 uedSize和len的比较
第二种是 可以使用标记 定义一个flag类型的变量 相遇的时候flag定义为false或者true
第三种是 浪费一个空间来区分 我们重点讲解这个内容
如果rear的下一个就是front 证明就是满的
rear如何实现 循环着走数组呢？
rear=（rear+1）%len; 这个公式满足了rear在数组里 面循环 不会出现数组越界异常
最后 front也得因为删除队列元素 而在数组里面循环 当然这个是后话
下面开始各种方法的讲解：
（1）判断满空的方法：为什么是rear=front呢 因为这里的rear和front因为数组是循环的
它们的位置不是固定的在开头
（2）判断满：用到rear的循环走公式碰到了front
就是要判断 (rear+1)%elem.length == front;
（3）构造器 为什么要k+1 呢 因为我们用的方法是浪费一个空间 所以创建的时候就多一个
这样就能有k个位置存放元素了
（4）入队 enQueue：入队的时候我们首先要判断满了没有 rear位置放上元素和rear位置的更新
要注意的地方是：我们不能使用rear++ 代码里面用哪个公式是为了 实现rear的循环
（5）出队 deQueue : 出队 我们首先要判断是不是空呢 注意出队的时候 直接更新front节点就可以
要注意的地方是：front 也得循环着走 所以也用到了那个公式
（6）从队首获得元素：这里的注意点是还是要提前判断循环队列是不是空的呢
（7）从队尾获得元素：这个要注意的是分类讨论 根据情况
如果rear的下标不是0 那么返回的是rear前面的元素 rear-1 前面我们也讲过 rear指向下一个
可插入的位置
如果rear的下标是0 那么返回的是 数组长度下标减一 这个特殊情况在图片上面有所呈现
下面是代码：
class MyCircularQueue {
int rear ;//队尾下表
int front ;//队头下标
int elem[] ;
public MyCircularQueue(int k) {
//构造器 设置队列的长度为k
this.elem= new int[k+1];
// rear= (rear+1)%elem.length;
}
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
elem[rear]=value;
//rear++; 这样容易越界
rear= (rear+1)%elem.length;
return true;
}
public boolean deQueue() {
//出 front往后面走就可以了
// 空的 不能出
if(isEmpty()){
return false;
}
//不空 front往后走
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];
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
if((rear+1)%elem.length == front){
return true;
}
return false;
}
}以上 就是队列的知识咯~ 遍历一个节点
感谢大家的支持
更多内容还在加载中...........
如有问题欢迎批评指正，祝大家生活愉快、学习顺利！！！