网站布局设计创意,哈尔滨最专业的网站建设,济南道驰网站建设有限公司怎么样,坪山网站的建设用两个栈来实现一个队列#xff0c;完成队列的Push和Pop操作。 队列中的元素为int类型。
思路#xff1a;大概这么想#xff1a;用一个辅助栈把进第一个栈的元素倒一下就好了。
比如进栈1#xff0c;2#xff0c;3#xff0c;4#xff0c;5
第一个栈#xff1a;
5 …用两个栈来实现一个队列完成队列的Push和Pop操作。 队列中的元素为int类型。
思路大概这么想用一个辅助栈把进第一个栈的元素倒一下就好了。
比如进栈12345
第一个栈
5
4
3
2
1
然后倒到第二个栈里
1
2
3
4
5
再倒出来顺序为12345
实现队列
然后要注意的事情
1栈2非空不能往里面倒数顺序就错了。栈2没数再从栈1倒。
2栈1要倒就一次倒完不倒完的话进新数也会循序不对。
import java.util.Stack;public class Solution {StackInteger stack1 new StackInteger();StackInteger stack2 new StackInteger();public void push(int node) {stack1.push(node);}public int pop() {if(stack1.empty()stack2.empty()){throw new RuntimeException(Queue is empty!);}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();}
} 用两个队列实现栈要求同上
这其实意义不是很大有些数据结构书上甚至说两个队列不能实现栈。
其实是可以的只是时间复杂度较高一个弹出操作时间为O(N)。
思路两个队列编号为1和2.
进栈操作进1号队列
出栈操作把1号队列全弄到2号队列里剩最后一个别压入而是返回。
最后还得把1和2号换一下因为现在是2号有数1号空。 仅仅有思考价值不实用。
比如压入123
队列1123
队列2空
依次弹出123
队列1里的23进入2号3弹出
队列1空
队列223 队列2中3压入1号2弹出
队列13
队列2空 队列1中只有一个元素弹出。 上代码
public class TwoQueueImplStack {QueueInteger queue1 new ArrayDequeInteger();QueueInteger queue2 new ArrayDequeInteger();
//压入public void push(Integer element){//都为空优先1if(queue1.isEmpty() queue2.isEmpty()){queue1.add(element);return;}//1为空2有数据放入2if(queue1.isEmpty()){queue2.add(element);return;}//2为空1有数据放入1if(queue2.isEmpty()){queue1.add(element);return;}}
//弹出public Integer pop(){//两个都空异常if(queue1.isEmpty() queue2.isEmpty()){try{throw new Exception(satck is empty!);}catch(Exception e){e.printStackTrace();}} //1空2有数据将2中的数据依次放入1最后一个元素弹出if(queue1.isEmpty()){while(queue2.size() 1){queue1.add(queue2.poll());}return queue2.poll();}//2空1有数据将1中的数据依次放入2最后一个元素弹出if(queue2.isEmpty()){while(queue1.size() 1){queue2.add(queue1.poll());}return queue1.poll();}return (Integer)null;}
//测试public static void main(String[] args) {TwoQueueImplStack qs new TwoQueueImplStack();qs.push(2);qs.push(4);qs.push(7);qs.push(5);System.out.println(qs.pop());System.out.println(qs.pop());qs.push(1);System.out.println(qs.pop());}
}
