劍指offer:用兩個棧實現佇列、用兩個佇列實現一個棧(java)

NO IMAGE

題目:用兩個棧實現一個佇列。佇列的宣告如下,請實現它的兩個函式appendTail和deletedHead,分別完成在佇列尾部插入節點和在佇列頭部刪除節點的功能。

該題目,要求我們操作兩個先進後出的棧實現一個先進先出的佇列Queue,當要插入元素時,不妨先插入到stack1,stack2為空,當佇列要彈出一個元素時,先把stack1的元素逐個彈出並壓入stack2,stack2順序和stack1正好相反,因此彈出stack棧頂的元素了,就是佇列要彈出的元素。

因此總結彈出的規律是,當stack2不為空直接彈出堆頂元素,當stack2為空,我們把stack1的元素逐個彈出並壓入stack2.

當插入一個元素時,由於它比stack2的元素後進隊,因此可以放入stack1中。

當總結完佇列插入、刪除的操作過程,我們就可以寫程式碼了。

private Stack<String> stack1 = new Stack<String>();  
private Stack<String> stack2 = new Stack<String>();  
public void appendTail(String s){  
stack1.push(s);  
}  
public String deletedHead() throws Exception{  
if(stack2.isEmpty()){  
while(!stack1.isEmpty()){  
stack2.push(stack1.pop());  
}  
}  
if(stack2.isEmpty()){  
throw new Exception("佇列為空,不能刪除");  
}  
return stack2.pop();  
}  

用兩個佇列實現棧。當往棧插入元素時,由於queue1和queue都為空,則插入queue1,當繼續往棧中插入元素,繼續插入queue1,但棧中要彈出一個元素,根據棧的後入先出原則,後壓入棧的應先彈出,那麼只能把queue1中不是最後一次插入的元素,插入到queue2,再彈出queue1的元素。根據上述棧插入、彈出情況的分析,寫程式碼。

queue1 = new LinkedList<String>();  
queue2 = new LinkedList<String>();  
public String pop(){  
String re =null;  
if(queue1.size() == 0 && queue2.size() == 0){  
return null;  
}  
if(queue2.size() == 0){  
while(queue1.size() >0){  
re = queue1.removeFirst();  
if(queue1.size() != 0){  
queue2.addLast(re);  
}  
}  
}else if(queue1.size() == 0){  
while(queue2.size() >0){  
re = queue2.removeFirst();  
if(queue2.size()!=0){  
queue1.addLast(re);  
}  
}  
}  
return re;  
}  
public String push(String str){  
if(queue1.size() ==0 && queue2.size() == 0){  
queue1.addLast(str);  
}else if(queue1.size()!=0){  
queue1.addLast(str);  
}else if(queue2.size()!=0){  
queue2.addLast(str);  
}  
return str;  
}