💛1.队列的基本底层实现
public class MyQueue { int array[]; int usedsize=0; public MyQueue(){ this.array=new int [5]; }
💙2.判断是否满，满了需要扩容
Arrays.copyOf(数组，数组的长度）；我常常会忘记哈哈哈哈哈
//判满 public void ifFull(){ if(usedsize==5) array=Arrays.copyOf(this.array,array.length*2); }
💜3.判断是否为空
//是否为空 public boolean isEmpty(){ if(usedsize==0){ return true; } return false; }
❤️4.添加元素
//添加元素 public void add(int data){ ifFull(); //满了就扩容 usedsize++; array[usedsize-1]=data; }
💚5.查找队首元素
//查看队首元素 public int element(){ return array[0]; }
💓 6.出队
//出队 public int poll(){ int m=array[0]; for(int i=1;i<usedsize;i++){ array[i-1]=array[i]; } usedsize--; return array[0]; }
💕7.遍历元素个数
//遍历队列元素 public void display(){ for(int i=0;i<usedsize;i++){ System.out.println(array[i]); } }
栈的集合基本操作
offer(x);把x元素插入到队列里面
poll()：弹出栈顶元素，并且返回该值
其他与栈相同，peek,isEmpty,
注意还有一个size()这个方法也容易忽视。：返回队列数值
一、
💛
最小栈
1.说简单也很简单，就是可能在一些小细节方面进坑，比如说插入元素，就容易没想那么多，导致多插入一次;（🌚 🌚 🌚 又是一下午的经验之道）
简单讲一下我的思路点：刚开始肯定都是没思路，我就开始一个一个慢慢写，为什么是两个栈，因为他要求找到最小的元素要求时间复杂度是O（1），所以要有第二个栈，然后栈肯定，他需要有一定特殊性，才能出栈是最小的，但是他假如只有一个，那她最小的肯定就是他，所以最小栈肯定要入他，剩下的就要找还有什么类型的需要进来，
看下图👋，5和2，哪个应该进来，肯定是2应该进来，因为2小啊。我就是为了找最小值
，只有删除和新增有点难度，其余的就不谈了，没啥必要。
⭐️ 🌟 💫 还有一个问题你要想清楚，我们弹出栈的时候，最小栈应该怎么办，
看下面图，假如是图1：他的最小栈应该是是只有1。图二应该是有1，2，4，
拿图2举例子，开始弹出1，然后最小栈的栈顶也是1，然后最小栈也开始弹，开始弹出3，然后最小栈的栈顶不是3，那么就原始栈弹，最小栈不弹，换句话说：一样就弹出，不一样的不用弹出。
class MinStack { private Stack<Integer> data; private Stack<Integer> minStack; public MinStack() { data=new Stack<>(); minStack=new Stack<>(); } public void push(int val) { data.push(val); if(minStack.isEmpty()){ minStack.push(val); } else if(minStack.peek()>=val){ //这个很关键，一定要是else minStack.push(val); //避免插入的时候，有可能进入一次这个，会再次插入 } } public void pop() { int pop=data.pop(); int top=minStack.peek(); if(pop==top){ minStack.pop(); } } public int top() { return data.peek(); } public int getMin() { return minStack.peek(); } }
二、
💙
2.用队列实现栈： 解法一通过一个栈，来实现，首先，一个栈的基本操作是压栈，弹栈，是否为空，返回栈顶操作（队列是进队从尾巴进，出队从头出）弹出栈顶也就是4，那么弹出4的话那么队列的队头也是4，他的弹栈操作就实现了，那么返回栈顶也实现了，空肯定也实现了，那么我们目前最大的问题就是如何把这个1队列逆置过来，让他变成2的：1，2，3，4呢。
把它用递归的想法去想，他只有一个队列，然后只有一个的时候，不逆置（size在插入之前的个数），所以从i=0;size=0刚开始为1开始，假如插入一个size停留在插入之前也就是1，也相对应他需要调整逆置一次，重新吧1插入，形成:2，1 💗 1，2的逆置变化。然后当他是3的时候（1，2，需要被逆置）所以，（注意哈，❗️❗️❗️他并不是从3，2，1开始换，而是从3，1，2开始换，）只需要换两次。～～～以此类推。
class MyStack { Queue<Integer>stack1; public MyStack() { stack1=new LinkedList<Integer>(); } public void push(int x) { int n=stack1.size(); stack1.offer(x); for (int i = 0; i < n; i++) { stack1.offer(stack1.poll()); } } public int pop() { return stack1.poll(); } public int top() { return stack1.peek(); } public boolean empty() { return stack1.isEmpty(); } }
💚
解法2:
用两个队列：两个队列就是思路是先从出队和入队开始思考，假如说要出队，那么就需要把除了队尾元素以外的全部拿出来，放到那个空的队列中，然后剩下的一个就是队尾（也就是要出的栈顶），那么插入的时候：我们就需要看哪个是空的，哪个里面有数，假如说里面有东西，就插入非空的队列（里面有东西的），要是两个都是空，那么随便插入一个。
class MyStack{ Queue<Integer>stack1; Queue<Integer> stack2; public MyStack() { stack1=new LinkedList<Integer>(); stack2=new LinkedList<Integer>(); } public void push(int x) { if((stack1.isEmpty())&&!(stack2.isEmpty())){ stack2.offer(x); } if(!(stack1.isEmpty())&&(stack2.isEmpty())){ stack1.offer(x); } if(stack1.isEmpty()&&stack2.isEmpty()){ stack1.offer(x); } } public int pop() { if((stack1.isEmpty())&&(!stack2.isEmpty())){ int a=stack2.size(); while(a>1){ stack1.offer(stack2.poll()); a--; //除了最后一个，全部移动到另一个队列中 } return stack2.poll(); //删除 } else if((!stack1.isEmpty())&&(stack2.isEmpty())){ int a=stack1.size(); while(a>1){ stack2.offer(stack1.poll()); a--; } return stack1.poll(); } else{ return -1; } } public int top() { if((stack1.isEmpty())&&(!stack2.isEmpty())){ int a=stack2.size(); while(a>1){ stack1.offer(stack2.poll()); a--; } int c=stack2.peek(); //最后一个剩余的元素，需要存起来，放回到和其他元素在一起 stack2.poll(); stack1.offer(c); return c; } if((!stack1.isEmpty())&&(stack2.isEmpty())){ int a=stack1.size(); while(a>1){ stack2.offer(stack1.poll()); a--; } int c=stack1.peek(); stack1.poll(); stack2.offer(c); return c; } else { return -1; } } public boolean empty() { return stack1.isEmpty()&&stack2.isEmpty(); //两个都是空，才真正是空 } }
