データ構造とアルゴリズム入門

10283 ワード

データ構造は、問題を解決するためのよく定義された命令のシーケンスまたは与えられたタスクを達成する間、それらが効率的にアクセスされて、働くことができるように、データを編成して、記憶する方法である.
この記事では、スタックとキューである最も一般的なデータ構造とPythonでの実装について詳しく説明します.

スタック
スタックは、挿入と削除のためにLFO(最後の最初のアウト)原則を使用しているアイテムを格納する線形データ構造として、コンピューターサイエンスで定義される最も初期のデータ構造のうちの1つです.
スタックの明確な理解を得るために本の山/スタックを考える.あなたはスタックの上部に本を追加するので、最初にピックアップされる1つのスタックに追加された最後のものになります.
スタックには2つの操作があります.
  • push -スタックの先頭に項目を追加します.
  • POP -スタックから項目を削除します.


  • なぜ我々はスタックを使用しますか?
  • スタックは、学習し、実装する簡単です.
  • スタックは、データを格納し、取得することができます.スタックは、挿入と削除操作のためにo ( 1 )時間をとります.
    スタックの実世界ユースケース
  • ウェブブラウザは以前にアクセスしたURLを追跡するためにスタックを使用します.ときに、新しいページを訪問すると、スタックに追加されるときに戻るボタンを押すと、スタックがポップされ、以前のURLにアクセスされます.
  • テキストエディターのアンドゥ機構は、すべての変更を続けるスタックを使用します.
  • 他のデータ構造を実装するために、
  • は、グラフと木の検索を実装するために使用されます.
  • コンパイラとパーサーは、スタック
  • を使用します
    More applications of Stack Data structures

    スタックメソッド
    スタック操作は以下のメソッドを使用して実装されます:
    スタック.isempty -スタックが空の場合にtrueを返し、そうでなければfalseを返します.スタック.length () -スタックの長さを返します.スタック.top () -スタックの先頭要素へのポインタ/リファレンスを返します.スタック.push(x)-要素Xをスタックの先頭に挿入します.スタック.pop () -スタックの先頭要素を削除し、それを返します.
    Pythonでのスタック実装.
    Pythonでは、次のような方法でスタックを実装できます
  • 組み込みのリストデータ構造を使用します.
  • 効率的に1つのオブジェクトのスタック操作を提供するdequeライブラリを使用している
  • .
  • リストを使用してスタック.
    リストを使用してスタックを実装するには、appendとpopメソッドを使用します.
    add ()メソッドは、既存のリストに単一の項目を追加します
    pop ()は、指定した位置の要素を削除します

    s = []
    
    s.append('stack')
    s.append('queue')
    s.append('list')
    s.append('tuple')
    
    print(s)
    
    出力
    ['stack', 'queue', 'list', 'tuple']
    
    ポップの使用
    s.pop()
    >>tuple
    s.pop()
    >>list
    s.pop()
    >>queue
    s.pop()
    >>stack
    s.pop()
    >>IndexError: pop from empty list
    
    Check this implementation
    Read More about stacks

    キュー
    スタックのように、キューは線形データ構造です.
    キューは、挿入と削除のためのFIFO(first - in - first - out)原理を使用して項目を格納します.

    Pythonのキューに関連する操作.

  • enqueue :キューの最後に要素を追加します.キューが全容量に達するとオーバーフロー状態になる.
  • dequeue :キューから要素を削除する.キューが空になるとアンダーフロー状態になる.
  • フロント:キューから最初の項目を返します.
  • Remember :キューから最後の項目を返します.

  • キューのアプリケーション
    キューは次のシナリオで有用です
  • リアルタイムシステムの割り込み処理-割り込みは、到着したときと同じ順番で処理されます.
  • ウェブサイト交通を取り扱う
  • .
  • プリンタまたはCPU作業スケジューリングのような単一の共用資源に関する
  • サービング要求.
  • Applications of Queue Data Structure

    Pythonでキューを実装する方法
    Pythonでキューを実装する方法は様々です.The
    コモンウェイズ
    ビルトインリストデータ構造を使用する
  • .
  • コレクションを使用して
  • .デーク図書館

  • リストを持つPythonでのキューの実装
    listのappend ()およびpop ()メソッドは、キューから要素を挿入・削除するために使用します.
    # Initialize a queue
    
    queue = []
    
    # Adding elements to the queue
    
    queue.append('Python')
    
    queue.append('Javascript')
    
    queue.append('Typescript')
    print(queue)
    
    出力
    ['Python', 'Javascript', 'Typescript']
    
    # Removing elements from the queue
    
    
    
    print(queue.pop(0))
    
    print(queue.pop(0))
    
    print(queue.pop(0))
    
    
    print(queue)
    
    出力
    Python
    Javascript
    Typescript
    []
    

    コレクションを持つPythonでキューを実装する.堤防
    Pythonコレクションモジュールからのdequeクラスは、キューを実装するためにも使用できます.DEQEがより速いEnqueueとDequeue操作を提供するので、それはより効率的です.
    from collections import deque
    
    queue = deque()
    
    queue.append('Black')
    
    queue.append('White')
    
    queue.append('Orange')
    
    print(queue)
    
    出力
    deque(['Black', 'White', 'Orange'])
    
    私はあなたが私がそれを書いて楽しんだとして記事を読んで楽しむことを願って、次の有用なリソースと参考資料を使用しています.
    Find the full source code here
    Using the Queue Data Structure in Python
    How to implement a queue in Python