这两个问题对我来说有点绕,不过还好,终于搞明白了,我把他们写在这里,防止自己再次犯错
1.用栈实现队列
一个栈显然是无法实现队列的,所以需要两个栈
数据是12,23,34,45,56.
首先把这几个数据按照顺序依次入栈1.
然后把它们按顺序出栈1,进入栈2
这个时候栈2的栈顶元素就是我们需要的
我在写这个代码的时候陷入了一种思维怪圈,总想着要求size(),判断栈满啥的,但是这是不对的,栈如果满了会自动扩容,所以不要这样想
现在上代码
class MyQueue { public Stack<Integer> stack1; public Stack<Integer> stack2; public MyQueue() { stack1=new Stack<>(); stack2=new Stack<>(); } public void push(int x) { //默认压入到栈1中 stack1.push(x); } public int pop() { if(empty()){ return -1; } if(stack2.empty()){ while(!stack1.empty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } public int peek() { if(empty()){ return -1; } if(stack2.empty()){ while(!stack1.empty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } public boolean empty() { return stack1.isEmpty()&&stack2.isEmpty(); } }
现在让我们进行下一个题,用队列实现栈
先判断哪个队列为空,哪个为空才能放到队列里面
这是在pop的情况
这是在top的情况
定义一个size()
上代码
class MyStack { Queue<Integer> queue1; Queue<Integer> queue2; public MyStack() { queue1=new LinkedList<>(); queue2=new LinkedList<>(); } public void push(int x) { if(!queue1.isEmpty()){ queue1.offer(x); }else if(!queue2.isEmpty()){ queue2.offer(x); }else{ queue1.offer(x); } } public int pop() { if(empty()){ return -1; } if(!queue1.isEmpty()){ int size=queue1.size(); while(size-1!=0){ int val= queue1.poll(); size--; queue2.offer(val); } return queue1.poll(); }else{ int size=queue2.size(); while(size-1!=0){ int val= queue2.poll(); size--; queue1.offer(val); } return queue2.poll(); } } public int top() { if(empty()){ return -1; } if(!queue1.isEmpty()){ int size=queue1.size(); int val=-1; while(size!=0){ val= queue1.poll(); size--; queue2.offer(val); } return val; }else{ int size=queue2.size(); int val=-1; while(size!=0){ val= queue2.poll(); size--; queue1.offer(val); } return val; } } public boolean empty() { return queue1.isEmpty()&&queue2.isEmpty(); } }
这就是今天的博客,我们下期再见,886!!!