使用棧實(shí)現(xiàn)一個隊(duì)列,需要弄清楚棧和隊(duì)列的區(qū)別:
棧:先進(jìn)后出;
隊(duì)列:先進(jìn)先出。
實(shí)現(xiàn)思路:
1)通過兩個棧(pushStack / popStack)對倒,確保 popStack 棧的出棧順序與隊(duì)列出列一致。
2)核心難點(diǎn)在加入隊(duì)列操作,假設(shè)隊(duì)列中已經(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
流程示意圖如下:
實(shí)現(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("入隊(duì)列:1"); queue.add(2); System.out.println("入隊(duì)列:2"); queue.add(3); System.out.println("入隊(duì)列:3"); queue.add(4); System.out.println("入隊(duì)列:4"); System.out.println("出隊(duì)列:" + queue.pop()); System.out.println("出隊(duì)列:" + queue.pop()); queue.add(5); System.out.println("入隊(duì)列:5"); queue.add(6); System.out.println("入隊(duì)列:6"); System.out.println("===================="); while (false == queue.isEmpty()) { System.out.println("出隊(duì)列:" + queue.pop()); } System.out.println("隊(duì)列內(nèi)元素個數(shù):" + queue.size()); } // 入棧是,將數(shù)據(jù)寫入該集合,然后在推向pop集合。 private Stack<T> pushStack = null; // 出站時(shí),讀取該集合 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); } } /** * 從隊(duì)列中取出數(shù)據(jù),并從隊(duì)列中移除數(shù)據(jù) */ public T pop() { if (isEmpty()) { throw new RuntimeException("Queue is empty."); } return popStack.pop(); } /** * 獲取棧頂元素,但不會從隊(duì)列中移除數(shù)據(jù) */ public T peek() { if (isEmpty()) { throw new RuntimeException("Queue is empty."); } return popStack.peek(); } }
打印結(jié)果:
入隊(duì)列:1 入隊(duì)列:2 入隊(duì)列:3 入隊(duì)列:4 出隊(duì)列:1 出隊(duì)列:2 入隊(duì)列:5 入隊(duì)列:6 ==================== 出隊(duì)列:3 出隊(duì)列:4 出隊(duì)列:5 出隊(duì)列:6 隊(duì)列內(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特點(diǎn)、計(jì)算復(fù)雜度及影響復(fù)雜度的因素。。。
3)JVM運(yùn)行組成與原理及調(diào)優(yōu)
4)Java類加載器運(yùn)行原理
5)Java中GC過程原理|使用的回收算法原理
6)Redis中hash一致性實(shí)現(xiàn)及與hash其他區(qū)別
7)Java多線程、線程池開發(fā)、管理Lock與Synchroined區(qū)別
8)Spring IOC/AOP 原理;加載過程的。。。
【+加關(guān)注】。
本文摘自 :https://blog.51cto.com/u