Stack & Queue

3844 ワード

データ構造テキストリンク

スタックとキュー

資料を表現して処理する方法の一つで、スタックとキューがあります.

スタック:LIFOで積み上げて荷揚げするのと同じ
下から上へ

キュー:先入先出(FIFO)は、トンネルなどを通ればいいと思います.
まず入力したデータがまず流出する資料構造.

Stack

後で入るデータが最初に現れる構造.

Reference
https://youtu.be/whVUYv0Leg0

Queue

先進入先出データの構成

Reference

https://youtu.be/W3jNbNGyjMs

 </blockquote> <hr/> <h2>우선순위 큐(Priority Queue)</h2> <ul><li>優先キュー: まず、最も優先度の高いデータのデータ構造を削除します. 優先順位でデータを処理する場合に使用します. 製品のデータが格納されている場合は、まず価値の高いものを取り出す必要があります.</li></ul> 優先キューを実装する方法は様々ですが、リストとスタック(heap)を使用する場合については <ul><li> N個のデータを処理する時間複雑度</li></ul> <table><thead><tr><th>優先キュー実装方式</th><th>挿入時間</th><th>削除時間</th><tr></tr><td><td>リスト</td><td><td><td><td><td><td></td><td><td><td></tr><td><td><td><td><td><td><td><td> 簡単にN個のデータをお尻に入れ、それを全て取り出して(お尻の位置合わせ)位置合わせ(お尻の位置合わせ) <ul><li>の場合,時間複雑度はO(Nlogn)であった.</li></ul> <h3>힙(heap)</h3> <ul><li> hipは完全なバイナリツリー構造である. </li> <li> hipデータ構造はpythonでheapqライブラリを使用して利用できます. Default = Min-heap -> Max-heapをマイナス(-)で置き換えるといいです. </li> <li> hipでは常にルートノード(root node)を削除します. </li> <li> 最小スタック(minheap) <ul><li>ノードの最小値.</li> <li>の値が最も小さいデータは優先的に削除されます.</li></ul> </li> <li> 最大スタック(最大スタック) <ul><li>ノードの最大値.</li> <li>の値が最も大きいデータは優先的に削除されます.</li></ul> <blockquote> フルバイナリツリー ツリー ルートノードから左サブノードと右サブノードの順にデータを挿入します. <img src="https://s1.md5.ltd/image/4083ae0e8aa0adc0d06ab80795f5c3cd.png"/> </blockquote> </li></ul> 最小臀部構成関数:Min-Hapify() <ul><li>(上向き)の親ノードにドリルダウンし、その値が親ノードより小さい場合に位置を交換します.</li></ul> お尻に新しい要素を挿入する場合: <ul><li> O(logn)の時間的複雑さを用いて臀部特性を維持することができる. <img src="https://s1.md5.ltd/image/375094855000037a5dc22e1c0f9149d2.png"/> 臀部から要素を除去する場合:</li><li>元素が除去されると、O(logn)の時間的複雑さはhip特性を維持することができる.<ul><li>要素を削除すると、最後のノードがルートノードの位置にあることを確認します.</li> <li>以降は、ルートノードから下(より小さなサブノード)へHeapify()を行います. <img src="https://s1.md5.ltd/image/0d48e4f760b606331dfc4a912d30e6bd.png"/> <img src="https://s1.md5.ltd/image/4b05e29f6a069819b8469b14fc4a11d2.png"/> </li></ul> </li></ul> <h2>Deque</h2> <ul><li> Dequeは、先入先出方式で一方向に実行されるキューとは異なり、双方向に実行することができる.</li> <li>、すなわち、構造の両端にデータを追加または削除することができる.最後にデータを追加/削除する速度が大幅に速くなります. -> 両端データへのアクセスはO(1)である.</li></ul> <h3>데크(deque)</h3> 言い換えれば、dakeはスタックのように使用してもよいし、キューのように使用してもよい. ほとんどの場合、pythonはlistよりも効率的にデータを処理できます. 特に,データの頻繁な出入りアルゴリズムでは,より大きな効果が得られる.p> <ul><li> Pythonではコレクションライブラリを使用してdequeを使用できます.</li> <li>デック(deque)に使用できる方法は、次のとおりです.</li></ul><pre><code class="language-null">deque.append(item): item을 데크의 오른쪽 끝에 삽입 deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입 deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제 deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제 deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가 deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가 deque.remove(item): item을 데크에서 찾아 삭제 deque.rotate(num): 데크를 num만큼 회전(양수면 오른쪽, 음수면 왼쪽).</code></pre><blockquote> Reference <a href="https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw" rel="nofollow">유튜브 나동빈</a> <a href="https://ooeunz.tistory.com/31?category=813437" rel="nofollow">윤자이 기술블로그</a> <a href="https://leonkong.cc/posts/python-deque.html" rel="nofollow">블로그 Leon</a> </blockquote>

Reference

この問題について(Stack & Queue), 我々は、より多くの情報をここで見つけました https://velog.io/@nine57/자료구조-Stack-Queue

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

動的htmlページの生成(一)

[アルゴリズム/規格]2210号:デジタルジャンプ(python)