題目：用兩個棧實現(xiàn)一個隊列，用兩個隊列實現(xiàn)一個棧。

首先要了解棧和隊列這兩種數(shù)據(jù)結(jié)構(gòu)各自的特點，棧是一種后入先出（Last In First Out，LIFO）的數(shù)據(jù)結(jié)構(gòu)，隊列是一種先進先出（First In First Out，FIFO）的數(shù)據(jù)結(jié)構(gòu)。

1. 兩個棧實現(xiàn)一個隊列

兩個棧實現(xiàn)一個隊列有如下兩種解決思路。

思路一：s1是入棧的，s2是出棧的。

（1）入隊列，直接壓到s1中去就行了。

（2）出隊列，先把s1中的元素全部出棧壓入s2中，彈出s2中的棧頂元素，再把s2的所有元素全部壓回s1中。

思路一方案實現(xiàn)過程

?

我們發(fā)現(xiàn)，棧s1負責(zé)元素的存儲，棧s2作為過渡棧，每次元素出隊時都需要將元素倒入到棧s2，彈出元素后又將元素倒回到棧s1，可以看出這個過程比較麻煩，因此有了如下思路二。

?

思路二：s1是入棧的，s2是出棧的。

（1）入隊列：直接壓入s1即可。

（2）出隊列：如果s2不為空，把s2中棧頂元素直接彈出；否則，把s1的所有元素全部彈出壓入s2中，再彈出s2的棧頂元素。

?

元素出隊列有兩種情況，一種是s1棧不為空，棧s2為空，此時將s1中元素都倒入s2，彈出棧s2的棧頂元素；一種是s1和s2都不為空，此時直接彈出棧s2的棧頂元素。

?

出隊情況一：棧s1不為空，棧s2為空。

情況一元素出隊列過程

?出隊情況二 ：棧s1和s2都不為空。

情況二元素出隊列過程

相比思路一，思路二的方案減少了元素在兩個棧內(nèi)的轉(zhuǎn)移，顯然是一種比較優(yōu)化的方案。?思路二的實現(xiàn)代碼如下：

