about 演算法 項目介紹 工作之餘，代碼敲多了，停下來思考思考，會有異常不到的收穫。。。只為更好的自己 如何用棧實現隊列？ 提示下：用一個棧肯定是沒辦法實現隊列，但如果我們有兩個棧呢? 分析：棧和隊列的特性 棧是先進後出，FILO 出入元素都是在同一端（棧頂） 入棧 1540432924606.p ...
about 演算法
項目介紹
工作之餘，代碼敲多了，停下來思考思考，會有異常不到的收穫。。。只為更好的自己
如何用棧實現隊列？
提示下：用一個棧肯定是沒辦法實現隊列，但如果我們有兩個棧呢?
分析：棧和隊列的特性
-
棧是先進後出，FILO
出入元素都是在同一端（棧頂）
入棧
1540432924606.png出棧
1540432988027.png -
隊列是先進先出，FIFO
-
出入元素是在不同的兩端（隊頭和隊尾）
入棧
1540433080831.png
出棧
1540433109205.png
思考：組裝
讓一個棧作為隊列的入口，負責插入新元素；另外一個棧作為隊列的出口，負責移除老元素。
如圖所示
1540433258745.png
讓棧A中的所有元素按順序出棧，再按照出棧順序壓入棧B。
這樣一來，元素從棧A彈出並壓入棧B的順序是3，2，1和當初進入棧A的順序123是相反的，如圖
1540433561742.png
1540433605060.png
此時讓元素1 “出隊”，也就是讓元素1從棧B彈出
1540433651738.png
代碼實現：
/**
* @author sunyang
* @date 2018/10/25 10:18
*/
public class StackImplQueue {
/**
* 定義兩個棧來實現隊列
* 棧A 負責插入新元素
* 棧B 負責移除老元素
*/
private Stack<Integer> stackA = new Stack<>();
private Stack<Integer> stackB = new Stack<>();
/**
* 入隊操作
* @Param element
*/
public void enQueue(int element){
stackA.push(element);
}
/**
*
* 出隊操作
*/
public Integer deQueue(){
if (stackB.isEmpty()){
if (stackA.isEmpty()){
return null;
}
fetchFormStackA();
}
return stackB.pop();
}
/**
* 從stackA棧中拿到出棧元素壓入棧B
*/
private void fetchFormStackA() {
while (!stackA.isEmpty()){
stackB.push(stackA.pop());
}
}
public static void main(String[] args) {
StackImplQueue stackQueue = new StackImplQueue();
stackQueue.enQueue(1);
stackQueue.enQueue(2);
stackQueue.enQueue(3);
System.out.println(stackQueue.deQueue());
System.out.println(stackQueue.deQueue());
System.out.println(stackQueue.deQueue());
stackQueue.enQueue(4);
System.out.println(stackQueue.deQueue());
}
}
列印結果
1540435153368.png
題外話：時間複雜度
入棧操作的時間複雜度顯然是O(1)
出棧操作的時間複雜度如果發生轉移的話就是O（n）
如果沒有發生轉移的話也是O（1）
