使用棧實現(xiàn)一個隊列,需要弄清楚棧和隊列的區(qū)別:
棧:先進(jìn)后出;
隊列:先進(jìn)先出。
實現(xiàn)思路:
1)通過兩個棧(pushStack / popStack)對倒,確保 popStack 棧的出棧順序與隊列出列一致。
2)核心難點在加入隊列操作,假設(shè)隊列中已經(jīng)加入1、2、3、4,加入5的過程:
2.1)假設(shè)已經(jīng)加入1/2/3/4
2.2)把popStack中的數(shù)據(jù)導(dǎo)入pushStack
2.3)pushStack加入5
2.4)把pushStack中的數(shù)據(jù)導(dǎo)入popStack
流程示意圖如下:
實現(xiàn)代碼:
import java.util.Stack; public class QueueWithStack<T> { /** * Test 測試代碼 */ public static void main(String[] args) { QueueWithStack<Integer> queue = new QueueWithStack<>(); queue.add(1); System.out.println("入隊列:1"); queue.add(2); System.out.println("入隊列:2"); queue.add(3); System.out.println("入隊列:3"); queue.add(4); System.out.println("入隊列:4"); System.out.println("出隊列:" + queue.pop()); System.out.println("出隊列:" + queue.pop()); queue.add(5); System.out.println("入隊列:5"); queue.add(6); System.out.println("入隊列:6"); System.out.println("===================="); while (false == queue.isEmpty()) { System.out.println("出隊列:" + queue.pop()); } System.out.println("隊列內(nèi)元素個數(shù):" + queue.size()); } // 入棧是,將數(shù)據(jù)寫入該集合,然后在推向pop集合。 private Stack<T> pushStack = null; // 出站時,讀取該集合 private Stack<T> popStack = null; public QueueWithStack() { pushStack = new Stack<>(); popStack = new Stack<>(); } public boolean isEmpty() { return popStack.isEmpty(); } public int size() { return popStack.size(); } public void add(T t) { while (false == popStack.isEmpty()) { T val = popStack.pop(); pushStack.push(val); } pushStack.add(t); while (false == pushStack.isEmpty()) { T val = pushStack.pop(); popStack.push(val); } } /** * 從隊列中取出數(shù)據(jù),并從隊列中移除數(shù)據(jù) */ public T pop() { if (isEmpty()) { throw new RuntimeException("Queue is empty."); } return popStack.pop(); } /** * 獲取棧頂元素,但不會從隊列中移除數(shù)據(jù) */ public T peek() { if (isEmpty()) { throw new RuntimeException("Queue is empty."); } return popStack.peek(); } }
打印結(jié)果:
入隊列:1 入隊列:2 入隊列:3 入隊列:4 出隊列:1 出隊列:2 入隊列:5 入隊列:6 ==================== 出隊列:3 出隊列:4 出隊列:5 出隊列:6 隊列內(nèi)元素個數(shù):0
?
基礎(chǔ)才是編程人員應(yīng)該深入研究的問題,比如:
1)List/Set/Map內(nèi)部組成原理|區(qū)別
2)mysql索引存儲結(jié)構(gòu)&如何調(diào)優(yōu)/b-tree特點、計算復(fù)雜度及影響復(fù)雜度的因素。。。
3)JVM運行組成與原理及調(diào)優(yōu)
4)Java類加載器運行原理
5)Java中GC過程原理|使用的回收算法原理
6)Redis中hash一致性實現(xiàn)及與hash其他區(qū)別
7)Java多線程、線程池開發(fā)、管理Lock與Synchroined區(qū)別
8)Spring IOC/AOP 原理;加載過程的。。。
【+加關(guān)注】。
本文摘自 :https://blog.51cto.com/u