1 import java.util.Stack; 2 3 public class b09_用兩個棧實現(xiàn)隊列 { 4 5 public static void main(String[] args) { 6 QueueWithTwoStack queue = new QueueWithTwoStack(); 7 queue.offer(1); 8 queue.offer(2); 9 queue.offer(3); 10 System.out.println(queue.peek()); 11 System.out.println(queue.poll()); 12 System.out.println(queue.peek()); 13 } 14 15 private static class QueueWithTwoStack{ 16 17 public static Stack<Integer> stackPush; //只負責(zé)入棧 18 public static Stack<Integer> stackPop; //只負責(zé)出棧 19 20 public QueueWithTwoStack() { 21 stackPush = new Stack<>(); 22 stackPop = new Stack<>(); 23 } 24 25 /* 26 * 在隊列尾部插入結(jié)點 27 */ 28 public void offer(int data) { 29 // 元素直接入棧 30 stackPush.push(data); 31 } 32 33 /* 34 * 在隊列頭部刪除結(jié)點 35 */ 36 public int poll() { 37 if (stackPop.empty() && stackPush.empty()) { //兩個棧都為空 38 throw new RuntimeException("Queue is empty."); 39 } else if (stackPop.empty()) { 40 // stackPop為空，則將stackPush中的元素倒入stackPop 41 while(!stackPush.empty()){ 42 stackPop.push(stackPush.pop()); 43 } 44 } 45 return stackPop.pop(); 46 } 47 48 /* 49 * 取隊列頭部結(jié)點，不從隊列中移除結(jié)點 50 */ 51 public int peek() { 52 if (stackPop.empty() && stackPush.empty()) { 53 throw new RuntimeException("Queue is empty!"); 54 } else if (stackPop.empty()) { // 用于出棧的棧為空 55 while (!stackPush.empty()) { 56 stackPop.push(stackPush.pop()); 57 } 58 } 59 // 用于出棧的棧不為空則直接去棧頂元素 60 return stackPop.peek(); 61 } 62 } 63 }

2.?兩個隊列實現(xiàn)一個棧

?思路一：q1是專職進出棧的，q2只是個中轉(zhuǎn)站。

（1）入棧：直接入隊列q1即可；

（2）出棧：把q1的除最后一個元素外全部轉(zhuǎn)移到隊q2中，然后把剛才剩下q1中的那個元素出隊列。之后把q2中的全部元素轉(zhuǎn)移回q1中。

元素入棧出棧過程

思路二：q1和q2同時負責(zé)進出棧。

（1）入棧：如果q1和q2都為空，則隨便入哪個隊列都可；如果一個隊列為空一個隊列非空，則元素入非空隊列；如果兩個都非空，則入隊列q1即可；

（2）出棧：如果一個隊列為空一個隊列非空，則將非空隊列的隊尾元素出隊；如果兩個隊列都非空，則將隊列q1的隊尾元素出隊，其他元素入隊列q2。

?

其實思路二和前面“兩個棧實現(xiàn)一個隊列”的思路類似，都是減少元素在兩個隊列之間的轉(zhuǎn)換，都是一種優(yōu)化的解決方案。思路二的代碼實現(xiàn)如下：

1 import java.util.LinkedList; 2 3 public class b09_用兩個隊列實現(xiàn)棧 { 4 5 public static void main(String[] args) { 6 StackWithTwoQueue stack = new StackWithTwoQueue(); 7 stack.push(1); 8 stack.push(2); 9 stack.push(3); 10 11 System.out.println(stack.peek()); 12 stack.push(4); 13 System.out.println(stack.pop()); 14 System.out.println(stack.pop()); 15 } 16 17 public static class StackWithTwoQueue { 18 static LinkedList<Integer> queue1 = new LinkedList<>(); 19 static LinkedList<Integer> queue2 = new LinkedList<>(); 20 21 /* 22 * 向棧中添加元素 23 */ 24 public static void push(int data) { 25 if (!queue1.isEmpty()) { 26 queue1.offer(data); 27 } else { 28 queue2.offer(data); 29 } 30 } 31 32 /* 33 * 從棧中取出棧頂元素 34 */ 35 public static int pop() { 36 if (!queue1.isEmpty()) { 37 // queue1不為空，則把queue1中除最后一個元素的其他元素移入queue2 38 while(queue1.size() != 1) { 39 queue2.offer(queue1.poll()); 40 } 41 return queue1.poll(); 42 } else if (!queue2.isEmpty()) { 43 // queue2不為空，則把queue2中除最后一個元素的其他元素移入queue1 44 while(queue2.size() != 1) { 45 queue1.offer(queue2.poll()); 46 } 47 return queue2.poll(); 48 } else { 49 System.out.println("Stack is empty!"); 50 } 51 return -1; 52 } 53 54 /* 55 * 取棧頂元素 56 */ 57 public static int peek() { 58 if (!queue1.isEmpty()) { 59 while (queue1.size() != 1) { 60 queue2.offer(queue1.poll()); 61 } 62 // 和pop()函數(shù)思路一樣，只是最后一個元素取出后需要將該元素再添加到queue2中 63 int val = queue1.poll(); 64 queue2.offer(val); 65 return val; 66 } else if (!queue2.isEmpty()) { 67 while(queue2.size() != 1) { 68 queue1.offer(queue2.poll()); 69 } 70 int val = queue2.poll(); 71 queue1.offer(val); 72 return val; 73 } else { 74 System.out.println("Stack is empty!"); 75 } 76 return -1; 77 } 78 } 79 }

?相比思路一，思路二的方案減少了元素在兩個棧內(nèi)的轉(zhuǎn)移，顯然是一種比較優(yōu)化的方案。

轉(zhuǎn)載于:https://www.cnblogs.com/walker-/p/8877878.html

總結(jié)

以上是生活随笔為你收集整理的两个栈实现一个队列，两个队列实现一个栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。