本文轉載自【微信公眾號：五角錢的程式設計師，ID:xianglin965】經微信公眾號授權轉載，如需轉載與原文作者聯繫
文章目錄
9. 用兩個棧實現隊列題目連結題目描述解題思路分析Java實現棧Java實現隊列用兩個棧實現隊列
9. 用兩個棧實現隊列
題目連結
牛客網
https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github
題目描述
用兩個棧來實現一個隊列，完成隊列的 Push 和 Pop 操作。
解題思路
in棧用來處理入棧（push）操作，out棧用來處理出棧（pop）操作。一個元素進入in棧之後，出棧的順序被反轉。當元素要出棧時，需要先進入out棧，此時元素出棧順序再一次被反轉，因此出棧順序就和最開始入棧順序是相同的，先進入的元素先退出，這就是隊列的順序。
分析
棧的特點是先進後出，而隊列的特點是先進先出，主要就是在兩個棧中來回倒騰從而實現隊列的功能，就好像一個黑盒子，裡邊是兩個棧的操作，但其他人在用這個黑盒子的時候，感覺就像在用隊列一樣。隊列和棧只是邏輯性的數據結構，實現隊列和棧可以用數組實現，也可以用鍊表實現，只要滿足隊列先進先出，棧先進後出的特性就可以。
用兩個棧實現隊列，比如一開始在stack1中把a，b，c入棧，想刪除虛擬隊列的隊首元素時，即刪除a，但是a在棧底，無法直接刪除，所以這個時候就要利用stack2了，在進行刪除操作時，可以把stack1中的c，b，a依次彈出併入棧到stack2中，此時a就在stack2的棧頂了，可以直接pop掉。現在b變成stack2的棧頂元素了，繼續刪除b，直接就可以pop，這就完成了隊列的pop操作。那麼怎麼插入一個新元素呢，比如插入d，那麼可以讓d直接入棧到stack1。繼續刪除隊列隊首元素，從stack2中刪除c，然後把d彈出stack1併入棧stack2，然後從stack2中直接pop。通過觀察我們發現，如果進行虛擬隊列的push操作，可以把元素直接入棧到stack1；如果進行虛擬隊列的pop操作，如果stack2為空，那麼把stack1中所有的元素彈出併入棧到stack2，然後對stack2進行pop操作；如果stack2不為空，那麼直接對stack2進行pop操作，到這裡你是不是已經思路變得清晰了。
我們先來用Java的LinkedList鍊表數據結構來實現鏈式棧和鏈式隊列，為後面的用兩個棧實現隊列和用兩個隊列實現棧來服務。
Java實現棧
package 用兩個棧實現隊列;/*
作者 :XiangLin
文件 :stackDemo.java
IDE :IntelliJ IDEA
*/
import java.util.Iterator;
import java.util.LinkedList;
/**
* 棧
*/
public class stackDemo {
private LinkedList<String> stackList = new LinkedList<>();
/**
* 入棧
*/
public void push(String str){
stackList.addFirst(str);
}
/**
*
*/
public String pop(){
return stackList.removeFirst();
}
/**
* 判斷是否為空
*/
public boolean empty(){
return stackList.isEmpty();
}
/**
* 列印棧內所有元素
*/
public void printStack(){
Iterator iterator = stackList.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next() + " ");
}
System.out.println();
}
public static void main(String[] args) {
stackDemo stack = new stackDemo();
System.out.println(stack.empty());
stack.printStack();
stack.push("a");
stack.push("b");
stack.push("c");
System.out.println(stack.empty());
stack.printStack();
}
}
輸出：
true
false
c
b
a
Java實現隊列
package 用兩個棧實現隊列;/*
作者 :XiangLin
文件 :QueueDemo.java
IDE :IntelliJ IDEA
*/
import java.util.Iterator;
import java.util.LinkedList;
/**
* 隊列
*/
public class QueueDemo {
private LinkedList<String> queueList = new LinkedList<String>();
/**
* 入隊列
*/
public void push(String str){
queueList.add(str);
}
/**
* 出隊列
*/
public String pop(){
return queueList.removeFirst();
}
/**
* 獲得隊列元素個數
*/
public int getQueueSize(){
return queueList.size();
}
/**
* 判斷隊列是否為空
*/
public boolean empty(){
return queueList.isEmpty();
}
/**
* 列印隊列內所有元素
*/
public void printQueue(){
Iterator iterator = queueList.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next()+" ");
}
System.out.println();
}
public static void main(String[] args) {
QueueDemo queueDemo = new QueueDemo();
queueDemo.push("a");
queueDemo.push("b");
queueDemo.push("c");
System.out.println(queueDemo.queueList.size());
queueDemo.pop();
queueDemo.printQueue();
System.out.println(queueDemo.queueList.size());
}
}
輸出：
3
b
c
2
用兩個棧實現隊列
package 用兩個棧實現隊列;/*
作者 :XiangLin
文件 :TwoStackToQueue.java
IDE :IntelliJ IDEA
*/
/**
* 用兩個棧實現隊列
*/
public class TwoStackToQueue {
stackDemo stack1 = new stackDemo();
stackDemo stack2 = new stackDemo();
/**
* 入隊列
*/
public void push(String str){
stack1.push(str);
}
/**
* 出隊列
*/
public String pop(){
if (stack2.empty()){
// 如果棧2為空，就要把棧1所有元素反彈到棧2中
while (!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
/**
* 判斷新隊列是否為空
*/
public boolean empty(){
if(stack1.empty() && stack2.empty()){
return true;
}else {
return false;
}
}
/**
* 列印隊列中所有元素
*/
public void printQueue(){
System.out.println("棧1中：");
stack1.printStack();
System.out.println("棧2中：");
stack2.printStack();
}
public static void main(String[] args) {
TwoStackToQueue queue = new TwoStackToQueue();
queue.push("a");
queue.push("b");
queue.push("c");
queue.printQueue();
queue.pop();
queue.printQueue();
}
}
輸出：
棧1中：
c
b
a
棧2中：
棧1中：
棧2中：
b
c