題目一：使用兩個棧實現(xiàn)一個隊列
隊列的聲明如下匆绣，請實現(xiàn)它的兩個函數(shù)appendTail和deletedHead,分別完成在隊列尾部插入節(jié)點和在隊列頭部刪除節(jié)點的功能费韭。
我們通過一個具體的例子來分析該隊列插入和刪除元素的過程。首先插入一個元素a歇盼，不妨先把它插入到stack1囤捻，此時stack1 中的元素有｛a}，stack2為空胸蛛。再壓入兩個元素b和c,還是插入到stack1中，此時stack1中的元素有｛a,b,c}樱报，其中c位于棧頂葬项，而stack2仍然為空。
這個時候迹蛤，我們試著刪除從隊列中刪除一個元素民珍。按照隊列先入先出的規(guī)則襟士，由于a比b、c先插入到隊列中嚷量，最先被刪除的元素應該是a陋桂。元素a存儲在stack1中，但并不在占頂上蝶溶，因此不能直接被刪除嗜历。注意到stack2我們還一直沒有使用過，現(xiàn)在是讓stack2發(fā)揮作用的時候了抖所。如果我們把stack1中的元素逐個彈出并壓入stack2梨州，元素在stack2中的順序正好和原來的stack1中的順序相反。因此經(jīng)過3次彈出stack1和壓入stack2操作之后田轧，stack1為空暴匠，而stack2中的元素是｛c,b,a}，這個時候就可以彈出stack2的棧頂a了傻粘。此時的stack1為空每窖，而stack2的元素為{c,b}，其中在棧頂弦悉，代碼如下：
import java.util.Stack;
/**
* 用兩個棧實現(xiàn)一個隊列岛请，完成兩個函數(shù)appendTail和deletedHead, 分別是在隊列尾部插入節(jié)點 和在隊列頭部刪除節(jié)點的功能
*/
public class WDQueueWithTwoStacks {
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();
}
public static void main(String[] args) throws Exception {
WDQueueWithTwoStacks test = new WDQueueWithTwoStacks();
test.appendTail("1");
test.appendTail("2");
test.deletedHead();
}
}
題目二：使用兩個隊列實現(xiàn)棧
通過一系列的棧的壓入和彈出操作來分析用隊列模擬一個棧的過程警绩，如圖所示崇败，我們先往棧內壓入一個元素a。由于兩個隊列現(xiàn)在都是空肩祥，我們可以選擇把a插入兩個隊列中的任一個后室。我們不妨把a插入queue1。接下來繼續(xù)網(wǎng)棧內壓入b,c兩個元素混狠。我們把它們都插入queue1岸霹。這個時候 queue1包含3個元素a,b,c其中a位于隊列的頭部，c位于隊列的尾部将饺。
現(xiàn)在我們考慮從棧內彈出一個元素贡避。根據(jù)棧的后入先出的原則，最后被壓入棧的c應該最先被彈出予弧。由于c位于queue1的尾部刮吧，而我們每次只能從隊列的頭部刪除元素，因此我們可以從queueu中依次刪除a/b/c并插入到queue2中掖蛤，再從queue1中刪除c杀捻。這就相當于從棧中彈出元素c了。我們可以用同樣的方法從棧內彈出元素b蚓庭。
接下來我們考慮從棧內壓入一個元素d.此時queue1已經(jīng)有了一個元素致讥，我們就把d插入到queue1的尾部仅仆。如果我們再從棧內彈出一個元素，此時被彈出的應該是最后被壓入的d.由于d位于queue1的尾部垢袱，我們只能先從頭部刪除 queue1的元素并插入到queue2墓拜，直到queue1中遇到d再直接把它刪除。代碼如下：
import java.util.LinkedList;
/**
* 用兩個隊列實現(xiàn)棧
*/
public class WDStacksWithTwoQueue {
private LinkedList<String> queue1 = new LinkedList<String>();
private 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);
}
if (queue1.size() != 0) {
queue1.addLast(str);
} else if (queue2.size() != 0) {
queue2.addLast(str);
}
return str;
}
public static void main(String[] args) {
WDStacksWithTwoQueue stack = new WDStacksWithTwoQueue();
String tmp;
stack.push("1");
stack.push("2");
stack.push("3");
tmp = stack.pop();
System.out.println(tmp);//3
stack.push("4");
tmp = stack.pop();
System.out.println(tmp);//4
tmp = stack.pop();
System.out.println(tmp);//2
stack.push("5");
stack.push("6");
tmp = stack.pop();
System.out.println(tmp);//6
tmp = stack.pop();
System.out.println(tmp);//5
tmp = stack.pop();
System.out.println(tmp);//1
}
}
