4. 用栈实现队列
题目：
思路：
队列是先进先出，需要用到两个栈才能实现队列
指定S1为输入栈，S2为输出栈
入队时，直接将元素压入S1栈即可
出队时，要将输入栈S1中的元素依次出栈，并压入输出栈S2中，然后将S2栈顶元素出栈，这样就能实现先入队的元素先出队，有一点要注意，只有S2为空的时候，才能将输入栈S1中的元素移到S2中，不然会打乱队列顺序！
实现代码：
class MyQueue { //创建两个栈 Stack<Integer> s1;//输入栈 Stack<Integer> s2;//输出栈 public MyQueue() { s1 = new Stack<>(); s2 = new Stack<>(); } public void push(int x) { s1.push(x);//入队直接将元素压入S1即可 } public int pop() { int size = s1.size();//出队时，将s1中所以元素移至s2中 if(!s2.isEmpty()){ return s2.pop();//s2不为空，则直接弹出栈顶元素即可 }else{ for(int i=0; i<size; i++){//否则要将s1中元素转移到s2中再弹出s2栈顶元素 int tmp = s1.pop(); s2.push(tmp); } return s2.pop(); } } public int peek() {//和出队方法一样，只不过由删除变成查看，只看不删 int size = s1.size(); if(!s2.isEmpty()){ return s2.peek(); }else{ for(int i=0; i<size; i++){ int tmp = s1.pop(); s2.push(tmp); } return s2.peek(); } } public boolean empty() { return s1.isEmpty() && s2.isEmpty(); } }
5. 设计循环队列
题目：
思路：
要设计一个循环队列，用到的是一个数组，需要设置一个front下标表示队列首元素，rear下标，表示尾元素后一个可用位置的下标
有三个关键问题要解决：
①front和rear相遇之后，队列到底是空了还是满了？
答：每次再放元素的时候，都去判断rear位置的下一个位置是不是front，如果是，就满了，所以要预留一个空间，不放元素
②rear每次存放完成之后，能不能进行rear=rear+1
③front每次出队之后，能不能进行front=front+1
答：rear和front都不能直接+1，因为假设7个元素的循环队列，下标走到6了，6+1=7 数组此时能访问7下标嘛？不能，所以研究处一个公式rear/front = (rear/front+1)%len就能表示下一个位置了
实现代码：
class MyCircularQueue { private int[] elem; //数组 private int front;// 头 private int rear;//尾巴下标 当前可以存放元素的下标 public MyCircularQueue(int k) { //这里为什么是k+1: 题的描述指定要放k个，因为用我的方法实现的时候就是多一个空间出来的 this.elem = new int[k+1]; this.rear = 0; this.front = 0; } //入队 public boolean enQueue(int value) { if(isFull()) //判断循环队列满了没有 return false;//满了就返回false this.elem[this.rear] = value;//没满就给rear位置插入元素 this.rear = (this.rear+1)%this.elem.length;//然后rear下标往后走一步 //this.rear = this.rear+1; return true; } //删除 出队 public boolean deQueue() { if(isEmpty()) {//先判断循环队列是否空 return false;//空的就返回false } //循环队列不为空，就将首元素位置，front往后走一步 //原来的元素会被以后加入的覆盖掉，或者不再能被访问到 this.front = (this.front+1)%this.elem.length; return true; } //得到队头元素 public int Front() { if(isEmpty()) {//依旧先判断是否为空 return -1; } return this.elem[this.front]; } //得到队尾元素 注意：当rear == 0下标的时候 public int Rear() { if(isEmpty()) {//依旧先判断是否为空 return -1; } //这里注意一个问题，我们已经知道rear-1位置就是队尾元素，可是当rear=0的时候，0-1=-1，这样不就出错了？所以遇到这种情况的时候用 循环队列的长度-1 就是0下标的上一个位置了 int index = (this.rear == 0) ? this.elem.length-1 : this.rear-1; return this.elem[index]; } public boolean isEmpty() { //只要他两相遇了 那么就是空的队列 if(this.front == this.rear) { return true; } return false; } public boolean isFull() { //判断rear位置的下一个位置是不是front，如果是，就满了 if((this.rear+1) % this.elem.length == this.front) { return true; } return false; } }
