三、
💜
用栈实现队列和，大体和用队列实现栈的思想相同，但是我们这里面定义了一个m，他的含义是什么呢，因为假如我们插入，删除，取栈顶的时候情况不同。假如删除和取栈顶的操作，需要把栈中的元素全逆置出来，如果我们删除了，就不用再需要取栈顶时候逆置。但是当我们插入的时候有需要把原本逆置的元素给他恢复到正常状态，这样他才可以进行正常的插入，不影响他的顺序。后续假如再去删除接着逆置就好了，所以我们这里定义一个m，m开始为0，偶数默认有序，奇数认为进行了逆序操作，push是如果正常直接插入，不正常的话奇数，开始一个逆序把它变为正常💫💫💫（要注意这个m不++）因为把它变到正常序了，下一个要进行的操作还是需要逆序
class MyQueue { Stack<Integer> stack1; Stack <Integer>stack2; int m=0; public MyQueue() { stack1=new Stack<>(); stack2=new Stack<>(); } public void push(int x) { if(m%2==0) { if ((stack1.isEmpty()) && !(stack2.isEmpty())) { stack2.push(x); } if (!(stack1.isEmpty()) && (stack2.isEmpty())) { stack1.push(x); } } if(m%2!=0){ if((stack1.isEmpty())&&(!stack2.isEmpty())){ int a=stack2.size(); while(a>0){ stack1.push(stack2.pop()); a--; } m++; stack1.push(x); } else if((!stack1.isEmpty())&&(stack2.isEmpty())){ int a=stack1.size(); while(a>0){ stack2.push(stack1.pop()); a--; } m++; stack2.push(x); } } if (stack1.isEmpty() && stack2.isEmpty()) { stack1.push(x); } } public int pop() { if(m%2!=0){ if((stack1.isEmpty())&&(!stack2.isEmpty())){ return stack2.pop(); } if((!stack1.isEmpty())&&(stack2.isEmpty())){ return stack1.pop(); } } if(m%2==0){ if((stack1.isEmpty())&&(!stack2.isEmpty())){ int a=stack2.size(); while(a>1){ stack1.push(stack2.pop()); a--; //除了最后一个，全部移动到另一个队列中 } m++; return stack2.pop(); //删除 } else if((!stack1.isEmpty())&&(stack2.isEmpty())){ int a=stack1.size(); while(a>1){ stack2.push(stack1.pop()); a--; } m++; return stack1.pop(); } } return -1; } public int peek() { if(m%2!=0){ if((stack1.isEmpty())&&(!stack2.isEmpty())){ return stack2.peek(); } if((!stack1.isEmpty())&&(stack2.isEmpty())){ return stack1.peek(); } } if(m%2==0) { if ((stack1.isEmpty()) && (!stack2.isEmpty())) { int a = stack2.size(); while (a > 1) { stack1.push(stack2.pop()); a--; } m++; int c = stack2.peek(); //最后一个剩余的元素，需要存起来，放回到和其他元素在一起 stack2.pop(); stack1.push(c); return c; } if ((!stack1.isEmpty()) && (stack2.isEmpty())) { int a = stack1.size(); while (a > 1) { stack2.push(stack1.pop()); a--; } m++; int c = stack1.peek(); stack1.pop(); stack2.push(c); return c; } } return -1; } public boolean empty() { return stack1.isEmpty()&&stack2.isEmpty(); } }
四、设计循坏队列
⭐️⭐️⭐️
首先设计循环队列，我们要清楚什么是循环队列以及他出现的意义
🌋🌋🌋1.为了解决假溢出问题（front在q号位置，rear在m号位置）就叫假溢出，因为正常队列这个时候存不了，所以才有循环队列。（假溢出的原因是由于弹栈导致会使front向前移动）
⛅️⛅️⛅️2.不是说他可以无限插入无数个数，而是她可以满了后，覆盖前面的数据
❗️❗️循环队列的特性是（有一个空间，他是不用来存东西，而是区分判断他是空还是满，从而彻底解决假溢出（满就是(rear+1)%capaciy(容量k+1)==front
🎥🎥🎥
其次不要忘了，他的本质还是队列，插入完成rear++; 删除是front++。 （但是这个题，他不允许，满的时候就不可以插入了）
class MyCircularQueue { int array[]; int front=0; int rear=0; int capacity; public MyCircularQueue(int k) { capacity=k+1; this.array=new int[capacity]; } public boolean enQueue(int value) { if(isFull()){ return false; } if(rear==capacity){ //如果这时候相等，但还不是满，就说明是假溢出 rear=0; //此时吧rear放到0开始，（front没占的空间） } array[rear]=value; rear++; return true; } public boolean deQueue() { if(isEmpty()){ return false; } if(front==capacity){ //假溢出，此时要删除，直接front跳到1，把0号删除 front=1; return true; } front++; return true; } public int Front() { if(isEmpty()){ return -1; } return array[front]; } public int Rear() { if(isEmpty()){ return -1; } return array[rear-1]; } public boolean isEmpty() { if(front==rear){ return true; } return false; } public boolean isFull() { if((rear+1)%(capacity)==front){ //不行就记，能理解更好 return true; } return false; } }
一个比较不好理解的，弹栈中
if(front==capacity){ //假溢出，此时要删除，直接front跳到1，把0号删除
front=1;
return true;
}
也就是这种情况，front需要跳过到0的位置，如果rear是0不就是null了吗，就不会弹栈了
五、
💥💥💥
判断是不是栈的压入，弹出的序列：我们在想的时候很好想，但是具体如何写成代码的时候，就有些问题了。
解法：将给的序列，压入到栈里面，然后看弹出栈的序列和栈顶元素是否相同。假如说相同，那么进行弹栈，假如说不相同就把这个元素添加进入栈里面
那么这里说一点细节，光看上面肯定会有一些小疑惑：
那么首先是一边判断一边压入，他需要判断，从哪里开始出栈，假如说匹配上就说明，从这个点开始出栈了
其次空了，他就直接插入就行，
public boolean IsPopOrder (int[] pushV, int[] popV) { // write code here Stack <Integer>stack1=new Stack<>(); int i=0; for(int j=0;j<pushV.length;j++){ while(i<pushV.length&&(stack1.isEmpty()||popV[j]!=stack1.peek())){ stack1.push(pushV[i]); //遍历去寻找，有没有和栈顶相同的序列元素， i++; } if(!stack1.isEmpty()&&popV[j]==stack1.peek()) stack1.pop(); else return false; } return true; }
