Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
コンピュータサイエンスにおけるキューとスタックの解説
Search
Satoshi Kaneyasu
January 28, 2024
Programming
0
520
コンピュータサイエンスにおけるキューとスタックの解説
Satoshi Kaneyasu
January 28, 2024
Tweet
Share
More Decks by Satoshi Kaneyasu
See All by Satoshi Kaneyasu
アプリケーションエンジニアがDistributed Load Testingで 負荷テストをしてみる〜Ver.B〜
satoshi256kbyte
2
42
アプリケーションエンジニアがDistributed Load Testingで負荷テストをしてみる〜Ver.A〜
satoshi256kbyte
2
78
AWS App Studio (Preview)は何分でアプリを作れるのか
satoshi256kbyte
0
180
AWS CodeGuruでPythonのコードを自動レビューしてもらおう
satoshi256kbyte
1
120
Gitでコンフリクトが起きたらコミットしよう
satoshi256kbyte
1
45
ワクワク状態を維持するレトロスペクティブ
satoshi256kbyte
1
98
プログラムのスタート地点はどこなのか?
satoshi256kbyte
1
65
DB調査をしやすくするためのログ設計
satoshi256kbyte
5
540
Amazon Aurora Serverless v2が意外と高かった話と、AWS Database Migration Serviceの話
satoshi256kbyte
1
290
Other Decks in Programming
See All in Programming
ドメイン駆動設計の実践
masuda220
PRO
17
5.2k
Jetpack for KMP
fornewid
1
290
Cloudflare Workers x AWS Lambdaの組み合わせユースケース / Cloudflare Workers x AWS Lambda Combination Use Case
seike460
PRO
2
310
Microservices rules (July 2024) : what good looks like
cer
PRO
0
1.6k
20240706_CDKConf
takuyay0ne
0
1.2k
Prompt FlowによるLLMアプリケーション開発
yuto2000
1
1k
CSC307 Lecture 09
javiergs
PRO
1
500
CSC307 Lecture 11
javiergs
PRO
0
240
CSC307 Lecture 14
javiergs
PRO
0
220
AHC035解説
terryu16
0
710
Xcode 16のPreviewModifierと@Previewableを活用した効率的なプレビュー方法の考察
ojun9
2
160
유연한 Composable 설계
l2hyunwoo
0
380
Featured
See All Featured
[RailsConf 2023] Rails as a piece of cake
palkan
35
4.4k
Typedesign – Prime Four
hannesfritz
37
2.2k
The Art of Programming - Codeland 2020
erikaheidi
48
13k
We Have a Design System, Now What?
morganepeng
46
7k
Java REST API Framework Comparison - PWX 2021
mraible
PRO
20
7.2k
Building Applications with DynamoDB
mza
89
5.8k
Raft: Consensus for Rubyists
vanstee
134
6.5k
Art, The Web, and Tiny UX
lynnandtonic
291
20k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
248
20k
Docker and Python
trallard
37
2.9k
Visualization
eitanlees
139
14k
Infographics Made Easy
chrislema
238
18k
Transcript
コンピュータサイエンスにおける キューとスタックの解説 2024.01.31 SATOSHI KANEYASU
⾃⼰紹介 ⽒名︓兼安 聡 職種︓クラウドエンジニア 最近のお仕事︓DevOpsの推進 趣味︓サックス、筋トレ、CS ゲーム 資格︓ X(Twitter)︓@satoshi256kbyte 1/9
追加
はじめに • また情報処理技術者試験の季節が近づいてきてますね。 • 個⼈の感想ですが、勉強は意味を知らないと頭に⼊りません。 • 昔はピンとこなかった、キューをここ数年使いまくってるので、 その解説をします。 • ついでにスタックも解説します。
キュー(Queue)とスタック(Stack) • どちらもデータの格納・取り出し⽅法の⽤語 • それぞれ、データの格納・取り出しのルールが決まっている • ルールが決まっているのがポイント • ルールが決まっている=保証されている
キュー(Queue) • 先⼊れ先出し⽅と呼ばれるデータ格納⽅式 • First-In-First-Out、略してFIFO • 現実世界で⾔うと、病院の受付番号など • 病院に⾏く •
受付して、受付番号をもらう • 受付番号順に診察
キューは受付番号のようなもの
キューがなかったどうなるか︖ • 同時に対処できる数を超えて訪問者を受けいれてしまう • 訪問者がいつまで待てばいいのかわからない • ↑による焦りから更なる混雑を招く • 多少処理時間が伸びたとしても、 負荷を平準化し安定化させることが必要なシチュエーションがある
スタック(Stack) • 後⼊れ先出し⽅と呼ばれるデータ格納⽅式 • Last-In-First-Out、略してLIFO • 現実世界で例えるのは難しい • ブラウザの戻る •
エディタのUndo機能 • プログラムでエラーが発⽣した時のスタックトレース
ブラウザの戻るの例 番号 訪問履歴 4 https://example.com/page2 3 https://example.com/page1 2 https://example.com/calendar 1
https://example.com 現在のページ︓https://example.com/page3
キューの使⽤例 – キュー未使⽤ DOWNLOAD Server • 画⾯の内容のPDFでダウンロードする機能を考える
キューの使⽤例 – DLする⼈が増えたら DOWNLOAD Server • 受け付けたら⼀気にPDFをDLさせる⽅式だと混雑しやすい • 受け付ける •
PDFを作成する • 受け付ける • PDFを作成する • 受け付ける • PDFを作成する • 受け付ける • PDFを作成する ❌ ❌ 重たい処理が、 同時発⽣する混雑する
キューの使⽤例 – 混雑は混雑を⽣む DOWNLOAD Server • 混雑が発⽣すると何度も試す⼈が増えて余計混雑を⽣む • 受け付ける •
PDFを作成する • 受け付ける • PDFを作成する • 受け付ける • PDFを作成する • 受け付ける • PDFを作成する ❌ ❌ ❌ ❌ ❌ ❌ ❌
キューの使⽤例 – キューを活⽤する Server • キューを活⽤してDOWNLOADの受付とPDF出⼒を分ける • 受け付ける • PDFを作成する
• 受け付ける • 受け付ける • 受け付ける キュー DOWNLOAD4 DOWNLOAD2 DOWNLOAD2 DOWNLOAD1 4 DOWNLOAD
キューの使⽤例 – システムを分ける Server • キューを活⽤してDOWNLOADの受付とPDF出⼒を分ける • 受け付ける • PDFを作成する
• 受け付ける • 受け付ける • 受け付ける キュー DOWNLOAD4 DOWNLOAD2 DOWNLOAD2 DOWNLOAD1 4 DOWNLOAD
まとめ • キューは先⼊れ先出し、スタックは後⼊れ先出し • 多数の⼈が使うシステムだと、キューはかなり有⽤ • クラウドとも相性が良い • クラウド絡めるとキューはめちゃめちゃ使います。 •
何に使うかわからない技術があれば教えてください できる限り答えられるようにします