當前位置:首頁 > IT技術 > 編程語言 > 正文

JAVA:使用棧實現(xiàn)一個隊列
2021-10-27 14:41:41

使用棧實現(xiàn)一個隊列,需要弄清楚棧和隊列的區(qū)別:

棧:先進后出;

隊列:先進先出。

實現(xiàn)思路:

1)通過兩個棧(pushStack / popStack)對倒,確保 popStack 棧的出棧順序與隊列出列一致。

2)核心難點在加入隊列操作,假設隊列中已經加入1、2、3、4,加入5的過程:

2.1)假設已經加入1/2/3/4

2.2)把popStack中的數(shù)據(jù)導入pushStack

2.3)pushStack加入5

2.4)把pushStack中的數(shù)據(jù)導入popStack

流程示意圖如下:

JAVA:使用棧實現(xiàn)一個隊列_數(shù)據(jù)導入

實現(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("隊列內元素個數(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();
    }
}

打印結果:

入隊列:1
入隊列:2
入隊列:3
入隊列:4
出隊列:1
出隊列:2
入隊列:5
入隊列:6
====================
出隊列:3
出隊列:4
出隊列:5
出隊列:6
隊列內元素個數(shù):0

?

基礎才是編程人員應該深入研究的問題,比如:
1)List/Set/Map內部組成原理|區(qū)別
2)mysql索引存儲結構&如何調優(yōu)/b-tree特點、計算復雜度及影響復雜度的因素。。。
3)JVM運行組成與原理及調優(yōu)
4)Java類加載器運行原理
5)Java中GC過程原理|使用的回收算法原理
6)Redis中hash一致性實現(xiàn)及與hash其他區(qū)別
7)Java多線程、線程池開發(fā)、管理Lock與Synchroined區(qū)別
8)Spring IOC/AOP 原理;加載過程的。。。
+加關注】。

本文摘自 :https://blog.51cto.com/u

開通會員,享受整站包年服務立即開通 >