Cracking coding interview(3.5)使用2个堆栈实现一个队列
程序员文章站
2023-12-25 14:57:09
...
3.5 Implement a MyQueue class which implements a queue using two stacks. explanation: 1.MyQueue实现原理:当MyQueue需要offer(add)一个元素时,直接添加到堆栈s1中即可,若要poll(remove)一个元素时,则需要借助堆栈s2,将s1中元素pop并且push到s2中,
3.5 Implement a MyQueue class which implements a queue using two stacks.
explanation:
1.MyQueue实现原理:当MyQueue需要offer(add)一个元素时,直接添加到堆栈s1中即可,若要poll(remove)一个元素时,则需要借助堆栈s2,将s1中元素pop并且push到s2中,此时s2栈顶元素即是对头元素。之后再将s2中元素pop并且push回s1中。
2.MyQueue2针对MyQueue的优化。堆栈s2中的元素不再回到s1.堆栈s1用于存放最新的push的元素,堆栈s2用于将堆栈s1中的现有元素反序,这样最先入队的几个元素都会在s2中。当MyQueue队列要弹出一个元素时,只需要从s2中弹出元素即可,若s2为空,则将s1中的最新的元素再次pop->push到s2。如此往复。
import java.util.Stack; class MyQueue{ private Stacks1 = new Stack (); private Stack s2 = new Stack (); //time complexity:O(1), space complexity:O(1) public boolean offer(int val){ s1.push(val); return true; } //time complexity:O(n) space complexity:O(n) public int poll(){ if(empty()) return Integer.MIN_VALUE; else{ while(!s1.empty()) s2.push(s1.pop()); int val = s2.pop().intValue(); while(!s2.empty()) s1.push(s2.pop()); return val; } } public boolean empty(){ return s1.empty(); } } //improvement for MyQueue class MyQueue2{ Stack s1 = new Stack (); Stack s2 = new Stack (); public boolean offer(int val){ s1.push(val); return true; } //time complexity gradually reduced, most cases is O(1) public int poll(){ if(s2.empty()) while(!s1.empty()) s2.push(s1.pop()); if(s2.empty()) return Integer.MIN_VALUE; else return s2.pop().intValue(); } public boolean empty(){ if(s1.empty() && s2.empty()) return true; else return false; } } public class Solution{ public static void main(String[] args){ //test for MyQueue MyQueue mq = new MyQueue(); int i=0; for(;i 10 && !mq.empty()) System.out.print(mq.poll()+" "); System.out.println(); for(i=40;i