キューとスタックの解説🎢📚

キューとスタック

YouTube動画

キューとスタック:データ構造🎢📚過去問解説!/ITパスポート・基本情報技術者・高校情報

基本情報技術者試験では、たびたび出題される
キュースタックについて、問題が解けるようになる解説をしていきます!

キューとは

キュー先入れ先出しと言われ、文字通り入ったデータの順に、出すときもデータが出ていく構造です。

エンキューとデキュー

キューの構造を取るときデータが入ることエンキューといい、データが出ていくことデキューといいます。

キュー

この図の場合、1・2・3とデータをエンキューすると同じく、1・2・3デキューされる状態です。

キューの具体例 🎢

具体例なイメージは、人の行列を思い出してみてください🎡

ディズニーランドでアトラクションを待っているとき、先に列に並んでいる人から、アトラクションに案内されますね🎠

これと同じで、予約システムのキャンセル待ち処理や、プリンターの印刷ジョブキューの構造をとったシステムになっています。

スタックとは

スタックは、後入れ先出しと言われ、後から入ったデータが、先に出てくる という構造です。

PUSHとPOP

スタックにおいて、データが入ることPUSHといい、出ていくことPOPといいます。

スタックは、用語同士の関連性がないため混乱しやすいです。

試験問題にPUSHPOPの用語補足は必ず書いてあるわけではないので、ここは頑張って暗記をしていきましょう👆

 

pushとpop

 

この図の場合、1・2と情報をPUSH したら、2・1と情報がPOPされる状態です。

スタックの具体例 📚

身近な例としては、本を積み上げたときに上から取っていく📚 という行動です!

システムに置き換えると、WEBブラウザの戻るボタンや、CPUのレジスタスタックの構造を取っています。

スタックキュー 2つの違い

通称として、

Queue  先入れ先出しのことを、First In First Out:FIFO といい
Stack   後入れ先出しのことを、Last In First Out:LIFO といいます。

 

FIFOとLIFO

 

スタックキューで、名前と構造が混乱してしまう場合には

仕事がスタックする等の言葉から、スタック構造での 1 のデータの上に沢山の情報が積み上がって、なかなかPOPできない状態を思い浮かべてみてください。

すると、箱型のほうがスタックだな、と確認できるとおもいます🙌

スタックとキューを利用した過去問にチャレンジ!

最後に、過去問の改題を解くことで、この2つの構造を理解していきましょう!

ABCDの4つのデータが入ったキューと、空のスタックがある。
キューのデータをDCBAに並び替えるとき、最小のデキューの実行回数は何回か?

 

過去問

 

問題は、実際に図を書きながら整理していきましょう!

まずは、キューの情報をスタックに入れ替えることで、DCBAの操作を実現していきましょう!

 

DCBAの操作

 

・まずは、移動できるA → B → C を順番にスタックに入れていきましょう。

・スタック側にも、A ・ B ・ C の順にPUSHされました。

・これをこのまま、POPして戻してあげましょう。

 すると、C → B → A の順に移動させることができ、キューの構造に DCBA を入れることができました!

問題では、最小のデキューの回数を聞かれているため、数えてみると、1・2・3回の操作がありました。

そのため、3回 が答えとなります!

 

試験では例題のように、

キューやスタックが何個あるとき、何回の操作が必要ですか?

1回の操作で完了するには、最低何個のスタックがあれば良いですか?

といった問題が多いので、スタックとキューの問題は構造を理解した上で、

パターンを1つずつ整理する力を身に着けていきましょう!

他にも、過去問動画をみて、ぜひ問題を解けるようになっていきましょう💡

 

今日も最後までブログを見てくださり、ありがとうございました!

次のITすきま教室でお会いしましょう👋

あなたのIT知識を
もっと深めませんか?

ITすきま教室では、IT関連の資格取得や教養を身につけるための記事講座・動画講座を数多く取り揃えています!

コンピュータサイエンスの他の記事

企業研修や情報授業、イベント司会まで講師・講演を依頼してみませんか?

ITすきま教室では講師や講演のご依頼もお受けしております。
YouTubeチャンネル運営のほか、ナレーターや司会業としても活動してきた経験から、分かりやすく満足度の高い講義をご提供します!

講師ご依頼特設ページへ

チャンネル登録者数8万人突破!YouTube好評運用中!

解説が分かりやすいと沢山の方からご好評をいただいており、IT資格勉強コンテンツで日本トップの登録者数を集めています。すきま時間を使って勉強して資格合格や成績アップを目指しましょう!

Youtubeチャンネルはこちら

単語帳BOT

X(旧Twitter)で関連用語を3時間に1度つぶやきます!
すきま時間の学習にお役立てください!

ITすきま教室のLINEスタンプができました!

ITすきま教室の公式LINEスタンプができました!
ポップなTechnologyをテーマに、
ボケたり、ツッコんだり、使い勝手を意識して
プログラミングの世界を表現しています!

LINEストアへ
アプリで効率良く学習!
ITすきま教室が本になりました!