[DataStructure] Stack & Queue

2556 ワード
テキストリンク

まず,StackとQueueは線形データ構造である.

Stack


  • 先入要素の構造
  • 第1の出力形式の資料構造.
  • アンドロイドシステムは、スタック管理アクティブデバイスを使用します.
  • 時間複雑度:O(n)
  • 空間複雑度:O(n)
  • 関数に使用されるcallスタック、文字列逆シーケンス出力、演算子接尾辞表現など.

    • Queue


  • は、先に入った要素が先に出てくる構造です.
  • 第1の出力形態の資料構造.
  • キューには多くの使用分野があります.Androidの場合、Looperのメッセージキューが一例です.
  • 時間複雑度:O(n)
  • 空間複雑度:O(n)
  • バッファは,乱入を処理できず,BFSなどを閲覧するために用いられる.

    • 2つのスタック実装キューを使用



    A,B順のデータをスタックに入れて取り出すとB,Aとなる.
    これを順番にスタックに戻し、外すとA、Bになります.
    内部動作は異なりますが、結果は入る順番に現れるキューです.
    他の人が作成した関連コードが参考になります.
    package Stack;

import java.util.Stack;

/**
 * created by victory_woo on 2020/05/06
 * Stack 2개를 이용해서 Queue 구현하기.
 */
public class StackWithQueue {
    public static void main(String[] args) {
        StackQueue<String> queue = new StackQueue<>();
        queue.enQueue("A");
        queue.enQueue("B");
        queue.enQueue("C");

        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
    }

    static class StackQueue<T> {
        private Stack<T> inBox;
        private Stack<T> outBox;

        StackQueue() {
            inBox = new Stack<>();
            outBox = new Stack<>();
        }

        void enQueue(T item) {
            inBox.push(item);
        }

        Object deQueue() {
            if (outBox.isEmpty()) {
                while (!inBox.isEmpty()) {
                    outBox.push(inBox.pop());
                }
            }

            return outBox.pop();
        }
    }
}
    オブジェクト
    7/9メディアクエリー