新手做网站需要什么,如何在百度推广,每个网站都有服务器吗,如何wordpress建站文章目录 前言队列队列方法队列模拟实现循环队列练习1 队列实现栈 前言
队列和栈是相反的#xff0c;栈是先进后出#xff0c;队列是先进先出#xff0c;相当于排队打饭#xff0c;排第一的是最先打到饭出去的。
队列
队列#xff1a;只允许在一端进行插入数据操作栈是先进后出队列是先进先出相当于排队打饭排第一的是最先打到饭出去的。
队列
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(FirstIn First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头
队列方法 队列模拟实现
public class MyLinkQueue {//内部类static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val) {this.val val;}}public ListNode head;public ListNode last;public int usedSize;//入队列public boolean offer(int val){ListNode node new ListNode(val);if (head null){head node;last node;}else {//尾插法last.next node;node.prev last;last last.next;}usedSize;return true;}//出队列public int poll(){if (head null){return -1;}int retVal head.val;if (head.next null){head null;last null;return retVal;}head head.next;head.prev null;return retVal;}//查看对头元素public int peek(){if (head null){return -1;}return head.val;}//队列是否为空public boolean empty(){return head null;}//队列元素数量public int size(){return usedSize;}
}
循环队列
这个循环队列有点点抽象用视频来说明一下 循环队列 还可以用这种方式表示循环队列并附带两个问题
第一个问题
解决方法1用usedZize进行记录 解决方法2浪费一个空间表示满 解决方法3使用标记
第二个问题
怎么循环放rear呢?
公式 : rear (rear1) % len % 求的是余数 (01)%81 (71)%80
练习1 队列实现栈
1.哪个队列不为空就放哪个队列里 2.出栈的时候哪个队列不为空就出哪个队列的元素size-1 3.当两个队列都空了那么说明模拟的栈是空的了 队列实现栈 class MyStack {private QueueInteger que1;private QueueInteger que2;public MyStack() {que1 new LinkedList();que2 new LinkedList();}public void push(int x) {if (que1.isEmpty()){que1.offer(x);} else if (que2.isEmpty()) {que2.offer(x);}else{//两个队列都为空指定存放到que1que1.offer(x);}}public int pop() {if (empty()){return -1;}if (!que1.isEmpty()){int size que1.size();for (int i 0; i size-1; i) {int x que1.poll();//把que1中size-1的值都出到que2中que2.offer(x);}return que1.poll();//剩下最后一个值就是要出的数}else{int size que2.size();for (int i 0; i size-1; i) {int x que2.poll();que1.offer(x);}return que2.poll();}}public int top() {if (empty()){return -1;}if(!que1.isEmpty()){int size que1.size();int x -1;for (int i 0; i size; i) {x que1.poll();que2.offer(x);}return x;}else{int size que2.size();int x -1;for (int i 0; i size; i) {x que2.poll();que1.offer(x);}return x;}}public boolean empty() {return que1.isEmpty() que2.isEmpty();}
}
