前言
队列和栈是相反的，栈是先进后出，队列是先进先出，相当于排队打饭，排第一的是最先打到饭出去的。
队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出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 = (rear+1) % len
% 求的是余数
(0+1)%8=1
(7+1)%8=0
练习1 队列实现栈
1.哪个队列不为空就放哪个队列里
2.出栈的时候哪个队列不为空就出哪个队列的元素（size-1）
3.当两个队列都空了，那么说明模拟的栈是空的了
队列实现栈
class MyStack { private Queue<Integer> que1; private Queue<Integer> 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{ //两个队列都为空，指定存放到que1 que1.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(); } }
用栈实现队列
1.入栈的时候都放到第一个栈里
2.出栈的时候的出第二个栈的，如果第二个栈为空，则把第一个栈的数放到第二个栈里（前提是第一个栈不为空），也就是把它们倒过来放到s2，第一个入s2的数就是要出栈的数。
栈实现对列
//栈实现队列 class MyQueue { public Stack<Integer> s1; public Stack<Integer> s2; public MyQueue() { //实例化两个栈 s1 = new Stack<>(); s2 = new Stack<>(); } //入栈 public void push(int x) { s1.push(x); } //出栈 public int pop() { if (empty()) { return -1; } //如果s2为空，要把s1的元素放到s2里，前提是s1不为空 if (s2.empty()) { while (!s1.empty()) { s2.push(s1.pop()); } } //走到这s2一定有元素了 return s2.pop(); } //查找 public int peek() { if (empty()) { return -1; } if (s2.empty()) { while (!s1.empty()) { s2.push(s1.pop()); } } //走到这s2一定有元素了 return s2.pop(); } public boolean empty() { return s1.empty() && s2.empty(); } }
